这种循环递归如何提供所需的结果？

Question

请考虑以下优秀博客文章中的以下缩写代码:

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)

到目前为止还不错 - 一个monadic,递归数据结构和从列表中构建一个的方法.

现在考虑使用常量内存从流中选择(统一)随机元素的函数:

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,但我显然无法对其进行足够的推理.

任何人都可以解释这个函数如何产生它的行为吗？

Answer 1

该代码实际上并不在恒定空间中运行,因为它组成了一个越来越大的IO a动作,它延迟了所有随机选择,直到它到达流的末尾.只有当我们到达Nothing -> a案例时才能a实际运行.

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

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

显然,select在这个流上运行不会终止,但你应该看到内存使用率上升,因为它为延迟的动作分配了很多thunk.

这是一个稍微重写的代码版本,随着它的进行做出选择,所以它在恒定的空间中运行,并且应该也更加清晰.请注意,我已经IO a使用plain 替换了该参数,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)保留我们当前的选择然后再其余的的流.