Writerモナドを試してみた

Haskell 30分プログラム

30分プログラム、その670。Writerモナドを試してみました。
前回がReaderモナドだったので、今回はWriterモナドを試してみました。
The Writer monadには、Writerモナドは裏でログをとったりするのに便利だと書いてあったので、関数の呼び出しを記録してみました。

使い方

*Main> runWriter $ fib 10
(55,["fib(10)",
     "fib(9)",
     "fib(8)",
     "fib(7)",
     "fib(6)",
     "fib(5)",
     "fib(4)",
     "fib(3)",
     "fib(2)",
     "fib(2)",
     "fib(3)",
     "fib(2)",
     ....])

とやって、普通のフィボナッチ数の定義が、いかに非効率かに驚く。

そのあと、

*Main> runWriter $ fibi (1,0) 10
(55,["fibi(10)","fibi(9)","fibi(8)",...])

とやって、フィボナッチ数の反復的な定義が、いかに効率的かに驚く。

ソースコード

import Control.Monad.Writer
import Text.Printf

fib :: Int -> Writer [String] Int
fib 0 = return 0
fib 1 = return 1
fib n = do tell [printf "fib(%d)" n]
           a <- fib (n-1)
           b <- fib (n-2)
           return $ a + b

fibi :: (Int,Int) -> Int -> Writer [String] Int
fibi (current,_) 1 = return current
fibi (current,prev) n = do tell [printf "fibi(%d)" n ]
                           fibi (current+prev,current) (n-1)

参考