Quicksort in F# (again)

Here is the quicksort algorithm in F#. Nothing new here, this algorithm can be found on many sites. But I noticed that none of them takes advantage of partial application of (<) and (>=) operators in List.filter.

#light

let rec quicksort l =
      match l with
      |[] -> []
      |h::t -> quicksort (List.filter ((<) h) t) @ [h] @ (quicksort (List.filter ((>=) h) t))

let l = [8;2;10;5;3;6;12;23;1;2;5;11]

quicksort l

Functional Reactive Programming in F# (2)

In my previous post about Functional Reactive Programming, we have seen how a continuous function of time could be implemented in F# (Behaviors) and how it was possible to create more complex Behaviors by combining simpler Behaviors. However, such Behaviors are in fact 'pure' functions of time, without any state. In this post, we will see how Behaviors can handle state in a functional way (without side effects). We start by considering a very simple state machine that consumes unit values () and produces a succession of boolean values: true, false, true, false... Let's start with a classic, imperative implementation:

#light

type 'a StateMachine = unit -> 'a


let TogglingMachine =
     let state = ref true
     let bf evt = state := not (!state)
                  !state
     in (bf :bool StateMachine)

let eventList = [(); (); (); ()]

let r = List.map TogglingMachine eventList

Here, a state machine that produces results of type 'a is simply represented as a function from unit to 'a. Here is a second example. The next machine accepts a unit option as input value and returns a result which is defined as follows:

• If the input value is None then the machine returns -1.
• If the input value is Some() then the machine returns the number of None received since the last Some().

type 'a StateMachine = unit option -> 'a


let CountingMachine : int StateMachine =
 let nbNone = ref 0
 let bf evt = match evt with
              |None ->   nbNone := !nbNone + 1;
                         -1
              |Some _ -> let res = !nbNone;
                         nbNone := 0;
                         res
 in bf

let eventList = [None; None; Some(); None; Some(); Some(); None]

let r = List.map CountingMachine eventList

In both examples above, we see that the machine needs to retain some state between two invocations and it does it with the help of some side effects (ref 0 and ref true). There are several solutions to create state machines without side effects. The general idea is to design a machine that externalizes its state. In practice, that means:

• Its state should be given as an additional input argument.
• The machine produces a result that, in addition to itsexpected output, contains its new state.

Let's illustrate this with the previous example (the CountingMachine above). First, we have to modify the type representing the machine. It is now a function that takes 2 arguments. The first one is the previous state of the machine (the state before the call) and the second is the usual unit option value. The state is simply the current count of None values. This function returns a pair made of the count of None as explained above and the new state of the machine after the call.

type StateMachine = int -> unit option -> (int * int)


let CountingMachine : StateMachine =
     let bf previousCount evt =
          match evt with
          |None ->  (-1, previousCount+1)
          |Some _ -> (previousCount, 0)
     in bf

It is now the responsibility of the caller to make sure that the right state is passed to the Machine. For this, we can define a runList function which runs the machine against a list of inputs.

let rec runList previousCount machine events =
    match events with
    |[] -> []
    |event::t -> let (res, nextCount) = machine previousCount event
                 nextRes :: runList nextCount machine t

let r = runList 0 CountingMachine eventList

We see clearly the drawbacks of such a solution. The runList function must be aware of two things:

• The first, as already mentionned, is the handling of the state. Unfortunately, in this solution and in the next solution (a little bit below), this cannot be avoided.
• The other drawback is the dependency of runList on the type of the state - int in this case. Thus, every Machine designed on state externalization needs its own runList function.
• A third drawback, a bit less obvious at first sight, is the fact that the state must always be of the same type across several calls. It is not possible to replace, from one call to another, such a Machine with another that has a state of a different type.

Of course, the type for the machine presented above may be made generic:

type StateMachine<'a, 'state> = 'state -> unit option -> ('a * 'state)

Last solution, based on residual state machines. This solution is based on a simple fact. Since a State Machine is basically a function of one argument, let's imagine that this function returns both its expected value and new State Machine. This a new State Machine acts a bit like the state in the previous example. The type of such a machine is:

type 'a StateMachine = SM of (unit option -> ('a * 'a StateMachine))

We can already define some simple state machines: A machine that always returns true. Two implementation are possible, depending on which definition is recursive.

let AlwaysTrueMachine = let rec bf evt = (true, SM bf)
                        SM bf


let rec AlwaysTrueMachine = let bf evt = (true, AlwaysTrueMachine)
                            SM bf

The Toggling Machine in the beginning of this post becomes.

let TogglingMachine = let rec bf previous evt = (previous, SM (bf (not previous)))
                      SM (bf true)

To be able to run these machines, we must again define a runList function:

let rec runList (SM bf) events =
       match events with
       |[] -> []
       |h::t -> let (r, nb) = bf h
                 r :: runList nb t

let r = runList TogglingMachine eventList

This runList function is somewhat similar to the one already defined above but with 2 advantages:

• It does not depend on the way the state machine models its state (or not - see the AlwaysTrueMachine which has no state at all).
• As a consequence, a state machine may well change its state representation at will. The only condition is that the values it produces must have the same type.

So we come to the end of this post. As a last note, I must admit that there could be another way to model state machines, which is based on sequences but I have not explored this direction yet. In a next post, I will make the connection between state machines and Behaviors.