[Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)

Matthew Brecknell haskell at brecknell.org
Mon Mar 19 21:27:21 EDT 2007


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.



More information about the Haskell-Cafe mailing list