무한 목록에 대한 왼쪽 및 오른쪽 접기

무한 목록에 대한 왼쪽 및 오른쪽 접기

---

Learn You A Haskell (Great book imo, not dissing it) 의 다음 구절에 문제가 있습니다 .

한 가지 큰 차이점은 오른쪽 접기는 무한 목록에서 작동하는 반면 왼쪽 접기는 작동하지 않는다는 것입니다! 명확하게 말하면, 어떤 지점에서 무한 목록을 가져 와서 오른쪽에서 접 으면 결국 목록의 시작 부분에 도달하게됩니다. 그러나 한 지점에서 무한 목록을 가져 와서 왼쪽에서 접 으려고하면 끝이 없습니다!

나는 이것을 이해하지 못한다. 무한한 목록을 가져 와서 오른쪽에서 접 으려고하면 무한대 지점에서 시작해야합니다. 이것은 일어나지 않습니다. (누군가이 작업을 수행 할 수있는 언어를 알고 있다면 다음과 같이 말하십시오. ). 적어도 Haskell의 구현에 따라 시작해야합니다. Haskell foldr 및 foldl에서는 목록에서 접기를 시작해야하는 위치를 결정하는 인수를 취하지 않기 때문입니다.

foldr과 foldl이 목록에서 접기를 시작할 위치를 결정하는 인수를 취했다면 따옴표에 동의 할 것입니다. 무한 목록을 가져와 정의 된 색인에서 바로 접기를 시작 하면 결국 종료되지만 그렇지 않은 경우 왼쪽 접기로 시작하는 곳은 중요하지 않습니다. 무한대로 접을 것입니다. 그러나 foldr 및 foldl은 하지 않습니다 이 인수를 가지고, 따라서 견적 이해되지 않는다. Haskell에서 무한 목록에 대한 왼쪽 접기와 오른쪽 접기 모두 종료되지 않습니다 .

내 이해가 정확합니까 아니면 내가 뭔가를 놓치고 있습니까?

---

여기서 핵심은 게으름입니다. 목록 접기에 사용하는 함수가 엄격하다면 무한 목록이 주어지면 왼쪽 접기도 오른쪽 접기도 종료되지 않습니다.

Prelude> foldr (+) 0 [1..]
^CInterrupted.

그러나 덜 엄격한 함수를 폴딩하려고하면 종료 결과를 얻을 수 있습니다.

Prelude> foldr (\x y -> x) 0 [1..]
1

무한한 데이터 구조의 결과를 얻을 수도 있으므로 어떤 의미에서는 종료되지 않지만 느리게 소비 될 수있는 결과를 생성 할 수 있습니다.

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

그러나 foldllazy 여부에 관계없이 가장 바깥 쪽의 함수 호출을 평가할 수 없으므로에서는 작동 하지 않습니다.

Prelude> foldl (flip (:)) [] [1..]
^CInterrupted.
Prelude> foldl (\x y -> y) 0 [1..]
^CInterrupted.

왼쪽 및 오른쪽 접기의 주요 차이점은 목록이 항상 왼쪽에서 오른쪽으로 순회되는 순서가 아니라 결과 함수 응용 프로그램이 중첩되는 방식입니다.

• 를 사용하면 foldr"내부"에 중첩됩니다.

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

  여기에서 첫 번째 반복은 f. 따라서 f두 번째 인수가 항상 평가되지 않거나 두 번째 인수를 강요하지 않고 데이터 구조의 일부를 생성 할 수 있도록 지연 될 수 있습니다.

• 를 사용하면 foldl"외부"에 중첩됩니다.

  foldl f y (x:xs) = foldl f (f y x) xs
  

  여기에서 가장 바깥 쪽 응용 프로그램에 도달 할 때까지 아무것도 평가할 수 없으며 f, f엄격 여부에 관계없이 무한 목록의 경우에는 도달 하지 않습니다.

---

핵심 문구는 "어떤 지점에서"입니다.

어떤 지점에서 무한 목록을 가져 와서 오른쪽에서 접 으면 결국 목록의 시작 부분에 도달하게됩니다.

그래서 당신 말이 맞습니다. 당신은 무한 목록의 "마지막"요소에서 시작할 수 없습니다. 그러나 저자의 요점은 이것이다 : 당신이 할 수 있다고 가정하자. 멀리 떨어진 지점을 선택하고 (엔지니어에게는 무한대에 "충분히 가까움") 왼쪽으로 접기 시작합니다. 결국 당신은 목록의 시작 부분에서 끝납니다. 왼쪽 폴드의 경우도 마찬가지입니다. 만약 당신이 거기에있는 포인트 waaaay를 선택하고 (그리고 그것을 목록의 시작 부분에 "충분히 가깝게"라고 부르는) 오른쪽으로 폴드하기 시작한다면, 당신은 여전히 ​​무한한 방법을 가지고 있습니다.

그래서 비결은 때로는 무한대로 갈 필요가 없다는 것입니다. 거기 밖으로 waaaay 갈 필요조차 없습니다. 그러나 사전에 얼마나 멀리 가야하는지 모를 수도 있습니다.이 경우 무한 목록이 매우 편리합니다.

간단한 그림은 foldr (:) [] [1..]입니다. 접기를 수행합시다.

그 foldr f z (x:xs) = f x (foldr f z xs). 무한 목록에서는 실제로 무엇이 중요하지 않으므로 그림을 어수선하게 만드는 대신 z유지하고 있습니다.z[]

foldr (:) z (1:[2..])         ==> (:) 1 (foldr (:) z [2..])
1 : foldr (:) z (2:[3..])     ==> 1 : (:) 2 (foldr (:) z [3..])
1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..])
1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] )

방법을 참조하십시오 foldr이론적에서 배에도 불구하고, 바로 이 경우 실제로에서 시작하여 결과 목록의 개별 요소를 크랭크에, 왼쪽 ? 따라서이 take 3목록 [1,2,3]에서 폴드 를 생성 할 수 있으며 더 이상 폴드를 평가할 필요가 없음 을 분명히 알 수 있습니다 .

---

Haskell에서는 지연 평가로 인해 무한 목록을 사용할 수 있음을 기억하십시오. 그래서, head [1..]단지 1이고, head $ map (+1) [1..]`[1 ..]이 무한히 길어도 2입니다. 당신이 그것을 얻지 못한다면, 잠시 멈추고 그것을 가지고 놀아 라. 당신이 그것을 얻으면 계속 읽으십시오 ...

나는 당신의 혼란의 부분이 있다고 생각 foldl하고 foldr, 따라서 당신이 길이를 줄 필요가 해달라고 항상 한쪽으로 시작한다.

foldr 매우 간단한 정의가 있습니다

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

이것이 무한 목록에서 종료되는 이유는 무엇입니까?

 dumbFunc :: a -> b -> String
 dumbFunc _ _ = "always returns the same string"
 testFold = foldr dumbFunc 0 [1..]

여기서 우리 foldr는 ""(값은 중요하지 않기 때문에)와 무한한 자연수 목록을 전달합니다. 종료됩니까? 예.

그것이 종료되는 이유는 Haskell의 평가가 게으른 용어 재 작성과 동일하기 때문입니다.

그래서

 testFold = foldr dumbFunc "" [1..]

(패턴 일치를 허용하기 위해)

 testFold = foldr dumbFunc "" (1:[2..])

이것은 (폴드의 정의에서)

 testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]

이제 정의에 의해 dumbFunc결론을 내릴 수 있습니다

 testFold = "always returns the same string"

이것은 무언가를하는 함수가있을 때 더 흥미롭지 만 때때로 게으르다. 예를 들면

foldr (||) False 

is used to find if a list contains any True elements. We can use this to define the higher order functionn any which returns True if and only if the passed in function is true for some element of the list

any :: (a -> Bool) -> [a] -> Bool
any f = (foldr (||) False) . (map f)

The nice thing about lazy evaluation, is that this will stop when it encounters the first element e such that f e == True

On the other hand, this isn't true of foldl. Why? Well a really simple foldl looks like

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

Now, what would have happened if we tried our example above

testFold' = foldl dumbFunc "" [1..]
testFold' = foldl dumbFunc "" (1:[2..])

this now becomes:

testFold' = foldl dumbFunc (dumbFunc "" 1) [2..]

so

testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]

and so on and so on. We can never get anywhere, because Haskell always evaluates the outermost function first (that is lazy evaluation in a nutshell).

One cool consequence of this is that you can implement foldl out of foldr but not vice versa. This means that in some profound way foldr is the most fundamental of all the higher order string functions, since it is the one we use to implement almost all the others. You still might want to use a foldl sometimes, because you can implement foldl tail recursively, and get some performance gain from that.

---

There is good plain explanation on Haskell wiki. It shows step-by-step reduction with different types of fold and accumulator functions.

---

Your understanding is correct. I wonder if the author is trying to talk about Haskell's lazy evaluation system (in which you can pass an infinite list to various functions not including fold, and it will only evaluate however much is needed to return the answer). but I agree with you that the author isn't doing a good job describing anything in that paragraph, and what it says is wrong.

참고URL : https://stackoverflow.com/questions/7396978/left-and-right-folding-over-an-infinite-list