Giving these definitions (let is found in Haskell documentation):
fix :: (a -> a) -> a
fix f = let x = f x in x
fact = fix (\f -> \x -> if x <= 1 then x else x * f (x-1))I'll try to explain how fix works.
Let's reduce fact
fact = fix (\f -> \x -> if x <= 1 then x else x * f (x-1)) =
-- by definition of fix
fact = let x = (\f -> \x -> if x <= 1 then x else x * f (x-1)) x in x =
-- by definition of let
fact = G G G G G G G G ... -- A little abuse of notation
where G = (\f -> \x -> if x <= 1 then x else x * f (x-1))Each G is then taken by its predecesor as its first argument f.
Abusing the notation again, let's define 'rec' as the resulting function G G G G G G ...
rec = \x -> if x <= 1 then x else x * rec (x-1)Then finally
fact = recWait... ¿fact == rec?
Well... yes. fix in this case is useful merely because we cannot define a function that has itself in it's body (In Haskell we can, but in other languages we cannot).