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 |