Difference between revisions of "Recursion in a monad"

From HaskellWiki
Jump to: navigation, search
(Deleting page that hasn't been edited for over 10 years)
m (Reverted edits by Tomjaguarpaw (talk) to last revision by Lemming)
 
Line 1: Line 1:
  +
People sometimes wonder how to effectively do recursion when inside a
  +
monadic <hask>do</hask>-block. Here's some quick examples:
  +
  +
The problem is to read 'n' lines from stdin, recursively:
  +
  +
The obvious, recursive way:
  +
  +
<haskell>
  +
main = f 3
  +
  +
f 0 = return []
  +
f n = do v <- getLine
  +
vs <- f (n-1)
  +
return $! v : vs
  +
</haskell>
  +
  +
Runs:
  +
  +
<haskell>
  +
$ runhaskell A.hs
  +
1
  +
2
  +
3
  +
["1","2","3"]
  +
</haskell>
  +
  +
Or make it [[tail recursion|tail recursive]]:
  +
  +
<haskell>
  +
f 0 acc = return (reverse acc)
  +
f n acc = do
  +
v <- getLine
  +
f (n-1) (v : acc)
  +
</haskell>
  +
  +
Or abstract the recursion pattern into a fold:
  +
  +
<haskell>
  +
f n = do
  +
s <- foldM fn [] [1..n]
  +
return (reverse s)
  +
  +
where fn acc _ = do x <- getLine
  +
return (x:acc)
  +
</haskell>
  +
  +
And finally, apply some functor and pointfree shortcuts:
  +
  +
<haskell>
  +
f n = reverse `fmap` foldM fn [] [1..n]
  +
where fn acc _ = (: acc) `fmap` getLine
  +
</haskell>
  +
  +
[[Category:Code]]
  +
[[Category:Glossary]]

Latest revision as of 15:18, 6 February 2021

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