foldr hoạt động như thế nào?

Question

Ai đó có thể giải thích cách hoạt động của foldr?

Thực hiện các ví dụ:

Prelude> foldr (-) 54 [10, 11] 
53 
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6] 
12.0 

Tôi đang bối rối về những hành. Bất kỳ đề xuất?

Answer 1

foldr bắt đầu ở cuối bên phải của danh sách và kết hợp từng mục nhập danh sách với giá trị bộ tích lũy bằng cách sử dụng chức năng bạn cung cấp. Kết quả là giá trị cuối cùng của bộ tích lũy sau khi "gấp" trong tất cả các phần tử danh sách. loại của nó là:

foldr :: (a -> b -> b) -> b -> [a] -> b 

và từ đây bạn có thể thấy rằng các yếu tố danh sách (loại a) là đối số đầu tiên với chức năng nhất định, và ác quy (loại b) là lần thứ hai.

Ví dụ đầu tiên của bạn:

Starting accumulator = 54 
11 - 54 = -43 
10 - (-43) = 53 

     ^Result from the previous line 

^ Next list item 

Vì vậy, câu trả lời bạn nhận được là 53.

Ví dụ thứ hai:

Starting accumulator = 54 
(6 + 54)/2 = 30 
(10 + 30)/2 = 20 
(4 + 20)/2 = 12 
(12 + 12)/2 = 12 

Vì vậy, kết quả là 12.

Sửa : Tôi muốn thêm vào, đó là danh sách hữu hạn. foldr cũng có thể hoạt động trên các danh sách vô hạn nhưng tốt nhất là nên để đầu của bạn xung quanh trường hợp hữu hạn trước tiên, tôi nghĩ vậy.

Answer 2

foldr nghĩa là lần từ bên phải, vì vậy foldr (-) 0 [1, 2, 3] sản xuất (1 - (2 - (3 - 0))). So sánh foldl sản xuất (((0 - 1) - 2) - 3).

Khi nhà khai thác không phải là commutativefoldl và foldr sẽ nhận được kết quả khác.

Trong trường hợp của bạn, ví dụ đầu tiên mở rộng để (10 - (11 - 54)) mang đến cho 53.

Answer 3

Hãy suy nghĩ về foldr 's rất definition:

-- if the list is empty, the result is the initial value z 
foldr f z []  = z     
-- if not, apply f to the first element and the result of folding the rest 
foldr f z (x:xs) = f x (foldr f z xs) 

Vì vậy, ví dụ foldr (-) 54 [10,11] phải bằng (-) 10 (foldr (-) 54 [11]), tức là mở rộng một lần nữa, tương đương (-) 10 ((-) 11 54). Vì vậy, hoạt động bên trong là 11 - 54, tức là -43; và hoạt động bên ngoài là 10 - (-43), tức là, 10 + 43, do đó, 53 khi bạn quan sát. Thực hiện các bước tương tự cho trường hợp thứ hai của bạn và một lần nữa bạn sẽ thấy các biểu mẫu kết quả như thế nào!

Answer 4

Tôi luôn nghĩ rằng http://foldr.com là một minh họa thú vị. Xem bài đăng Lambda the Ultimate.

Answer 5

Cách dễ nhất để hiểu foldr là viết lại danh sách bạn đang gấp mà không cần đường.

[1,2,3,4,5] => 1:(2:(3:(4:(5:[])))) 

bây giờ những gì foldr f x không là nó thay thế mỗi : với f ở dạng trung tố và [] với x và đánh giá kết quả.

Ví dụ:

sum [1,2,3] = foldr (+) 0 [1,2,3] 

[1,2,3] === 1:(2:(3:[])) 

nên

sum [1,2,3] === 1+(2+(3+0)) = 6 

Answer 6

Một cách dễ dàng để hiểu foldr là thế này: Nó thay thế tất cả các nhà xây dựng danh sách với một ứng dụng của hàm được cung cấp. Ví dụ đầu tiên của bạn sẽ dịch để:

10 - (11 - 54)

từ:

10 : (11 : [])

Một mảnh tốt lời khuyên mà tôi nhận được từ các Haskell Wikibook có thể sử dụng một số ở đây:

Theo quy tắc, bạn nên sử dụng foldr trên danh sách có thể là vô hạn hoặc nơi nếp gấp đang xây dựng cấu trúc dữ liệu và foldl' nếu danh sách được xác định là hữu hạn và đi xuống một giá trị duy nhất. foldl (không có dấu) hiếm khi được sử dụng.

Answer 7

Giúp hiểu sự khác biệt giữa foldr và foldl. Tại sao là foldr được gọi là "gấp bên phải"?

Ban đầu tôi nghĩ đó là vì nó tiêu thụ các phần tử từ phải sang trái. Tuy nhiên, cả hai số foldr và foldl đều sử dụng danh sách từ trái sang phải.

• foldlđánh giá từ trái sang phải (trái kết hợp)
• foldrđánh giá từ phải sang trái (phải kết hợp)

Chúng tôi có thể làm cho sự khác biệt này rõ ràng với một ví dụ sử dụng toán tử cho các vấn đề liên quan. Chúng ta có thể sử dụng một tấm gương con người, chẳng hạn như các nhà điều hành, "ngốn":

foodChain = (human : (shark : (fish : (algae : [])))) 

foldl step [] foodChain 
    where step eater food = eater `eats` food -- note that "eater" is the accumulator and "food" is the element 

foldl `eats` [] (human : (shark : (fish : (algae : [])))) 
    == foldl eats (human `eats` shark)        (fish : (algae : [])) 
    == foldl eats ((human `eats` shark) `eats` fish)    (algae : []) 
    == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) [] 
    ==   (((human `eats` shark) `eats` fish) `eats` algae) 

Ngữ nghĩa của foldl này là: Một con người ăn một số cá mập, và sau đó là con người cùng những người đã ăn cá mập sau đó ăn một số loài cá, vv Người ăn là người tích lũy.

Contrast này với:

foldr step [] foodChain 
    where step food eater = eater `eats` food. -- note that "eater" is the element and "food" is the accumulator 

foldr `eats` [] (human : (shark : (fish : (algae : [])))) 
    == foldr eats (human `eats` shark)        (fish : (algae : [])))) 
    == foldr eats (human `eats` (shark `eats` (fish))    (algae : []) 
    == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) [] 
    ==   (human `eats` (shark `eats` (fish `eats` algae) 

Ngữ nghĩa của foldr này là: Một con người ăn một con cá mập mà đã ăn một con cá, mà đã ăn một số tảo. Thức ăn là bộ tích lũy.

Cả hai foldl và foldr "bóc vỏ" người ăn từ trái sang phải, vì vậy đó không phải là lý do chúng tôi gọi gấp nếp là "gấp trái". Thay vào đó, thứ tự của các vấn đề đánh giá.

Answer 8

Ok, cho phép xem xét các đối số:

• một chức năng (mà phải mất một yếu tố danh sách và một giá trị (do một phần có thể) của cùng một loại giá trị của nó);
• đặc điểm kỹ thuật của kết quả ban đầu cho trường hợp đặc biệt danh sách trống
• danh sách;

giá trị trả về:

• một số kết quả cuối cùng

Nó đầu tiên áp dụng các chức năng để yếu tố cuối cùng trong danh sách và kết quả danh sách trống. Sau đó nó áp dụng lại hàm với kết quả này và phần tử trước đó, và cứ thế cho đến khi nó lấy một số kết quả hiện tại và phần tử đầu tiên của danh sách trả về kết quả cuối cùng.

Gấp "gấp" danh sách xung quanh kết quả ban đầu bằng cách sử dụng hàm lấy phần tử và một số kết quả xếp trước đó. Nó lặp lại điều này cho mỗi phần tử. Vì vậy, foldr làm điều này bắt đầu ở cuối danh sách, hoặc phía bên phải của nó.

folr f emptyresult [1,2,3,4] chuyển thành f(1, f(2, f(3, f(4, emptyresult)))). Bây giờ chỉ cần làm theo dấu ngoặc đơn trong đánh giá và đó là nó.

Một điều quan trọng cần lưu ý là hàm được cung cấp f phải xử lý giá trị trả về của chính nó làm đối số thứ hai ngụ ý cả hai phải có cùng loại.

Nguồn: my post nơi tôi xem xét từ góc độ javascript bắt buộc chưa được kiểm tra nếu bạn cho rằng nó có thể hữu ích.

Answer 9

Tôi nghĩ rằng việc triển khai bản đồ, gấp nếp và nếp gấp theo cách đơn giản giúp giải thích cách hoạt động của bản đồ. Ví dụ làm việc cũng hỗ trợ trong sự hiểu biết của chúng tôi.

myMap f [] = [] 
    myMap f (x:xs) = f x : myMap f xs 

    myFoldL f i [] = i 
    myFoldL f i (x:xs) = myFoldL f (f i x) xs 

    > tail [1,2,3,4] ==> [2,3,4] 
    > last [1,2,3,4] ==> 4 
    > head [1,2,3,4] ==> 1 
    > init [1,2,3,4] ==> [1,2,3] 

    -- where f is a function, 
    -- acc is an accumulator which is given initially 
    -- l is a list. 
    -- 
    myFoldR' f acc [] = acc 
    myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l) 

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

    > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] 
    > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] 

    > foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 
    > myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 

    foldl from above: Starting accumulator = 54 
     (12 + 54)/2 = 33 
     (4 + 33)/2 = 18.5 
     (10 + 18.5)/2 = 14.25 
     (6 + 14.25)/2 = 10.125` 

> foldr (++) "5" ["1", "2", "3", "4"] ==> "12345" 

> foldl (++) "5" ["1", "2", "3", "4"] ==> “51234" 

> foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 
> myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 
> myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 

    foldr from above: Starting accumulator = 54 
     (6 + 54)/2 = 30 
     (10 + 30)/2 = 20 
     (4 + 20)/2 = 12 
     (12 + 12)/2 = 12