5
\$\begingroup\$

I'm quite new to Monads and I tried add function call counting to the Ackermann function code. The goal was simplicity, not performance. I want to have code review on the ackCount function.

module AckermannPeterWrite where

import Data.Monoid
import Control.Monad.Writer (Writer, tell, runWriter)

ackCount :: Int -> Int -> Writer (Sum Int) Int
ackCount m n
  | m == 0 = do
            tell (Sum 1)
            return $ n + 1
  | (m > 0) && (n == 0) = do
            tell (Sum 1)
            ackCount (m-1) 1
  | (m > 0) && (n > 0)  = do
            tell (Sum 1)
            let (secondArg, count) = runWriter $ (ackCount m (n-1))
            tell (Sum $ getSum count)
            ackCount (m-1) secondArg

ackCountMain :: Int -> Int -> String
ackCountMain m n = do
    let (result, count) = runWriter $ ackCount m n
    "A(" ++ show m ++ ", " ++ show n ++ ") == " ++ show result ++ ",         " ++ show (getSum count) ++ " function calls"

main :: IO ()
main = do
   putStrLn $ ackCountMain 0 77
   putStrLn $ ackCountMain 0 9
   putStrLn $ ackCountMain 1 9
   putStrLn $ ackCountMain 2 9
   putStrLn $ ackCountMain 3 6

Bonus. A code that gives the same result without monads.

ackCounter :: (Int, Int) -> (Int, Int) -> (Int, Int)
ackCounter (m, sm) (n, sn)
  | m == 0              = (n + 1, sm+sn+1)
  | (m > 0) && (n == 0) = let (res, s) = ackCounter (m-1, 0) (1, 0) in (res, s+sm+sn+1)
  | (m > 0) && (n > 0)  = 
                let (res, s) = ackCounter (m-1, 0) (ackCounter (m, 0) (n-1, 0))
                in (res, s+sm+sn+1)

ackC :: Int -> Int -> (Int, Int)
ackC m n = ackCounter (m, 0) (n, 0)
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

The first thing that jumps out is these lines:

            let (secondArg, count) = runWriter $ ackCount m (n-1)
            tell (Sum $ getSum count)

You're not really using the monad you're using; the whole point is for the accumulation to happen in the background:

            secondArg <- ackCount m (n-1)

Other than that, it's mostly good!

It's a good idea to make your functions total, even if that means including an
| otherwise = error "message" clause. Alternately, you can avoid all your < 0 by retyping your function in terms of Naturals. Unfortunately, there's no first-class Natural data-type in Haskell, I found two options: natural-numbers and naturals, each of which deals with the problems in different ways. (See also)

Finally, with a little reorganization, you can avoid repeating the call to tell $ Sum 1 for every case.

This tests as correct for small values :)

ackNew :: Natural -> Natural -> Writer (Sum Natural) Natural
ackNew m n = do tell $ Sum 1
                case (m, n) of
                  (0, _) -> return $ n + 1
                  (_, 0) -> ackNew (m - 1) 1
                  _      -> do secondArg <- ackNew m (n - 1)
                               ackNew (m - 1) secondArg
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Haskell has had Numeric.Natural since base-4.8.0.0 in 2015. \$\endgroup\$
    – bisserlis
    Mar 18 at 18:23
  • \$\begingroup\$ You're right! Sorry I failed to find it. The documentation at Hackage raises more questions than it answers, but it seems to work in my code, changing nothing but the import. \$\endgroup\$ Mar 18 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.