How to count the number of times a function was called, the FP way

Question

I am currently working through SICP with Haskell. Exercise 1.15 asks how many times a function is called. The idea is probably that you should use the substitution method, but I would like to know how to do so in code.

In an imperative language one can keep a global variable and increment it every time the function is called. But how would you go about it in Haskell (or the pure functional way)?

Answer 1

You can use the Writer monad to accomplish this, provided that all of the calls to the function in question can be grouped together into a do block:

import Control.Monad.Writer

myFunc :: Int -> Int -> Writer (Sum Int) Int
myFunc a b = tell (Sum 1) >> return (a + b)

callMyFunc :: ((Int, Int, Int), Sum Int)
callMyFunc = runWriter $ do a <- myFunc 2 3
                            b <- myFunc 8 7
                            c <- myFunc 3 5
                            return (a, b, c)

main = putStrLn $
    "myFunc was called "
        ++ show (getSum $ snd callMyFunc)
        ++ " times and produced "
        ++ show (fst callMyFunc)

Which outputs:

myFunc was called 3 times and produced (5,15,8)

Answer 2

It sounds to me like you need to have some kind of counter regardless of whether you go with a functional or a non-functional way. In Haskell, you could use the State Monad to keep track of the state:

import Control.Monad.State

someFunc x = do
    num <- get
    put (num + 1)
    return $ x * x

runSomeFuncs = do
    someFunc 1
    someFunc 2
    someFunc 3

main = do
    let (res, state) = runState runSomeFuncs 0
    putStrLn ("result: " ++ (show res))
    putStrLn ("# of calls: " ++ show state)

Here, you want to keep track of how many times someFunc got called, so we pass an integer in as the state and increment the integer every time the function gets called by using:

num <- get
put (num + 1)

and then increment it by 1 and put it back. If you run this script, it should print

result: 9
# of calls: 3