W Haskell WikiRekurencja w monadzie istnieje przykład, który ma byćrekurencyjny ogon:

f 0 acc = return (reverse acc)
f n acc = do
    v  <- getLine
    f (n-1) (v : acc)

Podczas gdy imperatywna notacja prowadzi nas do przekonania, że ​​jest rekurencyjna, nie jest wcale taka oczywista (przynajmniej dla mnie). Jeśli odlamy cukierdo dostajemy

f 0 acc = return (reverse acc)
f n acc = getLine >>= \v -> f (n-1) (v : acc)

i przepisanie drugiej linii prowadzi do

f n acc = (>>=) getLine (\v -> f (n-1) (v : acc))

Widzimy tof występuje w drugim argumencie>>=, nie w pozycji rekurencyjnej. Musielibyśmy to zbadaćIOjest>>= uzyskać odpowiedź. Wyraźniewywołanie rekurencyjne jako ostatnia linia w ado blok nie jest wystarczającym warunkiem, aby funkcja była rekurencyjna.

Powiedzmy, że amonada jest rekurencyjna w każdej funkcji rekurencyjnej w tej monadzie zdefiniowanej jako

f = do
    ...
    f ...

lub równoważnie

f ...  =  (...) >>= \x -> f ...

jest rekurencyjny. Moje pytanie brzmi:

Jakie monady są rekurencyjne?Czy istnieje jakaś ogólna zasada, której możemy użyć, aby natychmiast odróżnić monady rekurencyjne ogonowe?

Aktualizacja: Pozwól, że zrobię konkretny kontrprzykład: The[] monada nie jest rekurencyjna ogonowo zgodnie z powyższą definicją. Jeśli tak, to

f 0 acc = acc
f n acc = do
    r <- acc
    f (n - 1) (map (r +) acc)

musiałby być rekurencyjny ogonowo. Jednak odsunięcie drugiej linii prowadzi do

f n acc = acc >>= \r -> f (n - 1) (map (r +) acc)
        = (flip concatMap) acc (\r -> f (n - 1) (map (r +) acc))

Oczywiście nie jest to rekurencja ogonowa i nie można wykonać IMHO. Powodem jest to, że wywołanie rekurencyjne nie jest końcem obliczeń. Jest wykonywany kilka razy, a wyniki są łączone, aby uzyskać ostateczny wynik.