関数型プログラミングの基礎 再帰関数の記述 効率よくフィボナッチ数を計算する方法
入門Haskellプログラミング (Will Kurt(著)、株式会社クイープ(監修、翻訳)、翔泳社)のUNIT1(関数型プログラミングの基礎)、LESSON8(再帰関数の記述)、8.5(練習問題)Q8-2の解答を求めてみる。
コード
fastFib :: (Eq t1, Num t1, Num t2) => t2 -> t2 -> t1 -> t2
fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib n1 n2 3 = n1 + n2
fastFib n1 n2 counter = fastFib n2 (n1 + n2) (counter - 1)
main :: IO ()
main = do
mapM_ (print . fastFib 1 1) $ [0 .. 10] ++ [1000]
入出力結果(Terminal, Zsh)
% runghc sample2.hs
0
1
1
2
3
5
8
13
21
34
55
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
%