foldr và gấp lại các giải thích và ví dụ khác

Question

Tôi đã xem different folds và folding in general cũng như một số khác và chúng giải thích rõ ràng.

Tôi vẫn gặp sự cố về cách lambda hoạt động trong trường hợp này.

foldr (\y ys -> ys ++ [y]) [] [1,2,3] 

Ai đó có thể đi qua từng bước đó và cố gắng giải thích điều đó cho tôi.

Và cũng làm cách nào foldl cũng hoạt động.

Answer 1

Sử dụng

foldr f z []  = z 
foldr f z (x:xs) = x `f` foldr f z xs 

Và

k y ys = ys ++ [y] 

Hãy giải nén:

foldr k [] [1,2,3] 
= k 1 (foldr k [] [2,3] 
= k 1 (k 2 (foldr k [] [3])) 
= k 1 (k 2 (k 3 (foldr k [] []))) 
= (k 2 (k 3 (foldr k [] []))) ++ [1] 
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1] 
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1] 
= ((([]) ++ [3]) ++ [2]) ++ [1] 
= (([3]) ++ [2]) ++ [1] 
= ([3,2]) ++ [1] 
= [3,2,1] 

Answer 2

Định nghĩa của foldr là:

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

Vì vậy, đây là một bước bằng cách giảm bước của ví dụ của bạn:

foldr (\y ys -> ys ++ [y]) [] [1,2,3] 
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3]) 
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1] 
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1] 
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1] 
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1] 
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1] 
= [] ++ [3] ++ [2] ++ [1] 
= [3,2,1] 

Answer 3

Infix ký hiệu có thể sẽ được rõ ràng hơn ở đây.

Hãy bắt đầu với định nghĩa:

foldr f z []  = z 
foldr f z (x:xs) = x `f` (foldr f z xs) 

Vì lợi ích ngắn gọn, chúng ta hãy viết g thay vì (\y ys -> ys ++ [y]). Các dòng sau là tương đương:

foldr g [] [1,2,3] 
1 `g` (foldr g [] [2,3]) 
1 `g` (2 `g` (foldr g [] [3])) 
1 `g` (2 `g` (3 `g` (foldr g [] []))) 
1 `g` (2 `g` (3 `g` [])) 
(2 `g` (3 `g` [])) ++ [1] 
(3 `g` []) ++ [2] ++ [1] 
[3] ++ [2] ++ [1] 
[3,2,1] 

Answer 4

foldr là một điều đơn giản:

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

Phải mất một chức năng mà là bằng cách nào đó tương tự như (:),

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

và một giá trị mà tương tự với danh sách trống [],

[] :: [a] 

và thay thế mỗi: và [] trong một số danh sách.

Nó trông như thế này:

foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e)) 

Bạn có thể tưởng tượng foldr như một số nhà máy đánh giá, quá:

f là quá trình chuyển đổi,

f :: input -> state -> state 

và e là trạng thái bắt đầu.

e :: state 

foldr (foldRIGHT) chạy máy trạng thái với chuyển tiếp f và trạng thái bắt đầu e trên danh sách đầu vào, bắt đầu từ đầu phải.Hãy tưởng tượng f trong ký hiệu infix như pacman đến từ-RIGHT.

foldl (foldLEFT) thực hiện tương tự từ LEFT, nhưng hàm chuyển tiếp, được viết bằng ký hiệu infix, lấy đối số đầu vào của nó từ phải. Vì vậy, máy tiêu thụ danh sách bắt đầu từ đầu bên trái. Pacman tiêu thụ danh sách từ LEFT với một miệng mở ở bên phải, vì miệng (b-> a-> b) thay vì (a-> b-> b).

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

Để làm sáng tỏ này, hãy tưởng tượng chức năng trừ như chuyển tiếp:

foldl (-) 100 [1]   = 99 = ((100)-1) 
foldl (-) 100 [1,2]  = 97 = ((99)-2) = (((100)-1)-2) 
foldl (-) 100 [1,2,3]  = 94 = ((97)-3) 
foldl (-) 100 [1,2,3,4] = 90 = ((94)-4) 
foldl (-) 100 [1,2,3,4,5] = 85 = ((90)-5) 

foldr (-) 100 [1]   = -99 = (1-(100)) 
foldr (-) 100 [2,1]  = 101 = (2-(-99)) = (2-(1-(100))) 
foldr (-) 100 [3,2,1]  = -98 = (3-(101)) 
foldr (-) 100 [4,3,2,1] = 102 = (4-(-98)) 
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102)) 

Bạn có thể muốn sử dụng foldr trong tình huống này, khi danh sách có thể là vô hạn, và nơi mà các đánh giá cần được lười biếng:

foldr (either (\l (ls,rs)->(l:ls,rs)) 
       (\r (ls,rs)->(ls,r:rs)) 
    ) ([],[]) :: [Either l r]->([l],[r]) 

Và bạn có thể muốn sử dụng phiên bản nghiêm ngặt của nếp gấp, gấp nếp ', khi bạn tiêu thụ toàn bộ danh sách để tạo đầu ra. Nó có thể thực hiện tốt hơn và có thể khiến bạn phải ngăn xếp tràn hoặc ngoại lệ out-of-bộ nhớ (tùy thuộc vào trình biên dịch) do danh sách dài cực kết hợp với đánh giá lười biếng:

foldl' (+) 0 [1..100000000] = 5000000050000000 
foldl (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci 
foldr (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci 

Một -step đầu tiên bước - tạo một mục trong danh sách, đánh giá nó và tiêu thụ nó.

Công thức thứ hai tạo công thức rất dài trước, lãng phí bộ nhớ bằng ((... ((0 + 1) +2) +3) + ...) và đánh giá tất cả sau đó.

Kiểu thứ ba như thứ hai, nhưng với công thức khác.