이 순환 회귀는 어떻게 원하는 결과를 제공합니까?

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에서 재귀에 따라 달라지며, 은에 따라 달라질 수 있습니다. 단, 반드시에 따라 다르지만 반드시 그런 것은 아닙니다.

회귀 작업자가 어쨌든 IO a 어큐뮬레이터의 잠재적 인 값을 누적하고 있다는 느낌이 들지만, 분명히 그것에 대해 충분히 추론 할 수는 없습니다.

누구든지이 기능이 어떻게 작동하는 지에 대한 설명을 제공 할 수 있습니까?

Answer 1

이 코드는 스트림의 끝에 도달 할 때까지 모든 무작위 선택을 지연시키는 더 크고 더 큰 동작을 구성하기 때문에 실제로는 일정한 공간에서 실행되지 않습니다. Nothing -> a 사례에 도달했을 때만 a에있는 작업이 실제로 실행됩니다.

예를 들어,이 기능에 의해 무한 일정 공간 스트림을 실행하십시오 : 종료하지 않습니다이 스트림에 select를 실행, 분명히

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

,하지만 당신은 메모리 사용량이 올라가 볼 수 지연된 작업에 많은 썽크를 할당하므로

다음은 코드가 약간 변경된 코드입니다. 일정한 공간에서 실행되므로 더 명확하게 이해해야합니다. 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) 나머지 항목을 되풀이하기 전에 현재 선택 항목을 유지할지 여부를 결정합니다 스트림의.

Answer 2

여기에 "순환"이 전혀 보이지 않습니다. 특히 a'은 이 아니고은 someA에 의존합니다. a'은 패턴 가공에 의해 next의 결과에 바인딩됩니다. 그것은 오른쪽에 차례로 사용되는 someA에 의해 사용되고 있지만 이것은 사이클을 구성하지 않습니다.

select'은 스트림을 통과하는 것입니다. 두 개의 누적 인수를 유지합니다. 첫 번째는 스트림에서 임의의 요소입니다 (아직 선택되지 않았으며 여전히 임의적이므로 IO a). 두 번째는 스트림의 위치 (Int)입니다.

불변성은 첫 번째 누산기가 지금까지 본 스트림에서 균일하게 요소를 선택하고 정수가 지금까지 만난 요소의 수를 나타내는 것입니다.

이제 스트림 (Nothing)의 끝 부분에 도달하면 현재 무작위 요소를 반환 할 수 있으며 괜찮습니다.

다른 요소 (Just 경우)가 표시되면 select'을 다시 호출하여 재발행합니다. 요소 수를 n + 1으로 업데이트하는 것은 간단합니다. 그러나 무작위 요소 someA을 어떻게 업데이트합니까? 음, 오래된 무작위 원소 a은 동일한 확률로 첫 번째 n 위치를 선택합니다. 확률이 1/(n + 1) 인 새로운 요소 a'을 선택하고 다른 모든 경우에 이전 요소를 사용하면이 시점까지 전체 스트림에 대해 균일 한 분포를 갖게됩니다.