0
comment
on 12/11/2009 9:05 AM

A noticeable omission in F# standard library is Seq.foldBack, or the famous Haskell foldr. The semantics of foldr is very simple to remember: it replaces the native cons and nil of a list with arbitrary computations:

1
2

    foldr cons nil []     = nil
foldr cons nil (x:xs) = cons x (foldr cons nil xs)

In particular, replacing the native cons and nil with themselves is always equivalent to the original list, e.g. forall x: foldr (:) [] x == x

Surprisingly, the above equation holds for infinite lists as well. This is something important to remember when porting these ideas to F#.

A naive F# translation would use this type:

1

 foldBack : ('T1 -> 'T2 -> 'T2) -> 'T1 -> seq<'T1> -> 'T2

However, by being strict in the second argument, cons will now prematurely force the evaluation of infinite sequences.

Here is a more faithful translation using LazyList from the FSharp.PowerPack.dll:

1
2
3
4
5
6

    /// Implements the lazy right-to-left fold.
let foldBack (f: 'T1 -> Lazy<'T2> -> 'T2) (z: 'T2) (xs: seq<'T1>) : 'T2 =
let rec foldr = function
| LazyList.Nil         -> z
| LazyList.Cons(x, xs) -> f x (lazy (foldr xs))
foldr (LazyList.ofSeq xs)

Now let us test the code to make sure we have been faithful to Haskell in our translation:

1
2
3
4
5
6
7
8

    Seq.FoldBack
(fun x xs -> LazyList.consDelayed x (fun () -> Lazy.force xs))
(LazyList.empty ())
(Seq.initInfinite (fun x -> x))
|> LazyList.toSeq
|> Seq.take 10
|> Seq.toArray
|> printfn "%A"