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

私は最後の4行で起こっている無限の神秘的な循環井戸を把握していません。結果a'は、の再帰に依存します。再帰someA自体はに依存する可能性がありますa'が、必ずしもそうとは限りません。

再帰ワーカーがアキュムレータに潜在的な値を何らかの形で「蓄積」しているという雰囲気がありますが、IO aそれについて十分に推論することはできません。

この関数がどのように動作を生成するかについて誰かが説明できますか？

4

2 に答える 2

5

IO aそのコードは、ストリームの最後に到達するまですべてのランダムな選択を遅らせるますます大きなアクションを構成するため、実際には定数空間で実行されません。ケースに到達Nothing -> aして初めて、アクションがa実際に実行されます。

たとえば、この関数によって作成された無限の一定空間ストリームで実行してみてください。

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

明らかに、selectこのストリームでの実行は終了しませんが、遅延アクションに多くのサンクが割り当てられるため、メモリ使用量が増加することがわかります。

これは、コードを少し書き直したバージョンで、進行中に選択を行うため、一定のスペースで実行され、うまくいけばより明確になるはずです。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'は、ストリームをトラバースすることです。2 つの累積引数を維持します。1 つ目は、ストリームからのランダムな要素です (まだ選択されておらず、まだランダムであるため、IO a)。2 番目は、ストリーム内の位置 ( Int) です。

維持される不変条件は、最初のアキュムレータがこれまでに見たストリームから一様に要素を選択すること、および整数がこれまでに検出された要素の数を表すことです。

ここで、ストリームの最後 ( Nothing) に到達すると、現在のランダム要素を返すことができ、問題ありません。

別の要素 (Justケース) が見つかった場合は、もう一度呼び出して再帰しselect'ます。要素数を に更新するのn + 1は簡単です。しかし、ランダム要素を更新するにはどうすればよいsomeAでしょうか? さて、古いランダム要素は、ストリームaの最初の位置から等しい確率で選択します。確率でn新しい要素を選択し、他のすべての場合に古い要素を使用すると、この時点までのストリーム全体に均一な分布が得られます。a'1 / (n + 1)

于 2012-11-16T07:27:03.373 に答える