Difference between revisions of "Recursion in a monad"
Jump to navigation
Jump to search
DonStewart (talk | contribs) (an faq on #haskell) |
DonStewart (talk | contribs) m (more) |
||
Line 34: | Line 34: | ||
</haskell> |
</haskell> |
||
− | Or |
+ | 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> |
<haskell> |
Revision as of 06:36, 29 November 2006
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