时间戳

首页 > 解决方案 > 每个元素与前一个元素最多相差 1 的随机列表

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

问题描述

我正在尝试编写一个将生成一个列表的函数，其中第一个元素被指定为函数的参数，之后的每个元素与前一个元素的差异最多为 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]，例如）

标签： haskellrandommonadslazy-evaluation

解决方案

您不需要严格版本的>>=. 您需要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

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

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

推荐阅读