같은 스칼라 구현에서 하스켈의 foldr이 왜 stackoverflow하지 않는가?

Question

나는 FP in Scala을 읽습니다.

연습 3.10에서는 foldRight이 오버플로됩니다 (아래 이미지 참조). 내가 아는 한, 하스켈의 foldr은 그렇지 않습니다.

http://www.haskell.org/haskellwiki/

-- if the list is empty, the result is the initial value z; else 
-- apply f to the first element and the result of folding the rest 
foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else 
-- we recurse immediately, making the new initial value the result 
-- of combining the old initial value with the first element. 
foldl f z []  = z     
foldl f z (x:xs) = foldl f (f z x) xs 

어떻게 다른 동작이 가능?

이 두 가지 언어/컴파일러의 차이점은 무엇입니까?

이 차이는 어디에서 발생합니까? 플랫폼 ? 언어? 컴파일러?

스칼라에서 스택 안전 foldRight를 작성할 수 있습니까? 그렇다면 어떻게?

Answer 1

하스켈은 게으르다. 정의

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

가 아닌 빈 목록 xs와 foldr f z xs의 동작은 게으름 결합 기능 f의에 의해 결정되는 것을 우리에게 알려줍니다. x과 썽크 - 전화 foldr f z (x:xs)가 힙에 한 썽크를 할당 특히

, {foldr f z xs} (식 ...를 들고 썽크에 대한 {...}을 쓰기), 그리고 두 개의 인수와 f 호출합니다. 다음에 일어나는 일은 f 님의 책임입니다. 그것은 지연 데이터 생성자 (예 (:) 등)이라면 특히

, 그것은 즉시 ((참조) 두 값에 의해 채워진 생성자의 두 개의 슬롯)을 foldr 호출의 호출자에게 반환한다.

그리고 가장 작은 컴파일러 최적화로 f이 오른쪽에서 그 값을 요구하면 foldr f z xs의 값이 즉시 필요하고 평소와 같이 썽크가 전혀 생성되지 않아야합니다. 스택 기반 평가가 사용될 수

foldr f z [a,b,c,....,n] == 
    a `f` (b `f` (c `f` (... (n `f` z)...))) 

그래서 foldr 실제로 발생할 수 있도록, 매우 긴리스트에 입력 엄격한 조합 기능을 사용했을 때.그러나 결합 기능이 오른쪽에서 값을 즉시 요구하지 않거나 일부만 요구하면 평가는 썽크로 일시 중단되고 f으로 생성 된 부분 결과는 즉시 반환됩니다. 왼쪽의 인수와 동일하지만 입력 목록에 잠재적으로 썽크가 올 수도 있습니다.

Answer 2

하스켈 게으른입니다. 따라서 foldr은 스택이 아니라 힙에 할당됩니다. 인수 함수의 엄격성에 따라 단일 (작은) 결과 또는 큰 구조를 할당 할 수 있습니다.

엄격한 꼬리 재귀 구현과 비교해도 여전히 공간이 부족하지만 스택을 힙으로 교환 했으므로 명확하지 않습니다.

Answer 3

여기서 작성자는 List에 정의 된 것과 같이 scala 표준 라이브러리의 foldRight 정의를 언급하지 않는다는 점에 유의하십시오. 그들은 3.4 절에서 위에 주어진 foldRight의 정의를 언급하고 있습니다.

스칼라 표준 라이브러리는 목록을 역전 (스택 공간에서 수행 할 수 있음) 한 다음 foldLeft를 foldLeft로 정의한 다음 전달 된 함수의 인수를 반대로하여 foldLeft를 호출합니다. 이 목록에 대한 작동하지만, 예를 들어, 안전하게 되돌릴 수 없습니다 구조에 대해 작동하지 않습니다 :

Stream.continually(false).foldRight(true)(_ && _) 

:

scala> Stream.continually(false) 
res0: scala.collection.immutable.Stream[Boolean] = Stream(false, ?) 

scala> res0.reverse 
java.lang.OutOfMemoryError: GC overhead limit exceeded 

이제 가이 작업의 결과 일해야하는지에 대해 생각 할 수 있습니다

대답은 거짓이어야합니다. 스트림에 얼마나 많은 거짓 값이 있는지는 중요하지 않습니다. 무한 값이면 연결을 사용하여 연결하면 false가됩니다. 물론

하스켈은 문제없이이 문제를 가져옵니다

Prelude> foldr (&&) True (repeat False) 
False 

그리고 그 때문에 두 가지 중요한 것들입니다 : 하스켈의 foldr은 오른쪽에서 왼쪽으로하지, 왼쪽에서 오른쪽으로 스트림을 통과하며, 하스켈에서 게으른 태만. 첫 번째 항목은 foldr이 실제로 왼쪽에서 오른쪽으로 목록을 가로 지르며 오른쪽 접기를 오른쪽에서 시작하는 것으로 생각하는 사람들을 놀라게하거나 혼란스럽게 할 수 있지만 오른쪽 접기의 중요한 특징은 시작하는 구조의 끝이 아니라는 것입니다 에, 그러나 어떤 방향으로 연관성이있다. 그래서 목록 [1,2,3,4]와 op라는 이름의 연산, 왼쪽 배는

((1 op 2) op 3) op 4) 

하고 오른쪽 배는

(1 op (2 op (3 op 4))) 

입니다 그러나 평가의 순서가 안 제공 문제. 따라서 제 3 장에서 저자가 왼쪽에서 오른쪽으로 목록을 가로 지르는 접미사를 제공하는 것입니다. 그러나 스칼라가 기본적으로 엄격하기 때문에 우리는 여전히 우리의 무한한 거짓의 흐름을 가로지를 수 없지만, 인내, 그들은 5 장에서 그것에 도달 할 것입니다 :) 나는 표준 라이브러리에 정의 된 foldRight와 scalaz의 Foldable typeclass에서 정의 된대로 차이점을 살펴볼 것입니다.

: scalaz의 접이식에서 정의 여기

def foldRight[B](z: B)(op: (A, B) => B): B 

것 :

다음은 스칼라 표준 라이브러리의 구현입니다

의 차이는 우리가 두 번째 매개 변수를 충분히 게으른 기능 제공으로, 기지국이 모든 게으른, 그리고 지금 우리가 다시 우리의 무한 스트림을 접을 수 있다는 것입니다 : 쉽게

scala> Foldable[Stream].foldRight(Stream.continually(false),true)(_ && _) 
res0: Boolean = false 

Answer 4

하나 하스켈에서 이것을 증명하는 방법은 방정식 추론을 사용하여 게으른 평가를하는 것입니다.의는 foldr의 측면에서 find 함수를 작성하자 열망 언어에서

-- Return the first element of the list that satisfies the predicate, or `Nothing`. 
find :: (a -> Bool) -> [a] -> Maybe a 
find p = foldr (step p) Nothing 
    where step pred x next = if pred x then Just x else next 

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

, 당신은 foldr와 find를 쓴 경우 전체 목록 및 사용 O (n)의 공간을 통과한다. 지연 평가하여, 그 술어를 만족시키는 첫번째 소자에 정지하고 (모듈 가비지 수집) 만 O (1)의 공간을 사용

find odd [0..] 
    == foldr (step odd) Nothing [0..] 
    == step odd 0 (foldr (step odd) Nothing [1..]) 
    == if odd 0 then Just 0 else (foldr (step odd) Nothing [1..]) 
    == if False then Just 0 else (foldr (step odd) Nothing [1..]) 
    == foldr (step odd) Nothing [1..] 
    == step odd 1 (foldr (step odd) Nothing [2..]) 
    == if odd 1 then Just 1 else (foldr (step odd) Nothing [2..]) 
    == if True then Just 1 else (foldr (step odd) Nothing [2..]) 
    == Just 1 

이 평가 결과에도 불구하고, 유한 한 단계에서 정지 사실 [0..] 목록은 무한하므로 전체 목록을 탐색하지는 않습니다. 또한 각 단계에서 표현식의 복잡도에 대한 상한이 있습니다.이 상한은이를 평가하는 데 필요한 상한선 상수로 변환됩니다.

열쇠는 여기에 우리가 접는하고있는 step 기능이 속성을 가지고 있다는 것입니다 : 상관없이 x 및 next의 값이 무엇인지, 그것을 것 중 하나

1. 이를 호출하지 않고, Just x로 평가하지 next thunk, 또는
2. 꼬리말 next (실제로는 문자가 아닐 경우)을 호출하십시오.