每个元素与上一个元素最多相差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。毕竟，您已经确定了问题所在，正在建立无限数量的计算：

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

您将需要一个单子变量iterate：

-- 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，IO并使用通常的scanl方法生成所需的列表。

^{*流媒体库中有一些变体，使用者可以决定是否可以运行计算。iterateM可以在那里实现，例如在中ConduitM。}