递归定义一元随机数列表：最惯用的 Haskell 并且类似于纯代码

Question

我正在尝试递归地创建一个随机数列表，该列表使用前一个值来获取下一个值（因此需要递归而不是 map 或 fold，而且我更愿意将其显式化，除非 map/foldr相比之下，它变得简单得可笑）。

在我看来，使用纯 PRNG 非常简单和惯用（puregaussian 使用 System.Random 生成正常变量并具有类型 puregaussian :: System.Random.RandomGen t => t -> Double -> Double -> (Double, t)）。

purecurse :: System.Random.RandomGen t => t -> Double -> [Double] -> [Double]
purecurse gen current [] = []
purecurse gen current (x:xs) = let (rand, gen2) = puregaussian gen 0 1
                                   next = current + rand
                               in current:purecurse gen2 next xs

不幸的是，纯 PRNG 在 Haskell 中似乎不如单子 PRNG 开发得那么好，所以我想使用像 random-fu 或 mwc-probability 这样的库来做同样的事情，并且我发现可行的解决方案要么单一，要么不够简洁，要么两者兼而有之。

这是一个使用 do 表示法的有效解决方案，以及我对它不满意的原因：

import Control.Monad.Primitive
import System.Random.MWC.Probability

recurse :: PrimMonad m => Gen (PrimState m) -> [Double] -> [Double] -> m [Double]
recurse gen history@(current:_) [] = return history
recurse gen history@(current:_) (x:xs) = do
                                         rand <- (sample (normal 0 1) gen)
                                         let next = current + rand
                                         recurse gen (next:history) xs

首先，我宁愿使用 >>= 也不愿使用符号，但是我找不到绑定类型为 m Double 的 rand 变量然后解除它的方法在最后的情况下得到 m [Double] 。似乎没有很多文档（我能找到）或关于如何做类似事情的例子。我想也许有必要嵌套 (>>=) 运算符，但这会使函数变得极其复杂或不可读。如果这是权衡，也许 do 表示法更简洁，但我什至没有设法做到这一点，我想知道如何做到。

其次，该函数要求在每次调用时传递整个列表，并反向返回列表（只需切换 next 和 history 即可打破它）。

所以。我希望能够传递初始状态和一个列表以递归 returns 一个单值列表。

我想得到帮助的主要问题是：是否有一种 Haskell 惯用的方式来编写这种单子值的递归，从而产生类似于纯函数结构的单子列表？

Answer 1

The main question I would like help with is: is there a Haskell idiomatic way of writing such a recursion of monadic values resulting in a monadic list that is similar to the structure of a pure function?

您可以分两步完成。让你的递归函数 return 有一个 "monadic actions" 的列表，然后组合/排序这些动作。

让我们考虑一个更简单但与您的函数类似的函数，以便于演示。让我们考虑输入而不是随机性。您追索的列表仅用于大小（内容被忽略）所以我们只使用一个整数。

rc ::  Int -> [Double] -> IO [Double]
rc 0 h        = return h
rc n h@(cr:_) = do rand <- readLn :: IO Double
                   let nx = cr + rand
                   rc (n-1)(nx:h)

这是一个类似的替代方案，可以按照您想要的方式工作

rc' ::  Int -> Double -> IO [Double]
rc' 0 cr = return []
rc' n cr = do rand <- readLn :: IO Double
              let nx = cr + rand
              xs   <- rc' (n-1) nx
              return (nx : xs)

这里没有做符号

rc'' ::  Int -> Double -> IO [Double]
rc'' 0 cr = return []
rc'' n cr = (readLn :: IO Double) >>= (\rand -> 
              let nx = cr + rand 
              in (rc'' (n-1) nx) >>= (\xs ->
                 return (nx : xs)))

无论如何，您可以做的另一件事是抽象出代码片段，而不是拥有单一的表示。

在每个步骤中，您都需要当前值来生成新值。因此，一个步骤是 Double -> IO Double 类型的函数。这是一个非常简洁的类型，是 monad 世界的基础。您可以通过 x >>= step 将值绑定到一个步骤或使用 step1 >=> step2 组合两个步骤。所以我们开始吧。

step :: Double -> IO Double
step cr = do rand <- readLn :: IO Double
             return (cr + rand)

非常容易理解。您 'generate' 一个数字，将当前数字与 return 结果相加。而你想要做 n 这样的步骤，所以列一个步骤列表。

steps :: Int -> [Double -> IO Double]
steps n = replicate n step

现在您可以选择如何组合它们。例如，用 >=> 折叠步骤列表是很自然的。你会得到这个，

runSteps :: Int -> Double -> IO Double 
runSteps n = foldr (>=>) return (steps n)

它接近你想要的但只是 return 最终结果，而不是在每一步累积生成的值。下面是一个（受限的）类型(>=>)和我们想要的运算符类型(*=>)。

(>=>) :: Monad m => (a -> m a) -> (b -> m  a)  -> a -> m  a
(*=>) :: Monad m => (a -> m a) -> (a -> m [a]) -> a -> m [a]

定义是，

(*=>) :: Monad m => (a -> m a) -> (a -> m [a]) -> a -> m [a]
(*=>) ac uc c = do x  <- ac c
                   xs <- uc x
                   return (x:xs)

我实际上认为这封装了您不是特别喜欢的部分。现在我们将其抽象为这段孤立的代码。甚至远离递归调用。最后我们只是折叠以执行这些步骤。

execSteps :: Int -> Double -> IO [Double] 
execSteps n = foldr (*=>) (\x -> return []) (steps n)

此函数与原始函数的不同之处在于初始输入是 Double 而不是 [Double]。但这是有意义的类型。您只需在原始函数中传递一个包装好的双精度值。并且它会按照您的要求累积 'right' 顺序中的元素。

Answer 2

在这种情况下，我通常会直接使用具有适当的类似列表界面的流式库，例如 streaming。它们允许从纯代码到 monadic 的更自然的转换，并且具有额外的好处，即您不需要一次 construct/consume 所有结果，而是增量地，就像纯列表一样。

我不确定purecurse在做什么，但可以写成

import           Streaming
import qualified Streaming.Prelude as S

recurse :: PrimMonad m 
        => Gen (PrimState m) 
        -> Double 
        -> [Double] 
        -> Stream (Of Double) m ()
recurse gen current [] = 
    return ()
recurse gen current (x:xs) =
    S.yield current *> -- (*>) and (>>) work like concatenation for pure lists
    lift (sample (normal 0 1) gen) >>= \rand -> 
    recurse gen (current + rand) xs

或者，更自然地使用 do-notation，如：

recurse :: PrimMonad m 
        => Gen (PrimState m) 
        -> Double 
        -> [Double] 
        -> Stream (Of Double) m ()
recurse gen current [] = 
    return ()
recurse gen current (x:xs) = 
    do S.yield current -- (*>) and (>>) work like concatenation for pure lists
       rand <- lift $ sample (normal 0 1) gen
       recurse gen (current + rand) xs

现在您可以使用类似 S.take to generate/extract only parts of the result. If you want to get the whole list, you can use S.toList_ 的函数了。

Answer 3

is there a Haskell idiomatic way of writing such a recursion of monadic values resulting in a monadic list that is similar to the structure of a pure function

通常，当需要将一元值应用于纯函数时，Applicative 运算符，例如 <$>、<*> 可能会有所帮助。

特别是对于列表构造，经常以递归的方式应用运算符(:)来构建列表，如

f [] = []
f (x:xs) = x : f xs

前缀方式：

(:) x (f xs)

然而，(:)是纯函数，默认不接受monadic值，但好消息是，每个数据类型都是Monad的实例，它也是Applicative的实例。在上面提到的 Applicative 运算符的帮助下，monadic value 可以应用于纯函数而无需任何更改。例如，

(:) <$> (pure x) <*> (pure .f) xs

将return一个单子列表而不是纯列表。

Return 对于您的问题，就我个人而言，我认为您的解决方案几乎是一种惯用的方法（因为它简单易读），除了总是在头部附加 next random value history。

正如您所说，the list back in reverse 更糟糕的是，当 history 列表已经有旧的随机值时，不方便找出哪个是新的添加到其中。

要解决，可以稍微修改为：

recurse :: PrimMonad m => Gen (PrimState m) -> [Double] -> [Double] -> m [Double]
recurse gen history [] = return history
recurse gen history (x:xs) = do rand <- (sample (normal 0 1) gen)
                                let next = (last history) + rand
                                recurse gen (history ++ [next]) xs

这是有道理的，如果历史的最后一个元素是最新的随机值。

但是(:)和(++)的区别在于：(:)是O(1)，而(++)是O(N)，其中N是历史列表的长度。（并且 last history 也是 O(N) 而不是 O(1)）。

为了存档一个有效的解决方案，辅助函数可能需要引入，比如说，newHistory，以构建一个新的随机值列表：

newHistory::PrimMonad m=>Gen(PrimState m)->m Double->[Double]->m [Double]
newHistory _ _ []             = return []
newHistory gen current (x:xs) = let next = (+) <$> current <*> sample (normal 0 1) gen
                                in  (:) <$> next <*> newHistory gen next xs

如前所述，在应用运算符的帮助下，语法看起来像纯函数，除了以前缀方式应用函数并使用应用运算符。

然后追加回原来的 history 列表为：

(++) <$> pure history <*> newHistory gen (pure $ last history) xs

recurse 函数的应用版本如下所示：

recurse2::PrimMonad m=>Gen(PrimState m)->[Double]->[Double]->m [Double]
recurse2 gen history xs = 
    (++) <$> pure history <*> newHistory gen (pure $ last history) xs

    where newHistory::PrimMonad m=>Gen(PrimState m)->m Double->[Double]->m [Double]
          newHistory _ _ []         = return []
          newHistory gen current (x:xs) = 
            let next = (+) <$> current <*> sample (normal 0 1) gen
            in  (:) <$> next <*> newHistory gen next xs

Answer 4

您的问题似乎与 do-notation 和 monad 有关。您假设发生的事情比实际情况要多得多：learning how the desugaring works 会帮助您。

无论如何，让我们一步步尝试将非 monadic 版本转换为 monadic 版本。一、类型签名：

recurse :: PrimMonad m => Gen (PrimState m) -> Double -> [Double] -> m [Double]

我不确定您为什么将 [Double] 作为您版本中的第二个参数：我们希望尽可能少地更改原始版本。第一条，则：

purecurse gen current [] = []
-- Goes to:
recurse gen current [] = return []

同样，我们正在尽可能少地进行更改：在您的纯代码中此子句中没有发生任何影响，因此此处也不应发生任何影响。接下来的两行你做对了：

purecurse gen current (x:xs) = let (rand, gen2) = puregaussian gen 0 1
                                   next = current + rand
-- Goes to:
recurse gen current (x:xs) = do rand <- (sample (normal 0 1) gen)
                                let next = current + rand

但是最后一个把你绊倒了。理想情况下，我们会写：

in current:purecurse gen2 next xs
-- Goes to:
current:recurse gen next xs

但是不行！更重要的是，你会得到一个令人困惑的错误：

• Couldn't match type ‘Double’ with ‘[Double]’
  Expected type: m [Double]
    Actual type: [Double]

这可能是导致您误入歧途的原因。该问题与列表无关：它与 m （封装 monad）有关。当你写 current : xs 时，xs 必须是一个列表：在这个例子中，它实际上是一个 m [Double]，或者一个包裹在 monad 中的列表。有两种方法可以解决这个问题（它们都是等价的）。我们可以展开列表，再次使用 do 表示法：

rest <- recurse gen next xs
return (current : rest)

或者我们可以提升函数current :在monad内部工作：

fmap (current:) (recurse gen next xs)

递归定义一元随机数列表：最惯用的 Haskell 并且类似于纯代码

Recursively defining a list of monadic random numbers: most idiomatic Haskell and analogous to pure code

random

monads

recursion

haskell

list