## A lazy example

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.