때때로 오른쪽에서 무한 목록을 접을 수있는 이유는 무엇입니까?

Dec 13 2020

저는 숙제 6의 Part 5에 갇혀있을 때 훌륭한 CIS 194 과정을 수강했습니다 . 분할 성 테스트없이 눈금자 기능 을 구현하는 것 입니다.

무한 목록의 값으로 누적기를 지속적으로 배치하여 눈금자 기능을 구축 할 수 있음을 발견했습니다.

nats = [0,1,2,3,..]
[3]
[2,3,2]
[1,2,1,3,1,2,1]
[0,1,0,2,0,1,0,3,0,1,0,2,0]

그런 다음 Stream목록이없는 데이터 유형에 대해이 알고리즘을 구현하려고 시도했습니다.nil

data Stream a = Cons a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs

instance Show a => Show (Stream a) where
  show = show . take 20 . streamToList

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f x = Cons x (streamFromSeed f (f x))

nats :: Stream Integer
nats = streamFromSeed succ 0

interleave x (Cons y ys) = Cons x (Cons y (interleave x ys))
foldStream f (Cons x xs) = f x (foldStream f xs)
ruler = foldStream interleave nats

예상대로 오른쪽에서 접 으려고했기 때문에 stackoverflow 오류가 발생했습니다. 그러나 일반적인 무한 목록에 대해 동일한 알고리즘이 작동하는 것을보고 놀랐습니다.

import Data.List

interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])

내가 무엇을 놓치고 있습니까? 한 구현은 작동하지만 다른 구현은 작동하지 않는 이유는 무엇입니까?

답변

8 DanielWagner Dec 13 2020 at 11:24

당신 interleave은 충분히 게으르지 않습니다. 무한 구조에서 작업하기 위해 오른쪽 접기가 수행해야하는 마술은 첫 번째 계산을 수행하기 전에 접힌 값의 결과를 너무 자세히 검사하지 않는 것입니다. 그래서:

interleave x stream = Cons x $ case stream of
    Cons y ys -> Cons y (interleave x ys)

이것은 Cons x _검사하기 전에 생성됩니다 stream. 반대로, 버전이 stream방정식의 오른쪽으로 전달되기 전에 약간의 평가가 필요 하며, 이는 본질적으로 생성자가 생성되기 전에 전체 폴드가 발생하도록 강제합니다.

다음 목록 버전에서도 확인할 수 있습니다 interleave.

interleave x list = [x] ++ intersperse x list ++ [x]

반환 된 목록 ( x) 의 첫 번째 요소는에서 intersperse패턴 일치를 시작 하기 전에 알려져 list있습니다.

5 WillemVanOnsem Dec 13 2020 at 07:39

foldr[src] 의 소스 코드를 검사 할 수 있습니다 . 덜 시끄러운 버전은 다음과 같습니다.

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Haskell은 열심히 평가 하지 않습니다 . 따라서 필요한 (foldr f z xs) 경우가 아니면 누산기를 평가하지 않습니다. 따라서 f두 번째 매개 변수가 필요하지 않음 을 의미합니다. 예를 들어 첫 번째 항목 x에 특정 값이 있기 때문에 누산기를 평가하지 않습니다.

예를 들어 우리가 구현하는 경우 takeWhileNeq:

takeWhileNeq a = foldr f []
    where f x xs -> if x == a then [] else (x:xs)

따라서 이것을 목록 takeWhileNeq 2 [1,4,2,5]에서 실행하면 아무것도 평가하지 않습니다 . 그러나 결과를 인쇄하려면 다음과 같이 평가합니다.

   f 1 (foldr f [4,2,5])

, 그렇지 않은 경우를 반환 하므로 다음 f을 검사합니다 .1 == 2(x:xs)

-> 1 : foldr f [4,2,5]

이제 평가 4 == 2하고 이것이 거짓이므로 다음과 같이 평가합니다.

-> 1 : (4 : foldr f [2,5])

이제 우리는을 평가 2 == 2하고 이것이이므로 True함수는 빈 목록을 반환 하고 누산기를 수집 하므로 절대로 보지 않을 것입니다 foldr f [5].