這種循環遞歸如何提供期望的結果？

Question

從this excellent blog post考慮以下簡稱代碼：

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'，但不一定。

我知道遞歸工作者在某種程度上積累了累積器中的潛在值，但我顯然無法對此進行充分的推理。

任何人都可以提供一個關於這個函數如何產生它的行爲的解釋嗎？

Answer 1

該代碼實際上並不在恆定空間中運行，因爲它構成了一個更大更大的動作，它會延遲所有隨機選擇，直到它到達流的末尾。只有當我們到達Nothing -> a的情況下，a的行動纔會真正運行。

例如，嘗試運行它通過這個功能做一個無限的，恆定的空間流：

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

顯然，在此流將不會終止運行select，但你應該看到的內存使用量上升因爲它爲延遲行動分配了大量的時間。

下面是代碼的一個稍微重寫的版本，它隨着它的發展做出選擇，所以它在恆定的空間中運行，並且希望更清晰。請注意，我用一個普通的a取代了IO 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）在遞歸之前保留我們的當前選擇的流。

Answer 2

似乎沒有什麼「循環」在這裏進行。特別地，a'確實是而不是取決於someA。 a'由next的結果受模式機制的約束。它正在被使用在someA這反過來用在右側，但這不構成一個循環。

select'所做的是遍歷流。它維護兩個積累的論點。第一個是流中的隨機元素（它尚未被選中並且仍然是隨機的，因此IO a）。第二個是流中的位置（Int）。

要保持的不變性在於第一個累加器從我們迄今爲止所看到的流中均勻地選擇一個元素，並且該整數表示到目前爲止遇到的元素的數量。

現在，如果我們到達流的末尾（Nothing），我們可以返回當前的隨機元素，這樣就可以了。

如果我們看到另一個元素（Just的情況），那麼我們通過再次調用select'來遞歸。將元素數量更新爲n + 1很簡單。但是，我們如何更新隨機元素someA？那麼，舊的隨機元素a選擇之間的第一個n位置的概率相等。如果我們選擇新元素a'，並且概率爲1/(n + 1)，並且在所有其他情況下使用舊元素，那麼我們再次在整個流中均勻分佈。