nếp gấp. thành phần chức năng foldr - Haskell

Question

Vì vậy, tôi đang thực sự chiên não của tôi cố gắng để hiểu các thành phần foldl.foldr. Dưới đây là ví dụ:

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

Kết quả là 22, nhưng điều gì thực sự xảy ra ở đây?

Với tôi, có vẻ như đây là những gì đang diễn ra: foldl (+) 1 [6,15]. Nghi ngờ của tôi liên quan đến phần foldr. Không nên thêm 1 vào tất cả các danh sách phụ? Như thế này: foldr (+) 1 [1,2,3]. Trong đầu của tôi, 1 được thêm vào chỉ một lần, đúng không? (có lẽ không, nhưng tôi muốn biết làm thế nào/tại sao!).

Tôi rất bối rối (và có thể làm mọi sự nhầm lẫn, haha). Cảm ơn bạn!

Answer 1

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

trở thành

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

Vì vậy, bạn sẽ có được

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

sau bước đầu tiên của foldl, hoặc

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

nếu chúng ta đánh giá áp dụng foldr (trừ trường hợp stric tness phân tích đá tại, nó sẽ trong thực tế vẫn là một thunk unevaluated cho đến khi foldl đã đi qua toàn bộ danh sách, nhưng các biểu hiện tiếp theo là dễ đọc hơn với nó đánh giá), và điều đó trở thành

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

và cuối cùng

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

Answer 2

Hãy kiểm tra foldl . foldr. Các loại của chúng là

Tôi cố ý sử dụng các biến kiểu riêng biệt và thêm dấu ngoặc Nhìn vào foldl chúng ta thấy rằng nó là một loại chức năng nâng: Với một chức năng sản xuất a từ a sử dụng b, chúng tôi nhấc nó lên để nó hoạt động trên [b] (bằng cách lặp lại tính toán). Chức năng foldr tương tự, chỉ với các đối số được đảo ngược.

Bây giờ điều gì xảy ra nếu chúng tôi áp dụng foldl . foldr? Đầu tiên, chúng ta hãy lấy được kiểu: Chúng ta phải hợp nhất các biến kiểu để kết quả của foldr khớp với đối số của foldl. Vì vậy, chúng ta phải thay thế: a = d, b = [c]:

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

Vì vậy, chúng tôi nhận

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

Và ý nghĩa của nó là gì? Trước tiên, foldr sẽ chuyển đối số của loại c -> d -> d để hoạt động trên danh sách và đảo ngược các đối số của chúng để chúng tôi nhận được d -> [c] -> d. Tiếp theo, foldl nâng chức năng này một lần nữa để hoạt động trên [[c]] - danh sách [c].

Trong trường hợp của bạn, thao tác đang được dỡ bỏ (+) là kết hợp, vì vậy chúng tôi không quan tâm đến thứ tự của ứng dụng của nó. Việc nâng đôi chỉ đơn giản là tạo ra một chức năng áp dụng các hoạt động trên tất cả các yếu tố lồng nhau.

Nếu chúng ta sử dụng chỉ foldl, hiệu quả là thậm chí đẹp hơn: Chúng tôi có thể nâng nhiều lần, giống như trong

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

Answer 3

Trên thực tế, (foldl.foldr) f z xs === foldr f z (concat $ reverse xs).

Ngay cả khi f là một hoạt động liên kết, trình tự chính xác của các ứng dụng quan trọng vì nó có thể có tác động đến hiệu suất.

Chúng tôi bắt đầu với

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

bằng văn bản với g = foldr f và [x1,x2,...,xn_1,xn] = xs trong một khoảnh khắc, đây là

(...((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 

Vì vậy, trong trường hợp của bạn chuỗi giảm đúng

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

Để wit ,

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

---

Tương tự, (foldl.foldl) f z xs == foldl f z $ concat xs. Với snoc a b = a++[b],

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

Ngoài ra, (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), v.v .:

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]