# Recursion in a monad

### From HaskellWiki

(Difference between revisions)

DonStewart (Talk | contribs) (an faq on #haskell) |
(link to tail recursion) |
||

(One intermediate revision by one user not shown) | |||

Line 25: | Line 25: | ||

</haskell> |
</haskell> |
||

− | Or make it tail recursive: |
+ | Or make it [[tail recursion|tail recursive]]: |

<haskell> |
<haskell> |
||

Line 34: | Line 34: | ||

</haskell> |
</haskell> |
||

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

## Latest revision as of 21:47, 25 March 2009

People sometimes wonder how to effectively do recursion when inside a

monadicdo

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