Evaluation mit Fixpunktkombinator

Dateiinhalt

fix :: (t -> t) -> t
fix = \f -> let x = f x in x


fix succ --> (let x = f x in x)[succ/f]
         --> let x = succ x in x
         --> x
         --> succ x
         --> succ (succ x)
         --> succ (succ (succ x))


fix fib 3 --> ((\f -> let x = f x in x) fib) 3
          --> (let x = fib x in x) 3
          --> x 3
          --> fib x 3
          --> (\f n -> if n<=1 then 1 else (f (n-1)) + (f (n-2))) x 3
          --> if 3<=1 then 1 else (x (3-1)) + (x (3-2))
          --> (x (3-1)) + (x (3-2))
          --> (x 2) + (x 1)
          --> (fib x 2) + (fib x 1)
          --> .. + ((\f n -> if n<=1 then 1 else (f (n-1)) + (f (n-2))) x 1)
          --> .. + (if 1<=1 then 1 else (x (1-1)) + (x (1-2)))
          --> .. + 1
          --> (fib x 2) + 1
          --> ((\f n -> if n<=1 then 1 else (f (n-1)) + (f (n-2))) x 2) + 1
          --> (if 2<=1 then 1 else (x (2-1)) + (x (2-2))) + 1
          --> ((x 1) + (x 0)) + 1
          --> ((fib x 1) + (fib x 0)) + 1
          ----> 1 + 1 + 1 = 3 
==================
Speicher: 

fix = \f -> let x = f x in x
fib = \f n -> if n<=1 then 1 else (f (n-1)) + (f (n-2))
x = fib x