(λblog. blog blog) (λblog. blog blog)

diverging since 2008

Musings on fix

2008-06-26 18:05

Today's small haskell satori: the least fixpoint operator

> fix f = let x = f x in x

(which seemed like dark magic when I first saw it) could be written a bit more intuitively as

> fix' f = let f' = f . f' in f' undefined

This captures the intuition that fix just applies a function iteratively to undefined (i.e. bottom, _|_). Actually we could use any value in the place of undefined but that would restrict the type of fix'. You see, the only reason f' really needs to be applied to anything is to appease the typechecker.

Of course the original (Haskell98) definition is more elegant and probably has better sharing characteristics too.

Update 2008-07-11: found some related musings on haskell-cafe. See also the reply