随机列表，其中每个元素与前一个元素的差异最多为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函数采用整数，并随机地向其添加-1,0或1。 steps函数需要执行一定数量的迭代和一个起始整数，并将step应用正确的次数。

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

然后我意识到这个问题可能是因为它实际上会产生一个类似于下面的列表：

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

然后似乎很清楚为什么会发生这种情况。所以我的问题是，我可以阻止这个吗？我可以强制Haskell评估每个元素的进展情况吗？是否有严格版本的>>=运营商？

（编辑：我认为给出一个我正在寻找的列表的例子可能是有用的，而不是仅仅描述一个。例如，[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中使用有限数量的IOs并使用通常的scanl生成您想要的列表。

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