More Y

Y is trivial to write in Haskell. The wikipedia entry on fixed point combinators shows that via some reduction operations you end up with a simple definition of: Y g = g (Y g)

To write this in Haskell is really straightforward:

let y g = g (y g)

Yes. Just that easy.

The type of the function y is now:

y :: (t -> t) -> t

That is to say y is a function, that takes a function that takes a type "t" and returns a type "t" and returns a type "t".

This form of type is consistent with being a fixed point calculator for functions. (see the top of that wikipedia article linked earlier for an explanation of a fixed point of a function).

Can this be used to compute a fibonacci function from a fibonacci step? You bet!

let fs = (\n -> (\x -> if x =< 1 then 1 else (n (x -1)) + (n (x - 2))))

Now just like before, in scheme, we can use this to try to manually unroll recursion via the "n" argument which is a function to be run next.

((fs (fs (fs (fs (fs undefined))))) 5)
8

So let's run it with Y

((y fs) 5)
8

or something larger

((y fs) 10)
89

Strictly speaking, writing trace in a pure functional language is not allowed, unless you break the rules. Debug.Trace.trace lets you do this, and since I'm tracing anyway...

let tracestep label = (\f -> (\g -> (\n -> let res = (f g) n in (Debug.Trace.trace (label ++ " " ++ (show res)) res))))

Can I still compose this with "y"?

((y (tracestep "fib" fs)) 5)
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
8

Yes!

I was going to write about memoizing this as in the Scheme example, but I'm quite tired, and my wife and I watch So You Think You Can Dance, so that's what I'm going to do instead.