foldl은 꼬리 재귀 적이므로 foldr이 foldl보다 빠르게 실행되는 이유는 무엇입니까?

foldl은 꼬리 재귀 적이므로 foldr이 foldl보다 빠르게 실행되는 이유는 무엇입니까?

---

foldl과 foldr를 테스트하고 싶었습니다. 내가 본 것에서 테일 재귀 최적화로 인해 가능할 때 foldl보다 foldl을 사용해야합니다.

이것은 의미가 있습니다. 그러나이 테스트를 실행 한 후 혼란 스럽습니다.

foldr (시간 명령 사용시 0.057 초 소요) :

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (시간 명령 사용시 0.089 초 소요) :

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

이 예제는 사소한 것이 분명하지만 foldr이 foldl을이기는 이유에 대해 혼란 스럽습니다. 이것은 foldl이이기는 명백한 사례가 아니겠습니까?

---

게으른 평가의 세계에 오신 것을 환영합니다.

엄격한 평가 측면에서 생각해 보면 foldl은 "좋아"보이고 foldr는 "나쁜"것처럼 보입니다. foldl은 꼬리 재귀이기 때문입니다.하지만 foldr는 스택에 타워를 만들어서 마지막 항목을 먼저 처리 할 수 ​​있습니다.

그러나 지연 평가는 테이블을 바꿉니다. 예를 들어 map 함수의 정의를 살펴 보겠습니다.

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Haskell이 엄격한 평가를 사용한다면 이것은 그다지 좋지 않을 것입니다. 먼저 꼬리를 계산 한 다음 항목 앞에 추가해야하기 때문입니다 (목록의 모든 항목에 대해). 이를 효율적으로 수행하는 유일한 방법은 요소를 반대로 만드는 것입니다.

그러나 Haskell의 지연 평가 덕분에이 맵 기능은 실제로 효율적입니다. Haskell의 목록은 생성자로 생각할 수 있으며이 맵 함수는 입력 목록의 첫 번째 항목에 f를 적용하여 첫 번째 항목을 생성합니다. 두 번째 항목이 필요한 경우 추가 공간을 사용하지 않고 동일한 작업을 다시 수행합니다.

그것은 그가 밝혀 map측면에서 설명 될 수 있습니다 foldr:

map f xs = foldr (\x ys -> f x : ys) [] xs

그것을 보면 알기 어렵지만, foldr가 f즉시 첫 번째 인수를 줄 수 있기 때문에 게으른 평가가 시작 됩니다.

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

f정의 된에 의해 map첫 번째 매개 변수 만 사용하여 결과 목록의 첫 번째 항목을 반환 할 수 있기 때문에 접기가 일정한 공간에서 느리게 작동 할 수 있습니다.

이제 게으른 평가가 반격을가합니다. 예를 들어, 합계 [1..1000000]를 실행 해보십시오. 스택 오버플로가 발생합니다. 왜 그래야합니까? 왼쪽에서 오른쪽으로 평가해야합니다.

Haskell이 평가하는 방법을 살펴 보겠습니다.

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

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

Haskell은 추가 작업을 수행하기에는 너무 게으르다. 대신 숫자를 가져와야하는 평가되지 않은 썽크의 탑으로 끝납니다. 스택 오버플로는 모든 썽크를 평가하기 위해 깊이 재귀해야하기 때문에이 평가 중에 발생합니다.

다행히도 Data.List에는 foldl'엄격하게 작동 하는 특수 함수가 있습니다. foldl' (+) 0 [1..1000000]스택 오버플로가 발생하지 않습니다. (참고 : 나는 교체 시도 foldl와 foldl'테스트에 있지만 실제로 느리게 실행했다.)

---

편집 :이 문제를 다시 보면 현재의 모든 설명이 다소 불충분하다고 생각하므로 더 긴 설명을 작성했습니다.

차이점은 감소 기능을 적용 하는 방법 foldl과 foldr적용에 있습니다. foldr케이스를 보면 다음과 같이 확장 할 수 있습니다.

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

이 목록은에서 처리되며 sum다음과 같이 사용됩니다.

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

목록 연결의 세부 사항을 생략했지만 이것이 감소가 진행되는 방식입니다. 중요한 부분은 목록 순회를 최소화하기 위해 모든 것이 처리된다는 것입니다. 는 foldr단지 회씩 연결 연속 목록 순회을 필요로하지 않는, 한 번 목록을 통과하고, sum마지막으로 한 번에 목록을 소모합니다. 비판적으로 목록의 헤드는 foldr즉시부터 까지 사용할 수 sum있으므로 sum즉시 작업을 시작할 수 있으며 값이 생성 될 때 gc'd 될 수 있습니다. 와 같은 융합 프레임 워크를 사용 vector하면 중간 목록조차도 융합 될 수 있습니다.

이것을 foldl함수와 대조하십시오 .

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

이제 foldl완료 될 때까지 목록의 헤드를 사용할 수 없습니다 . 이는 전체 목록 sum이 작동을 시작 하기 전에 메모리에 구성되어야 함을 의미합니다 . 이것은 전반적으로 훨씬 덜 효율적입니다. 두 버전을 실행하면 +RTS -sfoldl 버전에서 비참한 가비지 수집 성능이 나타납니다.

이것은 또한 foldl'도움이되지 않는 경우 입니다. 추가 된 엄격함은 foldl'중간 목록이 생성되는 방식을 변경하지 않습니다. 목록의 헤드는 foldl '이 끝날 때까지 사용할 수 없으므로 결과는 여전히 foldr.

다음 규칙을 사용하여 최선의 선택을 결정합니다. fold

• 축소 된 접기의 경우 사용합니다 foldl'(예 : 이것이 유일한 / 최종 순회입니다).
• 그렇지 않으면 foldr.
• 사용하지 마십시오 foldl.

대부분의 경우 foldr순회 방향이 목록의 지연 평가에 최적이기 때문에 가장 좋은 접기 기능입니다. 또한 무한 목록을 처리 할 수있는 유일한 제품입니다. 의 추가 엄격함은 foldl'경우에 따라 더 빠르게 만들 수 있지만 이는 해당 구조를 사용하는 방법과 게으른 정도에 따라 다릅니다.

---

나는 내가 뭔가를 놓치고 있지 않는 한 아직 누군가가 실제로 이것에 대한 진정한 대답을 말했다고 생각하지 않는다.

이 경우 가장 큰 차이점은 다음 foldr과 같이 목록 을 작성한다는 것입니다.

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

반면 foldl다음과 같이 목록을 작성합니다.

((([0] ++ [1]) ++ [2]) ++ ...) ++ [999888]) ++ [999999]) ++ [1000000]

The difference in subtle, but notice that in the foldr version ++ always has only one list element as its left argument. With the foldl version, there are up to 999999 elements in ++'s left argument (on average around 500000), but only one element in the right argument.

However, ++ takes time proportional to the size of the left argument, as it has to look though the entire left argument list to the end and then repoint that last element to the first element of the right argument (at best, perhaps it actually needs to do a copy). The right argument list is unchanged, so it doesn't matter how big it is.

That's why the foldl version is much slower. It's got nothing to do with laziness in my opinion.

---

The problem is that tail recursion optimization is a memory optimization, not a execution time optimization!

Tail recursion optimization avoids the need to remember values for each recursive call.

So, foldl is in fact "good" and foldr is "bad".

For example, considering the definitions of foldr and foldl:

foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

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

That's how the expression "foldl (+) 0 [1,2,3]" is evaluated:

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

Note that foldl doesn't remember the values 0, 1, 2..., but pass the whole expression (((0+1)+2)+3) as argument lazily and don't evaluates it until the last evaluation of foldl, where it reaches the base case and returns the value passed as the second parameter (z) wich isn't evaluated yet.

On the other hand, that's how foldr works:

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

The important difference here is that where foldl evaluates the whole expression in the last call, avoiding the need to come back to reach remembered values, foldr no. foldr remember one integer for each call and performs a addition in each call.

Is important to bear in mind that foldr and foldl are not always equivalents. For instance, try to compute this expressions in hugs:

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

foldr and foldl are equivalent only under certain conditions described here

(sorry for my bad english)

---

For a, the [0.. 100000] list needs to be expanded right away so that foldr can start with the last element. Then as it folds things together, the intermediate results are

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

Because nobody is allowed to change this list value (Haskell is a pure functional language), the compiler is free to reuse the value. The intermediate values, like [99999, 100000] can even be simply pointers into the expanded [0.. 100000] list instead of separate lists.

For b, look at the intermediate values:

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

Each of those intermediate lists can't be reused, because if you change the end of the list then you've changed any other values that point to it. So you're creating a bunch of extra lists that take time to build in memory. So in this case you spend a lot more time allocating and filling in these lists that are intermediate values.

Since you're just making a copy of the list, a runs faster because it starts by expanding the full list and then just keeps moving a pointer from the back of the list to the front.

---

Neither foldl nor foldr is tail optimized. It is only foldl'.

But in your case using ++ with foldl' is not good idea because successive evaluation of ++ will cause traversing growing accumulator again and again.

---

Well, let me rewrite your functions in a way that difference should be obvious -

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

You see that b is more complex than a. If you want to be precise a needs one reduction step for value to be calculated, but b needs two. That makes the time difference you are measuring, in second example twice as much reductions must be performed.

//edit: But time complexity is the same, so I wouldn't bother about it much.

참고URL : https://stackoverflow.com/questions/3429634/foldl-is-tail-recursive-so-how-come-foldr-runs-faster-than-foldl