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 |

Pingback: Dew Drop – December 16, 2011 (#1,221) | Alvin Ashcraft's Morning Dew()

Pingback: Interesting .NET Links - December 17 , 2011 | Tech Blog()