関数型プログラミングの基礎 再帰関数の記述 フィボナッチ数の計算、計算量、効率化
入門Haskellプログラミング (Will Kurt(著)、株式会社クイープ(監修、翻訳)、翔泳社)のUNIT1(関数型プログラミングの基礎)、LESSON 8(再帰関数の記述)、8.5(練習問題)Q8-2の解答を求めてみる。
コード
-- Q8-2
fib :: (Eq a, Num a, Num p) => a -> p
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 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)
myFib :: Integer -> Integer
myFib = fastFib 1 1
入出力結果(Terminal, Zsh)
% ghci
GHCi, version 8.10.4: https://www.haskell.org/ghc/ :? for help
macro 'doc' overwrites builtin command. Use ':def!' to overwrite.
(0.00 secs, 0 bytes)
(0.00 secs, 0 bytes)
Loaded GHCi configuration from /.../.ghc/ghci.conf
Prelude
λ> :load sample2
[1 of 1] Compiling Main ( sample2.hs, interpreted )
Ok, one module loaded.
(0.02 secs,)
*Main
λ> map fib [1..10]
[1,1,2,3,5,8,13,21,34,55]
it :: Num b => [b]
(0.05 secs, 238,496 bytes)
*Main
λ> map myFib [1..10]
[1,1,2,3,5,8,13,21,34,55]
it :: [Integer]
(0.00 secs, 96,408 bytes)
*Main
λ> fib 100
^CInterrupted.
*Main
λ> fib 20
6765
it :: Num p => p
(0.02 secs, 7,729,008 bytes)
*Main
λ> fib 30
832040
it :: Num p => p
(2.48 secs, 943,122,168 bytes)
*Main
λ> myFib 30
832040
it :: Integer
(0.00 secs, 77,040 bytes)
*Main
λ> myFib 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
it :: Integer
(0.00 secs, 820,568 bytes)
*Main
λ> :quit
Leaving GHCi.
%