Wie berechnet man, wie viele rekursive Aufrufe in dieser Haskell-Funktion passiert sind?

Question

Ich habe versucht, das jetzt für ein paar Stunden herauszufinden. Ich brauche zu berechnen, wie viele rekursive Aufrufe passiert eine bestimmte Funktion:

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 

Vielen Dank im Voraus

Answer 1

Liebst du funktionale Programmierung? Liebst du imperative Programmierung? Warum nicht beides haben! Hier ist ein rekursiver Imperativ, um die Rekursionstiefe zu zählen.

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

Eine Liste mit n Elemente gibt es n-1 rekursive Aufrufe. Um es einfacher zu sehen, schreiben wir die Funktion etwas um. (Wir können für diese leere Liste ignorieren.)

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

Ein rekursiven Aufruf gemacht wird, wenn der Schwanz des Arguments nicht leer ist. (Beachten Sie, dass eine Funktion, die für die leere Liste definiert wurde auch n rekursive Aufrufe auf einer Liste mit n Artikeln machen würde.)

Wir können einen Anruf an eine 3-Punkt-Liste erweitern, zum Beispiel:

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

können Sie umschreiben Ihre Funktion Informationen über Rekursionstiefe in einem zusätzlichen Argument zu tragen, und als zweite Rückkehr (oder zuerst, wenn Sie so bevorzugen) Element eines Tupels:

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) 

Dann können Sie rufen die Funktion mit maximum' lst 0 oder maximum' lst 1 abhängig davon, ob der erste Aufruf als Rekursionsstufe gezählt werden soll oder nicht.

Es kann mit jeder rekursiven Funktion gemacht werden, aber es ist wahrscheinlich in Ihrem Fall nicht notwendig. Wie chepner schrieb, ist die Antwort ohne zusätzliche Berechnungen bekannt.

Answer 4

Dies ist ein Exkurs über Michail 's und user2297560' s Antworten.

Was wäre, wenn wir, anstatt die Funktion von Grund auf neu zu schreiben, um Tracking-Funktionalität hinzuzufügen, könnten wir die ursprüngliche Implementierung und "Instrument" in irgendeiner Weise wiederverwenden?

Wir könnten eine Basisfunktion schreiben, die

• monadischen, aber polymorphen auf der Monade.
• Wird mithilfe der anonymen Rekursion mit Hilfe von fix definiert.

Zum Beispiel:

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) 

Und dann Instrument es so, die ursprüngliche Logik Wiederverwendung:

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 

Aber vielleicht funktioniert als "monadischen by default" definiert, ist nicht zu praktisch .