monad中的递归

Question

我无法理解monad中的递归.从haskell.org wiki这里有一个例子:

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

此时,没有任何递归.我们所做的就是应用函数定义.从这里开始,如果我们假设monad法则成立,我们可以进一步简化:

  ...
=   { 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'' : []