CODEWITHSUNDEEP
haskell
andro
andro

Reputation: 939

Recursion in a monad

I am at a loss to understand recursion in a monad. From the haskell.org wiki here is an example:

main = f 3

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

This program gets three lines from standard input recursively. What I cannot comprehend is what happens when you get to f 0 and how the recursion unwinds. How does the final value of the do block get constructed? Why is the final return line called repeatedly in the recursion? I know return is not function return as in imperative languages, but I cannot see how this line gets repeated.

I am aware that this is a raw beginners question, but I am stumped.

Upvotes: 6

Views: 1369

Answers (2)

Thiago Negri
Thiago Negri

Reputation: 5351

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 build up a list of the lines, the first line will be the first value in the list.

Every time you see a return in a monadic expression, you are putting a value inside it. Every time you see a <- (bind) in a monadic expression, you are taking values out of it. In the case of the IO monad, you are always putting and taking out a single of the monad. In contrast, the list monad may "take out" (bind) consecutive values.

Upvotes: 3

kosmikus
kosmikus

Reputation: 19657

In this particular case, you can just unfold 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
=
  ...

At this point, there's no recursion left. All we've done is apply function definitions. From here, we can simplify further if we assume that the monad laws 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'' : []

Upvotes: 9

Related Questions