Bryan Burgers:
On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it.
I don't know of any tutorials that teach how to use fix, but these are some of the pages that helped me on the way towards understanding what it is: http://en.wikipedia.org/wiki/Fixed_point_combinator http://en.wikipedia.org/wiki/Anonymous_recursion In Haskell, it might help to note the equivalence between a and a', b and b', etc, in the following (given appropriate definitions for p, q, r, s, t, etc):
a = fix (\f -> if t then f else r) a' = let f = (if t then f else r) in f
b = fix (\f x -> if t' x then f (s' x) else r' x) p b' = let f x = (if t' x then f (s' x) else r' x) in f p
c = fix (\f x y -> if t'' x y then uncurry f (s'' x y) else r'' x y) p q c' = let f x y = (if t'' x y then uncurry f (s'' x y) else r'' x y) in f p q
etc. The first case is not of much practical use, since each iteration of f must produce the same result, so it must either return immediately (if it doesn't recurse into f) or never (if it does). The other cases can be useful, since the additional arguments can be used by the implementation of f to decide whether or not to recurse. When writing an anonymous function inside an invocation of fix, the main thing to realise is that the first argument of that anonymous function is the anonymous function itself. You can use that argument to make a recursive call to the anonymous function. So you could say it's not really anonymous after all. Of course, you eventually have to return without recursing if you want to avoid an infinite loop.