# Difference between revisions of "Recursion in a monad"

From HaskellWiki

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 : 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
```