On key-feature in Haskell is it’s laziness, meaning that it does it’s evaluations in normal-order (an expression is evaluated when the value is needed). F# on the other hand uses applicative evaluation (for example: parameters to a function are evaluated before the function is called – so not the expressions but their values are passed).
Normally this is fine and there is no problem, but if you want to work with infinite lists things are getting interesting.
Look at this example in Haskell:
let natN = [0..] let posN = foldr (\ a s -> (a+1):s) [] natN
It creates the natural numbers (starting at 0) – a infinite list natN and uses a right-fold to just increment each value by 1 (getting the positive natural numbers) – aside from the fact that this is a rather stupid example it shows that – being lazy – Haskell has no problem folding infinite lists under certain circumstances.
This article tries to explain how you could do something similar in F#, introducing the nice lazy-computation syntax on the go.
Defining a lazy-list type
So let’s start by introducing our own lazy-list – as each list those can be either empty or can be a “con” – a pair of a value and the rest of the list (another lazy-list) but in our case the rest or tail should be lazy (i.e. only constructed on demand). You could either use functions of type unit –> ‘a for the laziness, or – as I choose – use the lazy computations F# comes bundled with:
type LazyList<'a> =
| Empty
| Cons of 'a * Lazy<LazyList<'a>>
with
member l.Head =
match l with
| Cons (h, _) -> h
| Empty -> failwith "empty list"
member l.Tail =
match l with
| Cons (_, t) -> t.Force()
| Empty -> failwith "empty list"
As you can see I implemented two simple properties to get to the Head/Tail part of the list.
Maybe you haven’t seen the lazy syntax yet. It’s very simple: if you wrap a expression inside a lazy( … ) F# won’t evaluate the expression till you call .Force() on the resulting value. Force() will return the evaluated value and even memoize it so that it’s only computed once – nice.
The basics
Of course you should provide the common primitives, namely singleton, cons, map and iter for this list, and it’s almost a no-brainer (“let the types guide you…”):
module LazyList =
let single a = Cons (a, lazy ( Empty ))
let cons (a : 'a) (l : LazyList<'a>) = Cons (a, lazy ( l ))
let rec map (f : 'a -> 'b) (l : LazyList<'a>) : LazyList<'b> =
match l with
| Empty -> Empty
| Cons (a, t) -> Cons (f a, lazy (map f (t.Force())))
let rec iter (f : 'a -> unit) (l : LazyList<'a>) : unit =
match l with
| Empty -> ()
| Cons (a, t) -> f a iter f (t.Force())
Ok – the lazy/force and it’s parentheses somewhat clutter the code (you certainly could improve here) but I think its succinct enough.
To really do something similar with a infinite list I need take too (well iter endlessly… well):
module LazyList =
let rec take nr (l : LazyList<'a>) : LazyList<'a> =
match l with
| Empty -> Empty
| Cons (a, t) ->
if nr = 0 then Empty
else Cons (a, lazy (take (nr-1) (t.Force()))) [/sourcecode
Unfolding the naturals
So how to we get the infinite naturals in the first place? Well this is what unfold is for:
module LazyList =
let rec unfold (f : 's -> ('a*'s) option) (init : 's) : LazyList<'a> =
match f init with
| None -> Empty
| Some (a, s) -> Cons (a, lazy ( unfold f s))
with this you can define the naturals by calling
let natNumbers = LazyList.unfold (fun n -> Some (n, n+1)) 0
Defining the right-fold
This is somewhat more tricky as we have to simulate Haskell’s laziness in just the right place. If you implement foldr the usual way:
let rec foldr' (f : 'a -> 's -> 's) (init : 's) (l : LazyList<'a>) : 's = match l with | Empty -> init | Cons (a, t) -> f a (foldr' f init (t.Force()))
you get the problem that F# begins to evaluate the current state for the call of the fold function f (in the Cons-case) and this will get you a nice stack-overflow exception in no time.
So we have to introduce laziness here:
let rec foldr (f : 'a -> Lazy<'s> -> 's) (init : 's) (l : LazyList<'a>) : 's = match l with | Empty -> init | Cons (a, t) -> f a (lazy (foldr f init (t.Force())))
That’s it – now we can to the Haskell equivalent:
let posNatNumbers = LazyList.foldr (fun n l -> Cons ((n+1), l)) Empty natNumbers posNatNumbers |> LazyList.take 20 |> LazyList.iter (printf "%d, ")
giving us the desired output:
> posNatNumbers |> LazyList.take 20 |> LazyList.iter (printf "%d, ");; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, val it: unit = ()
Disclaimer:
This is not meant to be production code or performance-optimized but I think it shows that there is a lot more to F# than you would expect but just toying around with seqs and lists.
and 
we already 
is in the range 
– and we call this the remainder of dividing 
so 
.
.
I should make sure that all works as it should – here is the test validating the second version for those special occasions:
