Doing recursion within an IO monad

Question

I have been trying to figure out how to do recursion within an IO monad. I am familiar with doing recursion with pure functions, but have not been able to transfer this knowledge to IO monads.

Recursion with pure functions
I'm comfortable with doing recursion with pure functions such as the foo function below.

foo (x:y:ys) = foo' x y ++ foo ys

A function with IO [String] output
I made a function like goo below that does what I need and has an IO output.

goo :: String -> String -> IO [String]
goo xs ys = goo' xs ys 

Trying to get recursion inside an IO monad
When I try to do recursion within an IO monad (e.g., a "main" function) I cannot. I've looked up liftM, replicateM, and the undo-the-IO <- operator or function. I want an IO monad like hoo or hoo' (apologies for the gibberish that follows).

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
                  let rs = goo xs ys ++ hoo yss
                  return rs

or

hoo' :: [String] -> IO [String]
hoo' (xs:ys:yss) = do
                  rs <- goo xs ys 
                  let gs = rs ++ hoo' yss
                  return gs

(BTW, in case you are wondering what my project is, I'm writing a Genetic Algorithm program from scratch for a course. My goo function takes two parents and breeds two offspring, which are returned as an IO because goo uses a random number generator. What I need to do is to to use a recursive hoo function to use goo to breed 20 offspring from a list of 20 parents. The idea I have is to take the first two parents in the list, breed two offspring, take the next two parents on the list, breed another pair of offspring, so on and so forth.)

Answer 1

If you find do notation confusing, my recommendation would be to not use it at all. You can do everything you need with >>=. Just pretend its type is

(>>=) :: IO a -> (a -> IO b) -> IO b

That said, let's look at your code.

let in a do block gives a name to some value. That's the same thing it does outside of do, so that's not helpful here (it gives you no additional power).

<- is more interesting: It acts as an "extract a value from IO locally" construct (if you squint a bit).

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
    -- The right-hand side (goo xs ys) has type IO [String], ...
    rs <- goo xs ys
    -- ... so rs :: [String].

    -- We can apply the same construct to our recursive call:
    hs <- hoo yss
    -- hoo yss :: IO [String], so hs :: [String].

    let gs = rs ++ hs
    return gs

As mentioned above, let just binds a name to a value, so we don't really need it here:

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
    rs <- goo xs ys
    hs <- hoo yss
    return (rs ++ hs)

---

Alternatively, without do notation and <- we'd do it as follows.

(>>=) :: IO a -> (a -> IO b) -> IO b

>>= takes an IO value and a callback function, and it runs the function on the "unwrapped" value (a). That means within the function we get local access to the value as long as the result of the whole thing is IO b again (for some arbitrary type b).

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys -- :: IO [String]
    ...

We have an IO [String] and we need to do something with [String], so we use >>=:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> ...)

If you look at >>='s type signature, the role of a is played by [String] here (rs :: [String]) and b is also [String] (because hoo as a whole needs to return IO [String]).

So what do we do in the ... part? We need to make a recursive call to hoo, which again results in an IO [String] value, so we use >>= again:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> hoo yss >>= (\hs -> ...))

Again, hs :: [String] and ... better have type IO [String] to make the whole thing typecheck.

Now that we have rs :: [String] and hs :: [String], we can simply concatenate them:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> hoo yss >>= (\hs -> rs ++ hs))  -- !

This is a type error. rs ++ hs :: [String], but the context requires IO [String]. Fortunately there's a function that can help us out:

return :: a -> IO a

Now it typechecks:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> hoo yss >>= (\hs -> return (rs ++ hs)))

Due to the way Haskell syntax works (function bodies extend as far to the right as possible), most parens here are actually optional:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= \rs -> hoo yss >>= \hs -> return (rs ++ hs)

And with a bit of reformatting the whole thing can be made to look pretty suggestive:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= \rs ->
    hoo yss   >>= \hs ->
    return (rs ++ hs)

Answer 2

do notation is very handy. Use it, it's your friend. We just need to follow its rules, were each thing going into its place must have a correct type, correspondingly.

You were very close:

goo :: String -> String -> IO [String]

{- hoo' :: [String] -> IO [String]
hoo' (xs:ys:yss) = do
                  rs <- goo xs ys 
                  let gs = rs ++ hoo' yss
                  return gs -}

hoo'' :: [String] -> IO [String]
hoo'' (xs:ys:yss) = do
                  rs <- goo xs ys     -- goo xs ys :: IO [String] -- rs :: [String]
                  qs <- hoo'' yss     -- hoo'' yss :: IO [String] -- qs :: [String]
                  let gs = rs ++ qs                               -- gs :: [String]
                  return gs           -- return gs :: IO [String]

In do notation, with x <- foo, when foo :: IO a, we have x :: a. That's it. (Some more explanations are e.g. here).

As for recursion, it is achieved with do notation just as it is achieved in pure code: by naming things, and referring to the same name from inside the expression defining that name, whether it is a pure expression or a do notation.

Recursion is a leap of faith. We don't care how the thing is defined -- we assume it is defined correctly so we can just refer to it by its name. As long as the types fit.

Answer 3

To do this with do notation, you need to bind the results of every IO action in order to use those results in pure expressions such as let rs =…++…, like so:

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
  g <- goo xs ys
  h <- hoo yss
  let rs = g ++ h
  return rs

However, often you don’t want to introduce a temporary name for the result of every action, so in typical Haskell code, there are a few combinators that make this kind of thing more compact. Here you can use liftA2:

liftA2
  :: Applicative f

  -- Given a pure function to combine an ‘a’ and a ‘b’ into a ‘c’…
  => (a -> b -> c)

  -- An action that produces an ‘a’…
  -> f a

  -- And an action that produces a ‘b’…
  -> f b

  -- Make an action that produces a ‘c’.
  -> f c

Like this:

hoo (xs:ys:yss) = liftA2 (++) (goo xs ys) (hoo yss)

liftA2 only works for functions of two arguments, though; for applying functions of other numbers of arguments, you can use the Functor operator <$> (an alias of fmap) and the Applicative operator <*>:

(<$>)
  :: Functor f

  -- Given a pure function to transform an ‘a’ into a ‘b’…
  => (a -> b)

  -- And an action that produces an ‘a’…
  -> f a

  -- Make an action that produces a ‘b’.
  -> f b

(<*>)
  :: Applicative f

  -- Given an action that produces a function from ‘a’ to ‘b’…
  => f (a -> b)

  -- And an action that produces an ‘a’…
  -> f a

  -- Make an action that produces a ‘b’.
  -> f b

These can be combined like so:

(++) <$> goo xs ys :: IO ([String] -> [String])
--                    f  (a        -> b)

hoo yss :: IO [String]
--         f a

hoo (xs:ys:yss) = (++) <$> goo xs ys <*> hoo yss :: IO [String]
--                                                  f  b

That is, fmapping (++) over the result of goo xs ys using <$> is an action that returns a partially applied function, and <*> produces an action that applies this function to the result of hoo yss.

(There is a law which states that f <$> x is equivalent to pure f <*> x—that is, if you have an action pure f that just returns a function f, unwrap that action and apply it to the result of x using <*>, then that’s the same as just applying the pure function to the action with <$>.)

Another example of using this with a function of 3 arguments:

cat3 a b c = a ++ b ++ c

main = do
  -- Concatenate 3 lines of input
  result <- cat3 <$> getLine <*> getLine <*> getLine
  putStrLn result

You can think of all of these combinators as different kinds of application operators, like ($):

 ($)  ::   (a ->   b) ->   a ->   b
(<$>) ::   (a ->   b) -> f a -> f b
(<*>) :: f (a ->   b) -> f a -> f b
(=<<) ::   (a -> f b) -> f a -> f b

• ($) applies a pure function to a pure argument
• (<$>) applies a pure function to the result of an action
• (<*>) applies a pure function resulting from an action to the result of another action
• (=<<) (the flipped version of (>>=)) applies a function returning an action to the result of an action