Difference between revisions of "Recursion in a monad"
Jump to navigation
Jump to search
(link to tail recursion) |
Tomjaguarpaw (talk | contribs) (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]] |
||