この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 

感謝をn要素を持つリストについては、事前

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-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 1のように、最初の呼び出しを再帰レベルとしてカウントするかどうかによって異なります。

これは任意の再帰関数で行うことができますが、おそらくあなたの場合は必要ではありません。 chepnerが書いたように、答えは余分な計算なしで分かっています。

Answer 4

これはミハイルさんとuser2297560さんの回答に余談です。

トラッキング機能を追加するために関数をゼロから書き直すのではなく、元の実装を何らかの形で再利用することができますか？

我々は

• はモナドが、モナド上の多型であることの基本機能を書くことができます。
• 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 

しかし、「デフォルトでモナドは」あまりにも実用的ではないとして、おそらく関数を定義します。