ユークリッド互除法の計算過程をControl.Monad.Writerで

ユークリッド互除法の計算問題をしていたのですが、途中計算が答えになかったので、自分で作りました。

ソースコード

gcd.hs

import Control.Monad.Writer
gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
   |b == 0    = do
                  tell["= " ++ show a]
                  return(a)
   |otherwise = do
                  let nb = a `mod` b 
                      expr = "gcd(" ++ show(b) ++ ", " ++ show(nb) ++ ")"
                      msg  = show(a) ++ " = " ++ show(b) ++ " * " ++ show(a `div` b) ++ " + " ++ show(nb)
                      in (tell["= " ++ expr ++ " [" ++  msg ++ "]"])
                  gcd' b (a `mod` b)

show_gcd :: (Int, Int) -> IO ()
show_gcd (a, b) = mapM_ putStrLn $ snd $ runWriter (gcd' a b)

fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

実行結果の例