Re: beginner's questions - fix f

Marcin 'Qrczak' Kowalczyk wrote:

BTW, a better definition than fix f = f (fix f) is fix f = let x = f x in x because it increases sharing, avoiding recomputation.

The latter definition is more likely to give you sharing, but Haskell gives you no such guarantees. There are also implementations that give you sharing for the first definition.

You can define fix without recursion in a typeless lambda calculus:

fix f = (\x -> f (x x)) (\x -> f (x x))

and this can even be stretched to fit Haskell's type system by smart use of algebraic types.

But those algebraic types are recursive! -- Lennart