haskell - 随机列表，其中每个元素与前一个元素最多相差 1

Question

我正在尝试编写一个函数来生成一个列表，其中第一个元素被指定为函数的参数，之后的每个元素与前一个元素的差异最多为 1。这是我尝试过的:

import Data.List
import System.Random

step :: Int -> IO Int
step n = (+n) <$> randomRIO (-1, 1)

steps :: Int -> Int -> IO [Int]
steps n = sequence . take n . iterate' (>>= step) . return

(我也尝试过非严格的 iterate 函数，它给了我相同的结果)。
step function 接受一个整数，并随机地将 -1、0 或 1 添加到它。 steps函数需要执行一定数量的迭代和一个起始整数，并应用 step正确的次数。

问题是 steps给我诸如 [0,1,-1,0,1,1,1,3] 之类的东西，这是错误的。看起来每个元素每次都是从头开始生成的，而我希望每个元素都依赖于前一个元素。这就是我决定使用 iterate' 的原因而不是 iterate ，这表示它在继续之前将每次迭代减少到 WHNF，但即使它仍然不起作用。

然后我意识到问题可能是由于它实际上会生成一个看起来像这样的列表:

[ n,
  n >>= step,
  n >>= step >>= step
  ... ]

然后似乎很清楚为什么会发生。所以我的问题是，我可以防止这种情况吗？我可以强制 Haskell 在执行过程中评估每个元素吗？有没有严格版的 >>=运算符(operator)？

(编辑:我认为给出一个我正在寻找的列表类型的例子可能很有用，而不是仅仅描述一个。例如 [0, 1, 2, 1, 2, 1, 0, -1] )

Answer 1

您不需要 >>= 的严格版本.您需要 iterate 的 monadic 变体.毕竟，您已经确定了您的问题，您正在构建无限数量的计算:

[ return x , return x >>= step, return x >>= step >>= step, ... ]

你需要一个 iterate 的 monadic 变体:

-- This function does not work, but shows the principle we would
-- want from such a function.
iterateM :: Monad m => (a -> m a) -> a -> m [a]
iterateM f x = do
     y  <- f x
     ys <- iterateM f y -- << this never terminates
     return (y:ys)

但是，该变体不存在*，因为它不会终止，原因与 forM [1..] return 相同。不终止。但是，如果更改算法以首先生成与 replicateM 的差异，我们可以解决此问题。然后将这些差异与 scanl 相加:

import Control.Monad (replicateM)
import System.Random (randomRIO)

step :: IO Int
step = randomRIO (-1, 1)

steps :: Int -> Int -> IO [Int]
steps n x = scanl (+) x <$> replicateM n step

在这种情况下，我们的数量有限 step s 在 IO并使用通常的 scanl生成您想要的列表。

* 流库中有一些变体，消费者可以在其中决定计算是否可以运行。 iterateM可以在那里实现，例如在 ConduitM 中.