무한 목록이있는 폴더 대 폴더 동작

무한 목록이있는 폴더 대 폴더 동작

---

이 질문 에서 myAny 함수의 코드 는 foldr를 사용합니다. 술어가 만족되면 무한리스트 처리를 중지합니다.

foldl을 사용하여 다시 작성했습니다.

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(단계 함수에 대한 인수는 올바르게 반대입니다.)

그러나 더 이상 무한 목록 처리를 중지하지 않습니다.

Apocalisp의 답변 에서와 같이 함수의 실행을 추적하려고했습니다 .

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

그러나 이것은 기능이 작동하는 방식이 아닙니다. 이게 어때?

---

방법 fold의이 다른 것은 그래서 여기보다 일반적인 개요입니다, 혼란의 빈번한 원인이 될 것 같다 :

[x1, x2, x3, x4 ... xn ]일부 함수 f와 seed 로 n 값 목록을 접는 것을 고려하십시오 z.

foldl 입니다 :

• 왼쪽 연관 :f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• 꼬리 재귀 : 목록을 반복하여 나중에 값을 생성합니다.
• 게으른 : 결과가 필요할 때까지 아무것도 평가되지 않습니다.
• 뒤로 : foldl (flip (:)) []리스트를 반대로합니다.

foldr 입니다 :

• 올바른 연관성 :f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• 인수로 재귀 : 각 반복 f은 다음 값과 나머지 목록을 접은 결과에 적용됩니다 .
• 게으른 : 결과가 필요할 때까지 아무것도 평가되지 않습니다.
• 전달 : foldr (:) []변경되지 않은 목록을 반환합니다.

약간 미묘한 점은 여기에있다 가끔 여행 사람들까지 그 : 때문에 foldl입니다 뒤쪽 의 각 응용 프로그램 f받는 추가 외부 결과; 게으 르기 때문에 결과가 필요할 때까지 아무것도 평가되지 않습니다. 즉, 결과의 일부를 계산하기 위해 Haskell은 먼저 전체 목록을 반복하여 중첩 함수 응용 프로그램의 표현식을 구성한 다음 가장 바깥 쪽 함수를 평가하고 필요에 따라 인수를 평가합니다. f항상 첫 번째 인수를 사용하는 경우 이는 Haskell이 가장 안쪽까지 내려 가서의 각 응용 프로그램을 거꾸로 계산해야한다는 것을 의미 f합니다.

이것은 대부분의 기능 프로그래머가 알고 사랑하는 효율적인 꼬리 재귀와는 거리가 멀다!

실제로 foldl기술적으로 꼬리 재귀 적이 지만 , 결과를 평가하기 전에 전체 결과 표현식이 작성 foldl되므로 스택 오버플로가 발생할 수 있습니다!

반면에을 고려하십시오 foldr. 또한 게으르지 만 앞으로 실행되기 때문에 각 응용 프로그램 이 결과 내부 에 f추가됩니다 . 따라서 결과를 계산하기 위해 Haskell은 단일 함수 응용 프로그램을 구성합니다. 두 번째 인수는 접힌 목록의 나머지 부분입니다. 경우 데이터 생성자, 인스턴스 - - 두번째 인수 지연되는 결과가 될 것이다 증분 지연 계산할 접어서 각각의 단계, 때만 평가된다 필요로하는 결과의 일부.f

So we can see why foldr sometimes works on infinite lists when foldl doesn't: The former can lazily convert an infinite list into another lazy infinite data structure, whereas the latter must inspect the entire list to generate any part of the result. On the other hand, foldr with a function that needs both arguments immediately, such as (+), works (or rather, doesn't work) much like foldl, building a huge expression before evaluating it.

So the two important points to note are these:

• foldr can transform one lazy recursive data structure into another.
• Otherwise, lazy folds will crash with a stack overflow on large or infinite lists.

You may have noticed that it sounds like foldr can do everything foldl can, plus more. This is true! In fact, foldl is nearly useless!

But what if we want to produce a non-lazy result by folding over a large (but not infinite) list? For this, we want a strict fold, which the standard libraries thoughfully provide:

foldl' is:

• Left associative: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Tail recursive: It iterates through the list, producing the value afterwards
• Strict: Each function application is evaluated along the way
• Backwards: foldl' (flip (:)) [] reverses a list.

Because foldl' is strict, to compute the result Haskell will evaluate f at each step, instead of letting the left argument accumulate a huge, unevaluated expression. This gives us the usual, efficient tail recursion we want! In other words:

• foldl' can fold large lists efficiently.
• foldl' will hang in an infinite loop (not cause a stack overflow) on an infinite list.

The Haskell wiki has a page discussing this, as well.

---

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

etc.

Intuitively, foldl is always on the "outside" or on the "left" so it gets expanded first. Ad infinitum.

---

You can see in Haskell's documentation here that foldl is tail-recursive and will never end if passed an infinite list, since it calls itself on the next parameter before returning a value...

---

I dont know Haskell, but in Scheme, fold-right will always 'act' on the last element of a list first. Thus is will not work for cyclic list (which is the same as an infinite one).

I am not sure if fold-right can be written tail-recursive, but for any cyclic list you should get a stack overflow. fold-left OTOH is normally implemented with tail recursion, and will just get stuck in an infinite loop, if not terminating it early.

참고URL : https://stackoverflow.com/questions/3082324/foldl-versus-foldr-behavior-with-infinite-lists