Monad Recursion

Question

I find it difficult to understand recursion in a monad. An example from the wiki haskell.org is given below:

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

This program outputs three lines from standard input recursively. What I cannot understand is what happens when you get to f 0 and how the recursion spins. How is the final value of the do block created? Why is the reverse line repeated many times in recursion? I know that return is not a function return, as in imperative languages, but I don’t see how this line is repeated.

I know this is a starting question for beginners, but I'm at a standstill.

Answer 1

In this particular case, you can simply turn around completely. Perhaps this helps:

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

There is no recursion at this point. All we have done is apply function definitions. From here we can simplify even more if we assume that the laws of the monad hold:

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

You can pseudo-compile / unwind the monadic block to see how it works:

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

So, it will getLine 3 times, and then create a list of lines, the first line will be the first value in the list.

Each time you see return in a monadic expression, you put a value in it. Each time you see <- (bind) in a monadic expression, you take values ​​from it. In the case of the IO monad, you always put and take out one of the monads. On the contrary, the list monad can "pull out" (bind) consecutive values.