폴드. foldr 함수 구성 - Haskell

Question

그래서, 나는 foldl.foldr 합성을 이해하려고 노력하면서 내 뇌를 정말로 튀기고있다.

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

결과는 정말 여기에서 무슨 일이 일어나고 있는지 22 :하지만, 여기 은 예입니다?

제게 이것은 어떤 일이 일어나고있는 것처럼 보입니다 : foldl (+) 1 [6,15]. 의심의 여지가있는 부분은 foldr입니다. 1을 모든 하위 목록에 추가하면 안됩니까? 이렇게 : foldr (+) 1 [1,2,3]. 내 머리 속에는 1 번만 추가됩니다. 맞습니까? (아마 아니지만, 어떻게/왜 알고 싶다!).

나는 매우 혼란 스럽다. (아마도 모든 혼란을 일으킬 것이다, 하하). 감사합니다.

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

우리가 STRIC하지 않는 한 (적용 foldr을 평가하는 경우

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

그래서 당신이

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

foldl의 첫 번째 단계 이후

, 또는

foldl (foldr (+)) 7 [[4,5,6]] 

를 얻을된다 GNU General Public License를 분석기는 foldl 전체 목록을 통과 할 때까지, 그것은 현실에서, 평가되지 않은 썽크 남아있을에서 개막 있지만, 다음 표현은 평가) 더 읽을 수 있으며, 그

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) [] 

마지막

foldl (foldr (+)) 22 [] 
~> 22 

된다

Answer 2

foldl . foldr을 살펴 보겠습니다. 이들 유형은 내가 의도적으로 구별 유형 변수를 사용하고 우리가 (그리고 그 결과는 함수입니다) 하나 개의 인수의 함수로 지금 볼 것을 더 분명해집니다 있도록 내가 괄호를 추가

foldl :: (a -> b -> a) -> (a -> [b] -> a) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

있습니다. foldl을 보면, 이것은 일종의 리프팅 함수라는 것을 알 수 있습니다. a을 a에서 b으로 생성하는 함수가 주어지면 [b] (계산을 반복 함)에서 작동하도록 리프트합니다. 함수 foldr은 인수가 반대 인 경우와 비슷합니다.

이제 foldl . foldr을 적용하면 어떻게됩니까? 먼저 유형을 파생시켜 보겠습니다. foldr의 결과가 foldl의 인수와 일치하도록 형식 변수를 통합해야합니다. a = d, b = [c]을 : 그래서 우리는 대체해야

foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

그래서 우리가

foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d) 

얻을 그리고 그 의미는 무엇인가? 먼저 foldr은 c -> d -> d 유형의 인수를 목록에서 작동하도록 해제하고 인수를 반대로하여 d -> [c] -> d이되도록합니다. 다음으로 foldl은이 기능을 다시 실행하여 [[c]] - [c]의 목록을 처리합니다.

귀하의 경우에는 작동이 해제되고 (+)은 연관성이 있으므로 해당 주문 순서에주의하지 않아도됩니다. 더블 리프팅은 단순히 중첩 된 모든 요소에 연산을 적용하는 함수를 만듭니다. 우리가 foldl를 사용하는 경우

, 효과도 좋네요 : 우리는 사실

foldl . foldl . foldl . foldl 
    :: (a -> b -> a) -> (a -> [[[[b]]]] -> a) 

Answer 3

, (foldl.foldr) f z xs === foldr f z (concat $ reverse xs)에서와 같이, 여러 번 들어 올릴 수 있습니다.

f이 연관 작업 인 경우에도 성능에 영향을 줄 수 있으므로 정확한 응용 프로그램 순서가 중요합니다.

우리는

(foldl.foldr) f z xs 
foldl (foldr f) z xs 

가 잠시 g = foldr f 및 [x1,x2,...,xn_1,xn] = xs로 쓰는이 올바른 감소 순서가 귀하의 경우

(...((z `g` x1) `g` x2) ... `g` xn) 
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ...) 
foldr f z $ concat [xn,xn_1, ..., x1] 
foldr f z $ concat $ reverse xs 

그래서 재치으로

(foldl.foldr) 1 [[1,2,3],[4,5,6]] 
4+(5+(6+( 1+(2+(3+ 1))))) 
22 

입니다 시작 ,

마찬가지로 0

Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]] 
[7,8,4,5,6,1,2,3] 

---

, (foldl.foldl) f z xs == foldl f z $ concat xs. snoc a b = a++[b], 또한

Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]] 
[1,2,3,4,5,6,7,8] 

, (foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs) 등 :

Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[1,2,3,4,5,6,7,8] 
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,1,2,3,4,5,6] 
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,4,5,6,1,2,3]