#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

## Sunday, February 15, 2009

### 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.

## Saturday, February 14, 2009

### 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 eventListHere, 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 eventListIn 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.

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 bfIt 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 eventListWe 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.

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 bfThe 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 eventListThis 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.

Subscribe to:
Posts (Atom)