Difference between revisions of "The Fibonacci sequence"
Jump to navigation
Jump to search
m (added unfoldr version, removed so-called "fix point" solution) |
|||
Line 50: | Line 50: | ||
main = getArgs >>= mapM_ (print . fib . read) |
main = getArgs >>= mapM_ (print . fib . read) |
||
</haskell> |
</haskell> |
||
+ | |||
+ | == See also == |
||
+ | |||
+ | Discussion at haskell cafe: |
||
+ | |||
+ | http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 |
||
[[Category:Code]] |
[[Category:Code]] |
Revision as of 06:43, 20 February 2007
Implementing the fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
Naive solution
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Canonical zipWith implementation
fib = 1 : 1 : zipWith (+) fib (tail fib)
With scanl
fib = fix ((1:) . scanl (+) 1)
With unfoldr
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
Fastest Fib in the West
This was contributed by wli
import System.Environment
import Data.List
fib n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
where
unfoldl f x = case f x of
Nothing -> []
Just (u, v) -> unfoldl f v ++ [u]
divs 0 = Nothing
divs k = Just (uncurry (flip (,)) (k `divMod` 2))
fib' (f, g) p
| p = (f*(f+2*g), f^2 + g^2)
| otherwise = (f^2+g^2, g*(2*f-g))
main = getArgs >>= mapM_ (print . fib . read)
See also
Discussion at haskell cafe:
http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623