MonadMemo で フィボナッチ数列

λカ娘（算）の田中さんの記事を読んで，練習のために書いてみました．

fib.hs

{-# LANGUAGE FlexibleContexts #-}
import Control.Applicative
import Control.Monad.Memo

-- cabal install monad-memo

fib :: (MonadMemo Int Integer m, Applicative m) => Int -> m Integer
fib 0 = return 1
fib 1 = return 1
fib n = (+) <$> memo fib (n-1) <*> memo fib (n-2)

GHCi での使用例

Prelude> :l fib.hs
[1 of 1] Compiling Main             ( fib.hs, interpreted )
Ok, modules loaded: Main.

*Main> startEvalMemo . fib $ 0
1
*Main> startEvalMemo . fib $ 1
1
*Main> startEvalMemo . fib $ 10
89
*Main> startEvalMemo . fib $ 100
573147844013817084101
*Main> startEvalMemo . fib $ 1000
70330367711422815821835254877183549770181269836358732742604905087154537118196933
57974224949456261173348775044924176599108818636326545022364710601205337412127386
7339111198139373125598767690091902245245323403501
*Main> startEvalMemo . fib $ 10000
54438373113565281338734260993750380135389184554695967026247715841208582865622349
01708305154793896054117382267597802631738435958475111624143917470264295916992558
63341179060630480897935314761084662590727593678991506779600883065979666419658249
37721800381441158841042480997984696487375337180028163763317781927941101369262750
97950980071359671802381471066991264421477525447858767456896380800296226513311135
99297627266794414001015758000435107774659358053625024617079180592264146790056907
52321895868142367849593880756423483754386342639635970733756260098962462668746112
04173981940487506244370986865431562684718619562014612664223271181504036701882520
53148458758171935335298278378003519025292395178366894676619179538847124410284639
35449484614450778762529520961887597272889220768537396475869543159172434537193611
26374392633731300589616724805173798630636811500308839674958710261952463135244749
95052041983051871683216232838597946272459197714546282183996957892237989121994317
75469705216131081096559950638297261253848242007897109054754028438149611930465061
86617012298328896435273375079278606944476185352514442107792804597990456129812942
38091560550330323389196091622366987599227829231918966880177185755555209946533201
28446502371153715141749290913104897203455577507196645425232862022019506091483585
22388271101670843305116994211577515125551025165593188816404834412955703882547752
11115773957801158683970726025656148249564605387002803313118614853998053970315557
27529693399586079850381581446276433858828529535803424850845426446471681531001533
18047956743639681565332615250957112748041192819602214884914828438912417852017450
73055389287178579235094177433833315068982393544219888054293324403711948672155435
76548565499134519271098919802665184564927827827212957649240235507595558205647569
36539487331765900020637312657064350970948264971003873351747771340331902810557566
79317894700241188030946040343629534719974613922747915497303564126330742308240519
99996101549784667340458326852960388301120765629245998136251652347093963049734046
44510636530416363082366924225776146828846179184322479343440607991788336067684671
1185597501
*Main>

すべて一瞬で計算できました．