Difference between revisions of "Recursion in a monad"

From HaskellWiki
Jump to: navigation, search
(link to tail recursion)
(Deleting page that hasn't been edited for over 10 years)
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]]
 

Revision as of 14:19, 6 February 2021