遞歸單子

Question

我不知道單子中的遞歸。來自haskell.org的維基是一個例子：

main = f 3 

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

這個程序從標準輸入中遞歸地獲取三行。我無法理解的是，當你到達f 0以及遞歸如何展開時會發生什麼。 do塊的最終值如何構建？爲什麼在遞歸中重複調用最終返回行？我知道返回不是函數返回，如命令式語言，但我不明白這條線是如何重複的。

我知道這是一個原始的初學者問題，但我很難過。

Answer 1

在這種特殊情況下，您可以完全展開。也許這有助於：

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 
= 
    ... 

在這一點上，沒有剩下遞歸。我們所做的只是應用函數定義。 從這裏，我們可以進一步簡化，如果我們假設單子法律成立：

... 
= { 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

可以「僞纂」 /「放鬆」看到單子塊它是如何工作的：

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 [] 

所以，它會getLine 3次，然後建立一個行列表，第一行將是列表中的第一個值。

每當您在monadic表達式中看到return時，就會在其中放入一個值。每當您在單表達式中看到一個<-（綁定）時，就會從中取出值。在monod的IO的情況下，你總是放置並取出一個monad。相反，列表單子可能會「取出」（綁定）連續的值。