関数型プログラミングの基礎 再帰関数の記述 フィボナッチ数を効率よく計算する関数の実装
入門Haskellプログラミング (Will Kurt(著)、株式会社クイープ(監修、翻訳)、翔泳社)のUNIT1(関数型プログラミングの基礎)、LESSON 8(再帰関数の記述)、8.5(練習問題)Q8-2の解答を求めてみる。
コード
lesson/app/Main.hs
module Main where
import Lib (fastFibN)
main :: IO ()
main = do
mapM_ print $ fastFibN <$> [1 .. 10]
mapM_ print $ fastFibN <$> [100, 200 .. 1000]
lesson/src/Lib.hs
module Lib
( fastFibN,
)
where
fastFib :: Integer -> Integer -> Integer -> Integer
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)
-- 部分的用
fastFibN :: Integer -> Integer
fastFibN = fastFib 1 1
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)
入出力結果(Terminal, Zsh)
% stack build
lesson> build (lib + exe)
Preprocessing library for lesson-0.1.0.0..
Building library for lesson-0.1.0.0..
[2 of 2] Compiling Lib
Preprocessing executable 'lesson-exe' for lesson-0.1.0.0..
Building executable 'lesson-exe' for lesson-0.1.0.0..
Linking .stack-work/dist/x86_64-osx/Cabal-3.4.1.0/build/lesson-exe/lesson-exe ...
lesson> copy/register
Installing library in /Users/…/lesson/.stack-work/install/x86_64-osx/b6e8c918185b27e9dcbc52db0653ed10d7a4ac8a88584523c7314e6b50554430/9.0.2/lib/x86_64-osx-ghc-9.0.2/lesson-0.1.0.0-CIOIkpTgcfQI9akDJnwnSd
Installing executable lesson-exe in /Users/…/lesson/.stack-work/install/x86_64-osx/b6e8c918185b27e9dcbc52db0653ed10d7a4ac8a88584523c7314e6b50554430/9.0.2/bin
Registering library for lesson-0.1.0.0..
% stack exec lesson-exe
1
1
2
3
5
8
13
21
34
55
354224848179261915075
280571172992510140037611932413038677189525
222232244629420445529739893461909967206666939096499764990979600
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200
87470814955752846203978413017571327342367240967697381074230432592527501911290377655628227150878427331693193369109193672330777527943718169105124275
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
% stack ghci
Using main module: 1. Package `lesson' component lesson:exe:lesson-exe with main-is file: /Users/…/lesson/app/Main.hs
The following GHC options are incompatible with GHCi and have not been passed to it: -threaded
Configuring GHCi with the following packages: lesson
* * * * * * * *
Warning: Multiple files use the same module name:
* Paths_lesson found at the following paths
* /Users/…/lesson/.stack-work/dist/x86_64-osx/Cabal-3.4.1.0/build/autogen/Paths_lesson.hs (lesson:lib)
* /Users/…/lesson/.stack-work/dist/x86_64-osx/Cabal-3.4.1.0/build/lesson-exe/autogen/Paths_lesson.hs (lesson:exe:lesson-exe)
* * * * * * * *
GHCi, version 9.0.2: 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 /Users/…/.ghc/ghci.conf
[1 of 3] Compiling Lib ( /Users/…/lesson/src/Lib.hs, interpreted )
[2 of 3] Compiling Main ( /Users/…/lesson/app/Main.hs, interpreted )
[3 of 3] Compiling Paths_lesson ( /Users/…/lesson/.stack-work/dist/x86_64-osx/Cabal-3.4.1.0/build/autogen/Paths_lesson.hs, interpreted )
Ok, three modules loaded.
Loaded GHCi configuration from /private/var/folders/wj/52wjq8dn0fj1qltsnx3xxpnh0000gn/T/haskell-stack-ghci/3d30ba19/ghci-script
*Main Lib Paths_lesson
λ> fastFibN 10
55
it :: Integer
(0.02 secs, 500,856 bytes)
*Main Lib Paths_lesson
λ> fib 10
<interactive>:2:1: error: Variable not in scope: fib :: t0 -> t
(0.01 secs,)
*Main Lib Paths_lesson
λ> :load Lib
[1 of 1] Compiling Lib ( /Users/…/lesson/src/Lib.hs, interpreted )
Ok, one module loaded.
(0.01 secs,)
*Lib
λ> fib 10
55
it :: Integer
(0.01 secs, 528,296 bytes)
*Lib
λ> fastFibN 100
354224848179261915075
it :: Integer
(0.01 secs, 535,936 bytes)
*Lib
λ> fib 100
^CInterrupted.
*Lib
λ> fastFib 20
<interactive>:7:1: error:
• No instance for (Show (Integer -> Integer -> Integer))
arising from a use of ‘print’
(maybe you haven't applied a function to enough arguments?)
• In a stmt of an interactive GHCi command: print it
(0.00 secs,)
*Lib
λ> fastFibN 20
6765
it :: Integer
(0.01 secs, 500,784 bytes)
*Lib
λ> fib 20
6765
it :: Integer
(0.03 secs, 4,653,032 bytes)
*Lib
λ> fib 30
832040
it :: Integer
(1.58 secs, 511,779,760 bytes)
*Lib
λ> fastFib 30
<interactive>:11:1: error:
• No instance for (Show (Integer -> Integer -> Integer))
arising from a use of ‘print’
(maybe you haven't applied a function to enough arguments?)
• In a stmt of an interactive GHCi command: print it
(0.00 secs,)
*Lib
λ> fastFib
fastFib fastFibN
λ> fastFibN 30
832040
it :: Integer
(0.01 secs, 505,008 bytes)
*Lib
λ> fastFibN 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
it :: Integer
(0.02 secs, 1,024,680 bytes)
*Lib
λ> :quit
Leaving GHCi.
%