SimonK77 <simonkaltenbacher <at> googlemail.com> writes: > as Haskell uses the Lazy Evaluation reduction policy also known as Outermost Graph Reduction, I was wondering if the following simple implementation of the Fibonacci sequence would result in linear runtime behaviour. > > fib :: Integer -> Integer > fib 0 = 0 > fib 1 = 1 > fib n = fib (n - 2) + fib (n - 1) > > Is the following reduction sequence realistic, or am I admitting to much intelligence to the Haskell Compiler?
You are, as easily seen when you try to calculate (fib 30). A version that works: import Data.MemoTrie fib :: Integer -> Integer fib = memo \n -> case n of 0 -> 0 1 -> 1 n -> fib (n-1) + fib (n-2) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe