Laurent Le Brun

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.