beginner's questions - fix f

Lennart Augustsson
Tue, 24 Jul 2001 15:18:54 +0200

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