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

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:

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.

By Laurent Le Brun, Tuesday 17 July 2007 :: [EN] F# articles :: #11

## Comments

No comments.

## Leave a comment

Comments are closed.