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)
So let's run it with Y
((y fs) 5)
or something larger
((y fs) 10)
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)
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.