Recursion in a monad

Revision as of 06:34, 29 November 2006 by DonStewart (Talk | contribs)

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 finally, abstract the recursion pattern into a fold:

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