Rekursion in einer Monade

Question

Ich bin ratlos, Rekursion in einer Monade zu verstehen. Vom haskell.org Wiki ist hier ein Beispiel: rekursiv

main = f 3 

f 0 = return [] 
f n = do v <- getLine 
     vs <- f (n-1) 
     return $! v : vs 

Dieses Programm wird drei Zeilen von der Standardeingabe. Was ich nicht verstehen kann ist, was passiert, wenn man zu f 0 kommt und wie die Rekursion abläuft. Wie wird der Endwert des do-Blocks aufgebaut? Warum wird in der Rekursion die letzte Rückleitung wiederholt aufgerufen? Ich weiß, dass Rückkehr nicht Funktionsrückgabe wie in Imperativsprachen ist, aber ich kann nicht sehen, wie diese Linie wiederholt wird.

Ich bin mir bewusst, dass dies eine rohe Anfänger Frage ist, aber ich bin ratlos.

Answer 1

In diesem speziellen Fall können Sie nur vollständig entfalten. Vielleicht hilft das:

f 3 
= { reduce f (and the subtraction) } 
    do v <- getLine 
    vs <- f 2 
    return $! v : vs 
= { reduce f (and the subtraction) } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- f 1 
       return $! v' : vs' 
    return $! v : vs 
= { reduce f (and the subtraction) } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- do v'' <- getLine 
         vs'' <- f 0 
         return $! v'' : vs'' 
       return $! v' : vs' 
    return $! v : vs 
= { reduce f } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- do v'' <- getLine 
         vs'' <- return [] 
         return $! v'' : vs'' 
       return $! v' : vs' 
    return $! v : vs 
= 
    ... 

An diesem Punkt gibt es keine Rekursion mehr. Wir haben nur Funktionsdefinitionen angewendet. Von hier aus können wir weiter vereinfachen, wenn wir, dass die Monade Gesetze halten annehmen:

... 
= { vs'' <- return [] means that vs'' is [] } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- do v'' <- getLine 
         return $! v'' : [] 
       return $! v' : vs' 
    return $! v : vs 
= { inline the innermost do block } 
    do v <- getLine 
    vs <- do v' <- getLine 
       v'' <- getLine 
       vs' <- return $! v'' : [] 
       return $! v' : vs' 
    return $! v : vs 
= { inline return $! v'' : [] } 
    do v <- getLine 
    vs <- do v' <- getLine 
       v'' <- getLine 
       return $! v' : v'' : [] 
    return $! v : vs 
= { inline the innermost do block } 
    do v <- getLine 
    v' <- getLine 
    v'' <- getLine 
    vs <- return $! v' : v'' : [] 
    return $! v : vs 
= { inline return $! v' : v'' : [] } 
    do v <- getLine 
    v' <- getLine 
    v'' <- getLine 
    return $! v : v' : v'' : [] 

Answer 2

können Sie „pseudo-Kompilierung“/„entspannen“, der monadischen Block, um zu sehen, wie es funktioniert:

f 3 = do v <- getLine 
     vs <- f 2 -- (will return a list with 2 lines from stdin 
     return $! v : vs 
f 2 = do v <- getLine 
     vs <- f 1 -- (will return singleton list with a line from stdin) 
     return $! v : vs 
f 1 = do v <- getLine 
     vs <- f 0 -- (will return an empty list) 
     return $! v : vs 
f 0 = return [] 

Also, es wird getLine 3 mal und dann eine Liste der Linien aufbauen, die erste Zeile wird der erste Wert in der Liste sein.

Jedes Mal, wenn Sie eine return in einem monadischen Ausdruck sehen, setzen Sie einen Wert hinein. Jedes Mal, wenn Sie einen (bind) in einem monadischen Ausdruck sehen, nehmen Sie Werte heraus. Im Fall der IO Monade, Sie setzen immer und nehmen Sie eine einzige der Monade. Im Gegensatz dazu kann die Listen-Monade aufeinanderfolgende Werte "herausnehmen" (binden).