每个元素与前一个元素最多相差 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 不会终止的原因相同。然而，我们可以解决这个问题，如果将算法更改为 first 生成与 replicateM 的差异，然后 sum 这些差异与 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

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

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

每个元素与前一个元素最多相差 1 的随机列表

Random list where each element differs by at most 1 from the previous element

random

monads

haskell

lazy-evaluation