Recursion in a monad: Difference between revisions
Tomjaguarpaw (talk | contribs) (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 : vsRuns:
$ 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