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.