递归单子

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。相反，列表单子可能会“取出”（绑定）连续的值。