foldr của haskell luôn luôn có một lambda hai tham số?

Question

Haskell newb đây

Tôi đang làm việc về vấn đề này trong Haskell:

(**) Eliminate consecutive duplicates of list elements. 
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed. 

Example: 
* (compress '(a a a a b c c a a d e e e e)) 
(A B C A D E) 

Giải pháp (mà tôi phải bất lực nhìn lên) sử dụng foldr:

compress' :: (Eq a) => [a] -> [a] 
compress' xs = foldr (\x acc -> if x == (head acc) then acc else x:acc) [last xs] xs 

foldr này, theo với giải pháp, có hai tham số, x và acc. Có vẻ như tất cả các foldr đều có những tham số này; có ngoại lệ nào cho điều này không? Giống như một foldr mất 3 hoặc nhiều hơn? Nếu không, quy ước này có dư thừa và công thức có thể được viết với ít mã hơn không?

Answer 1

foldr có chức năng 2 đối số, nhưng điều này không ngăn cản chức năng của 3 đối số được cung cấp chức năng có chữ ký loại phù hợp.

Nếu chúng ta có một hàm

g :: x -> y -> z -> w 

Với

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

đâu chúng ta muốn vượt qua g-foldr, sau đó (a -> b -> b) ~ (x -> y -> z -> w) (nơi ~ là gõ bình đẳng). Kể từ -> là kết hợp đúng, điều này có nghĩa là chúng ta có thể viết chữ ký g 's như

x -> y -> (z -> w) 

và ý nghĩa của nó là như nhau. Bây giờ chúng ta đã tạo ra một hàm của hai tham số trả về một hàm của một tham số.Để thống nhất điều này với các loại a -> b -> b, chúng ta chỉ cần xếp hàng các đối số:

a -> | x -> 
b -> | y -> 
b  | (z -> w) 

Điều này có nghĩa rằng b ~ z -> w, vì vậy y ~ b ~ z -> w và a ~ x nên g 's loại thực sự có được

g :: x -> (z -> w) -> (z -> w) 

ngụ ý

foldr g :: (z -> w) -> [x] -> (z -> w) 

Điều này chắc chắn là không thể, mặc dù khó xảy ra hơn. ắc chúng tôi là một chức năng thay vào đó, và với tôi đây cầu xin được chứng minh với DiffLists:

type DiffList a = [a] -> [a] 

append :: a -> DiffList a -> DiffList a 
append x dl = \xs -> dl xs ++ [x] 

reverse' :: [a] -> [a] 
reverse' xs = foldr append (const []) xs $ [] 

Lưu ý rằng foldr append (const []) xs trả về một chức năng mà chúng tôi áp dụng cho [] để đảo ngược một danh sách. Trong trường hợp này chúng tôi đã đưa ra một bí danh cho các chức năng của các loại [a] -> [a] gọi DiffList, nhưng nó thực sự không có khác biệt so với khi viết

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

mà là một chức năng của 3 đối số.

Answer 2

Như với tất cả mọi thứ trong haskell, hãy xem các loại để hướng dẫn bạn có thể thực hiện việc này cho bất kỳ chức năng nào trong ghci.

Nhìn vào này cho foldr chúng ta thấy:

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

Chuỗi hơi trừu tượng có thể được viết bằng tiếng Anh như:

foldr là một chức năng mà sẽ đưa

1) một chức năng với hai thông số một loại a và một loại b và trả về một loại nào đó b

.210

2) Một giá trị của loại b

3) Một danh sách các giá trị của loại a

Và trả về một giá trị kiểu b

đâu a và b là loại biến (xem here cho tốt hướng dẫn về chúng) có thể được điền bằng bất kỳ loại nào bạn thích.

Answer 3

Nó chỉ ra rằng bạn có thể giải quyết vấn đề compress của bạn bằng cách sử dụng một foldr với chức năng ba đối số.

compress :: Eq a => [a] -> [a] 
compress [] = [] 
compress (z:zs) = z : foldr f (const []) zs z 
    where f x k w | x==w  = k x 
       | otherwise = x : k x 

Hãy phân tích điều đó. Trước tiên, chúng tôi có thể cải thiện khả năng đọc bằng cách thay đổi hai dòng cuối cùng thành

where f x k = \w -> if x==w then k x else x : k x 

Điều này cho thấy chức năng nhị phân không có gì ngoài chức năng nhị phân trả về hàm đơn nhất. Lợi thế của việc xem xét nó theo cách này là foldr được hiểu rõ nhất khi truyền một hàm nhị phân. Thật vậy, chúng tôi là chuyển một hàm nhị phân, chức năng này chỉ xảy ra để trả về một hàm.

Hãy tập trung vào các loại bây giờ:

f :: a -> (a -> [a]) -> (a -> [a]) 
f x k 

Vì vậy, x::a là yếu tố của danh sách chúng tôi đang gấp trên. Chức năng k là kết quả của nếp gấp trên đuôi danh sách. Kết quả của f x k là thứ có cùng loại với k.

\w -> if .... :: (a -> [a]) 

Ý tưởng tổng thể đằng sau hàm ẩn danh này như sau. Tham số k đóng vai trò giống như acc trong mã OP, ngoại trừ nó là hàm mong đợi trước đó phần tử w trong danh sách trước khi tạo danh sách được nén tích lũy.

Cụ thể, chúng tôi sử dụng k x khi chúng tôi sử dụng acc, chuyển phần tử hiện tại sang bước tiếp theo, kể từ thời điểm đó x sẽ trở thành phần tử trước w. Ở cấp cao nhất, chúng tôi vượt qua z đến chức năng được trả về bởi foldr f (const []).

Biến thể compress này lười, không giống như giải pháp được đăng.Trong thực tế, giải pháp đã đăng cần phải quét toàn bộ danh sách trước khi bắt đầu sản xuất một cái gì đó: điều này là do (\x acc -> ...) bị nghiêm ngặt trong acc và việc sử dụng last xs. Thay vào đó, đầu ra nén ở trên liệt kê các phần tử theo kiểu "truyền trực tuyến". Thật vậy, nó hoạt động với danh sách vô hạn cũng như:

> take 10 $ compress [1..] 
[1,2,3,4,5,6,7,8,9,10] 

Điều đó đang được nói, tôi nghĩ rằng sử dụng một foldr đây cảm thấy một chút lạ: các mã trên được cho là ít có thể đọc hơn so với đệ quy rõ ràng