infinite lazy-lists and folding them in f#

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 “cons” – 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.