Search code examples
haskellbindmonadsapplicativereplicate

how to run an arbitrary number of generations in the bunny invasion problem

I'm working through a problem in the haskell wikibook and am totally stuck. They ask to "Generalize the bunny invasion example in the list monad chapter for an arbitrary number of generations."

The description of the bunny invasion example:

"It is easy to incorporate the familiar list processing functions in monadic code. Consider this example: rabbits raise an average of six kits in each litter, half of which will be female. Starting with a single mother, we can model the number of female kits in each successive generation (i.e. the number of new kits after the rabbits grow up and have their own litters):" 

Prelude> let generation = replicate 3
Prelude> ["bunny"] >>= generation
["bunny","bunny","bunny"]
Prelude> ["bunny"] >>= generation >>= generation
["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]

My attempt generates nested lists instead of a flat list

There are functions mentioned in the chapter which i guess I'm supposed to use including: sequence, replicate, replicateM, mapM, forM and their underscore versions which do not pass the context to the next bound monad.

["bunny"] >>= replicateM 2 gen

I get 

[["bunny","bunny","bunny"],["bunny","bunny","bunny"]]

but it should be 

["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]
Solution

  • You can make use of nest :: Monad m => Int -> (a -> m a) -> a -> m a, or implement this yourself. nest makes use of the foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b, where it is passed a list of "units" ():

    nest :: (Monad m) => Int -> (a -> m a) -> a -> m a
nest n f x0 = M.foldM (\x () -> f x) x0 (List.replicate n ())

    this then works with:

    Prelude Control.Monad.HT> nest 2 generation "bunny"
["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]

    Note that the initial value is not a list of "bunny", but "bunny" itself.

    We can implement a function, for example through foldl recursion:

    foldN :: Monad m => Int -> (a -> m a) -> m a -> m a
foldN n x0 = foldl (>>=) x0 . replicate n

    We then obtain:

    Prelude Control.Monad> foldN 2 ["bunny"] generation
["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]

    we can, like @DanielWagner says, define this with recursion with:

    import Control.Monad(>=>)

manyGenerations :: Integral n => n -> [a] -> [a]
manyGenerations 0 = id
manyGenerations n = generation >=> manyGenerations (n-1)