0

考虑一下这篇出色的博客文章中的以下缩写代码：

import System.Random (Random, randomRIO)

newtype Stream m a = Stream { runStream :: m (Maybe (NonEmptyStream m a)) }
type NonEmptyStream m a = (a, Stream m a)

empty :: (Monad m) => Stream m a
empty = Stream $ return Nothing

cons :: (Monad m) => a -> Stream m a -> Stream m a
cons a s = Stream $ return (Just (a, s))

fromList :: (Monad m) => [a] -> NonEmptyStream m a
fromList (x:xs) = (x, foldr cons empty xs)

到目前为止还不错 - 一种单子递归数据结构和一种从列表构建的方法。

现在考虑这个函数，它使用常量内存从流中选择（一致）随机元素：

select :: NonEmptyStream IO a -> IO a
select (a, s) = select' (return a) 1 s where
  select' :: IO a -> Int -> Stream IO a -> IO a
  select' a n s = do
    next <- runStream s
    case next of 
      Nothing -> a
      Just (a', s') -> select' someA (n + 1) s' where
        someA = do i <- randomRIO (0, n) 
                   case i of 0 -> return a'
                             _ -> a

我没有掌握最后四行中发生的神秘的无限循环井；结果a'取决于 上的递归someA，它本身可能取决于a'，但不一定。

我觉得递归工作者以某种方式在累加器中“累积”潜在值IO a，但我显然无法很好地推理它。

谁能解释一下这个函数是如何产生它的行为的？

4

2 回答 2

5

该代码实际上并没有在恒定空间中运行，因为它构成了一个越来越大的IO a动作，它会延迟所有随机选择，直到它到达流的末尾。只有当我们到达Nothing -> acase 时，动作才会a真正运行。

例如，尝试在此函数生成的无限恒定空间流上运行它：

repeat' :: a -> NonEmptyStream IO a
repeat' x = let xs = (x, Stream $ return (Just xs)) in xs

显然，select在此流上运行不会终止，但是您应该看到内存使用量上升，因为它为延迟的操作分配了大量的 thunk。

这是一个稍微重写的代码版本，它会随着选择进行选择，因此它在恒定空间中运行，并且希望也更清晰。请注意，我已经IO a用一个简单的参数替换了这个参数，a这清楚地表明这里没有建立延迟的操作。

select :: NonEmptyStream IO a -> IO a
select (x, xs) = select' x 1 xs where
  select' :: a -> Int -> Stream IO a -> IO a
  select' current n xs = do
    next <- runStream xs
    case next of 
      Nothing       -> return current
      Just (x, xs') -> do
        i <- randomRIO (0, n)                         -- (1)
        case i of                                     
          0 -> select' x       (n+1) xs'              -- (2)
          _ -> select' current (n+1) xs'              -- (3)

顾名思义，current在每一步存储当前选择的值。一旦我们从流中提取了下一个项目，我们 (1) 选择一个随机数并使用它来决定是 (2) 用新项目替换我们的选择还是 (3) 在递归其余部分之前保留我们当前的选择的流。

于 2012-11-16T06:56:24.380 回答
2

这里似乎没有任何“循环”发生。特别a'是不依赖于someA. 的a'结果受模式匹配的约束next。它被someA哪个轮流用在右手边，但这并不构成一个循环。

什么select'是遍历流。它维护两个累积参数。第一个是来自流的随机元素（它尚未被选择并且仍然是随机的，因此IO a）。第二个是流中的位置 ( Int)。

保持不变的是第一个累加器从我们目前看到的流中统一选择一个元素，并且整数表示到目前为止遇到的元素数量。

现在，如果我们到达流的末尾（Nothing），我们可以返回当前的随机元素，就可以了。

如果我们看到另一个元素（案例），那么我们通过再次Just调用来递归。select'更新元素的数量n + 1是微不足道的。但是我们如何更新随机元素someA呢？好吧，旧的随机元素以相等的概率在流a的第一个位置之间进行选择。如果我们以概率n选择新元素并在所有其他情况下使用旧元素，那么我们在整个流上再次得到均匀分布。a'1 / (n + 1)

于 2012-11-16T07:27:03.373 回答