A lazy example
By Laurent Le Brun on Tuesday, July 17 2007, 00:01 - [EN] F# articles - Permalink
On a french forum, someone wrote an little exercise: how to get all sets of numbers (> 0) whose sum is exactly n? Here is my solution, using lazy evaluation.
On a french forum, someone wrote an little exercise: how to get all sets of numbers (> 0) whose sum is exactly n? For example, with n = 5, result is:
5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
I wrote a naive but short and easy solution in F#:
[fsharp] let sums n = let rec sumrec = function | 0, _ -> [] | n, m -> [for i in 1 .. min n m ->> [for j in sumrec((n - i), i) -> i :: j]] sumrec(n, n)
It uses list comprehensions to compute the set (actually it returns a list, but all elements are distinct). Someone gave the following Haskell code, using a (lazy) matrix to store intermediate results (this is memoization):
sums n = a ! (n,n) where a = array ( (0,0), (n, n) ) $ ( (0,0), [] ) : populateList populateList = [( (k,l), [x:xs | x<-[1..l], xs<-a!(k-x, min (k-x) x)] ) | k<-[1..n], l<-[1..k]]
I converted this function in F#. It is interesting to see that F# can be as expressive and short as Haskell, even on algorithms using lazy evaluation:
[fsharp] let sums n = let rec a = Array2.init (n+1) (n+1) populate and populate k l = lazy if k = 0 then [] else [for x in 1 .. min k l ->> [for xs in a.[k-x, x].Force() -> x :: xs]] a.[n,n].Force()
An important thing to note is that the matrix 'a' and its initialization function are mutually recursive. This kind of code is forbidden in OCaml, but is allowed in F# (a warning is printed, but it can be removed with the flag --no-warn 40). This code is also interesting because it is a pure function (the OCaml equivalent would probably mutate some matrix cells).
Of course, this was just an example. There are several other ways to get laziness. For more details, have a look at these F# modules: Lazy, Seq (IEnumerable) and LazyList.