Как рассчитать, сколько рекурсивных вызовов произошло в этой функции Haskell?

Question

Я пытался понять это на пару часов. Мне нужно вычислить, сколько рекурсивных вызовов произошло с помощью определенной функции:

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 

Большое спасибо заранее

Answer 1

Вы любите функциональное программирование? Вам нравится императивное программирование? Почему бы не так! Вот рекурсивный-императивный способ подсчета глубины рекурсии.

{-# 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) 

Answer 2

Для получения списка с n элементами, есть n-1 рекурсивные вызовы. Чтобы было легче видеть, мы немного перепишем функцию. (Мы можем игнорировать пустой список для этого.)

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

Рекурсивный вызов сделан, когда хвост аргумент не является пустым. (Обратите внимание, что функция, которая была определена для пустого списка, а также сделать бы n рекурсивные вызовы в списке с n элементов.)

Мы можем расширить вызов списка из 3-позиционным, например:

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 

Answer 3

вы можете переписать функцию, чтобы нести информацию о глубине рекурсии в дополнительный аргумент и возвращает его в качестве второй (или первой, если вы так предпочитаете) элемент кортежа:

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) 

Тогда вы можете позвонить с maximum' lst 0 или maximum' lst 1 в зависимости от того, хотите ли вы, чтобы первый вызов считался уровнем рекурсии.

Это может быть сделано с любой рекурсивной функцией, но это, вероятно, не обязательно в вашем случае. Как писал чепнер, ответ известен без дополнительных вычислений.

Answer 4

Это экскурс по Michail 's и user2297560' s ответы.

Что делать, если вместо того, чтобы переписывать функцию с нуля, чтобы добавить функцию отслеживания, мы можем каким-то образом использовать оригинальную реализацию и «инструмент»?

Мы могли бы написать базовую функцию, которая

• Is монадическая, но полиморфный на монады.
• Определяется с помощью анонимной рекурсии с помощью fix.

Например:

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) 

И тогда инструмент это, как это, повторное использование оригинального логика:

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 

Но возможно определение функции, как «монадическая по умолчанию» не слишком практично ,