Recursion in a monad

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

People sometimes wonder how to effectively do recursion when inside a monadic do-block. Here's some quick examples:

The problem is to read 'n' lines from stdin, recursively:

The obvious, recursive way:

main = f 3

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

Runs:

    $ runhaskell A.hs
    1
    2
    3
    ["1","2","3"]

Or make it tail recursive:

f 0 acc = return (reverse acc)
f n acc = do
    v  <- getLine
    f (n-1) (v : acc)

Or abstract the recursion pattern into a fold:

f n = do
    s <- foldM fn [] [1..n]
    return (reverse s)

  where fn acc _ = do x <- getLine
                      return (x:acc)

And finally, apply some functor and pointfree shortcuts:

f n = reverse `fmap` foldM fn [] [1..n]
    where fn acc _ = (: acc) `fmap` getLine

Recursion in a monad

Navigation menu

Search