Month / December 2011

by Carsten König

toying with lazy sequences and the fixed-point combinator in F#

I recently watched this great cast from Graham Hutton on Channel 9: How to be more productive. Right at the beginning he shows us another application of the fixed-point combinator and this got me into the “Haskell/Lazy love”-mode again. So I (once again) toyed around with F# to get a similar behavior (and the combinator) working.

I know there is some inbuilt lazy-stuff but for now I will choose to build up from scratch, as I think it’s easier to get this way, so let’s start by defining a lazy-type and a lazy sequence.

The lazy-type itself will be nothing more than a function with no arguments that returns a value at call:

type 'a Lazy = unit -> 'a

As I need to wrap up a value into such a expression and as often need to evaluate it let’s get some shortcuts for this:

    let L x = fun () -> x
    let V x = x()

And of course I will need a “map” function for those lazy values – so let’s implement this as an operator to shorten up the stuff even more:

    let ( < % ) (f : 'a -> 'b) (a : 'a Lazy) : 'b Lazy =
        a >> f

(Please not: I had to insert spaces in there to prevent the code-plugin from removing the “<%”) I think it’s obvious what this does: it’s the fmap for the functor “Lazy”.

Now the part for the lazy-sequence is the old idea of getting one value and the rest of the sequence as lazy-values:

type 'a LSeq = | LSeq of 'a Lazy * 'a LSeq Lazy

Here are a bunch of helper functions to play with this:

    let rec lMap (f : 'a -> 'b) (l : 'a LSeq) : 'b LSeq =
        match l with
        | LSeq (x, t) -> LSeq (f  < % x, t  > > lMap f)

    let rec repeat (x : 'a) : 'a LSeq = LSeq (L x, fun () -> repeat x)

    let create (cf : 's -> 'a Lazy*'s) (seed : 's) : 'a LSeq =
        let rec create (s : 's) =
            match cf s with
            | (x, n) -> LSeq (x, fun () -> create n)
        create seed

    let rec toSeq lseq =
        seq {
            match lseq with
            | LSeq (x, t) -> yield x()
                             yield! toSeq (t())
        }

And some samples:

> let onlyOnes = repeat 1;;

val onlyOnes : int LSeq = LSeq (<fun:repeat@24>,<fun:repeat@24-1>)

> onlyOnes |> toSeq;;
val it : seq<int> = seq [1; 1; 1; 1; ...]
> let naturals = create (fun n -> (L n, n+1)) 0;;

val naturals : int LSeq = LSeq (<fun:naturals@12-3>,<fun:create@29-1>)

> naturals |> toSeq;;
val it : seq<int> = seq [0; 1; 2; 3; ...]
> let evenNaturals = naturals |> lMap (fun n -> n*2);;

val evenNaturals : int LSeq = LSeq (<fun:op_LessPercent@13>,<fun:lMap@22>)

> evenNaturals |> toSeq;;
val it : seq<int> = seq [0; 2; 4; 6; ...]
>

 

Fixed-point operator in F#

Of course you could write this just as in Haskell (and F# will understand):

> let rec fix f = f (fix f);;

val fix : ('a -> 'a) -> 'a

The problem is – without Haskell’s inbuilt laziness – you will see this:

> let rec fix f = f (fix f);;

val fix : ('a -> 'a) -> 'a

> let f l = L <| LSeq 1)L 1), l);;

val f : int LSeq Lazy -> (unit -> int LSeq)

> fix f;;

Process is terminated due to StackOverflowException.


let’s ...continue()

yeah it’s ugly but it finally yields the desired result:

> let ones = fix f |> V;;

val ones : int LSeq = LSeq (<fun:f@3-2>,<fun:ones@6-1>)

> ones |> toSeq;;
val it : seq<int> = seq [1; 1; 1; 1; ...]

 

If you might wonder what all this noise about fix is about – watch the screencast or try to understand that fix is a way to express recursion in “lambda-calculus-magic” – maybe I will write some more on this topic but for now let’s call it a day.

References   [ + ]

1. ↑ L 1), l);; val f : int LSeq Lazy -> (unit -> int LSeq) > fix f;; Process is terminated due to StackOverflowException.

let’s fix the fix! :

    let rec fix (f : 'a Lazy -> 'a Lazy) : 'a Lazy =
        fun () -> (f (fix f