How to calculate how many recursive calls happened

问题:

I've been trying to figure this out for a couple of hours now. I need to calculate how many recursive calls happened using a certain function:

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs  

Many thanks in advance

回答1:

Do you love functional programming? Do you love imperative programming? Why not have both! Here's a recursive-imperative way to count the recursion depth.

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.State

maximumWithCount :: (Ord a, MonadState Int m) => [a] -> m a
maximumWithCount xs = case xs of
  [] -> error "empty list"
  [x] -> return x
  (x:xs) -> do
    modify (+1)  -- increment the counter because we're recursing!
    y <- maximumWithCount xs
    return $ max x y

λ runState (maximumWithCount [1,2,3,4,5,4,3,2,1]) 0
(5,8)

回答2:

You can rewrite your function to carry information about recursion depth in an extra argument, and return it as second (or first, if you so prefer) element of a tuple:

maximum' :: (Ord a) => [a] -> Int -> (a, Int)
maximum' [] _ = error "maximum of empty list"  
maximum' [x] n = (x, n)
maximum' (x:xs) n   
    | x > fst maxTail = (x, snd maxTail)
    | otherwise = maxTail  
    where maxTail = maximum' xs (n + 1)

Then you can call the function with maximum' lst 0 or maximum' lst 1 depending on whether or not you want the first call to count as a recursion level.

It can be done with any recursive function, but it's probably not necessary in your case. As chepner wrote, the answer is known without extra computations.

回答3:

For a list with n elements, there are n-1 recursive calls. To make it easier to see, we'll rewrite the function slightly. (We can ignore empty list for this.)

maximum' [x] = x
maximum' (x:xs) = if x > maxTail then x else maxTail
                  where maxTail = maximum' xs

A recursive call is made when the tail of the argument is not empty. (Note that a function that was defined for the empty list as well would make n recursive calls on a list with n items.)

We can expand a call to a 3-item list, for example:

maximum' [1,2,3] = if 1 > maxTail then 1 else maxTail where maxTail = maximum' [2,3]
 maximum' [2,3] = if 2 > maxTail then 2 else maxTail where maxTail = maximum' [3]
  maximum' [3] = 3

回答4:

This is a digression on Michail's and user2297560's answers.

What if, instead of rewriting the function from scratch to add tracking functionality, we could reuse the original implementation and "instrument" it in some way?

We could write a base function that

• Is monadic, but polymorphic on the monad.
• Is defined using anonymous recursion, with the help of fix.

For example:

import Data.Function(fix)
import Data.Functor.Identity

maximumAux :: (Monad m,Ord a) 
           => ([a] -> m a) 
           ->  [a] -> m a  
maximumAux _ [] = error "maximum of empty list"  
maximumAux _ [x] = return x  
maximumAux recurse (x:xs) = 
    do maxTail <- recurse xs
       return (max x maxTail)

maximumPure :: Ord a => [a] -> a
maximumPure as = runIdentity (fix maximumAux as)

And then instrument it like this, reusing the original logic:

maximumInstrumented :: (Ord a, Show a) => [a] -> IO a
maximumInstrumented = fix (instrument maximumAux)
    where
    instrument auxf iorecurse as = 
        do print $ "starting call with params " ++ show as
           a <- auxf iorecurse as
           print $ "ending call with value" ++ show a
           return a

But perhaps defining functions as "monadic by default" isn't too practical.