如何在兔子入侵问题中 运行 任意代数

Question

我正在解决 haskell wikibook 中的一个问题，但完全卡住了。他们要求 "Generalize the bunny invasion example in the list monad chapter for an arbitrary number of generations."

兔子入侵实例说明：

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

我尝试生成嵌套列表而不是平面列表

我想我应该使用本章中提到的函数，包括：sequence、replicate、replicateM、mapM、forM 及其下划线版本，它们不会将上下文传递给下一个绑定 monad。

["bunny"] >>= replicateM 2 gen

我明白了

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

但应该是

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

Answer 1

您可以使用 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，其中传递了一个列表 "units" ():

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

这适用于：

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

注意初始值不是"bunny"的列表，而是"bunny"本身。

我们可以实现一个功能，比如通过foldl递归：

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

然后我们得到：

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

我们可以像 一样用递归定义它：

import Control.Monad(>=>)

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