Difference between revisions of "Recursion in a monad"

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"]

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

@@ 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"]
+</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]]