haskell - Haskell - 再帰回数を数える

Question

以下のn番目のフィボナッチ数を計算する簡単な関数があります。

fibonacci :: Integer -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = (fibonacci (n-1) ) + (fibonacci (n-2))

しかし、この関数の再帰回数を数える方法に興味があります。それを行う方法はありますか？

Answer 1

これは、いわゆる Writer モナドsigfpeの のイラストを思い起こさせます。次のように、もう少し体系的に行うことができます。

import Control.Monad.Trans.Writer
import Control.Monad.Trans
import Data.Monoid

fibwriter :: Int -> Writer (Sum Int) Integer
fibwriter 0 = return 0
fibwriter 1 = return 1
fibwriter n =  do a <- fibwriter (n-1)
                  b <- fibwriter (n-2)
                  tell (Sum (2::Int))
                  return (a + b)

次のように使用されます。

*Fib> runWriter $ fibwriter  11
(89,Sum {getSum = 286})

これは同じ定義ですが、追加の再帰の各ペアをログに記録するという「副作用」があります。IO「ナイーブ」定義に関連するすべてのクレイジーな再計算が発生している間に確認したい場合は、副作用を追加することもできます。

fibprint :: Int -> WriterT (Sum Int) IO Integer
fibprint 0 = return 0
fibprint 1 = return 1
fibprint n = do  a <- fibprint (n-1)
                 record a
                 b <- fibprint (n-2)
                 record b
                 return (a + b)
 where  record x = lift (putStr $  ' ' : show x) >> tell (Sum 1)

フィボナッチ 11 の場合、計算が 89 に向かって上昇するにつれて、これはばかげて反復的なショーを示します。

*Fib> runWriterT $ fibprint 11
 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0
 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 1 0 1 1
 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5
 13 34 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1
 3 1 0 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 55
 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0
 1 1 2 5 13 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 21 1 0 1 1
 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5
 13 34(89,Sum {getSum = 286})