Chức năng zip tham gia bên ngoài Canonical

Question

Nếu bạn xem xét các chỉ mục (ẩn) của từng phần tử trong danh sách dưới dạng khóa của chúng, thì zipWith giống như một liên kết bên trong quan hệ. Nó chỉ xử lý các khóa mà cả hai yếu tố đầu vào đều có giá trị:

zipWith (+) [1..5] [10..20] == zipWith (+) [1..11] [10..14] == [11,13,15,17,19] 

Có chức năng tương ứng chuẩn nào tương ứng với tham gia bên ngoài không? Một cái gì đó như:

outerZipWith :: (a -> b -> c) -> a -> b -> [a] -> [b] -> [c] 
outerZipWith _ _ _ [] [] = [] 
outerZipWith f a' b' [] (b:bs) = f a' b : outerZipWith f a' b' [] bs 
outerZipWith f a' b' (a:as) [] = f a b' : outerZipWith f a' b' as [] 
outerZipWith f a' b' (a:as) (b:bs) = f a b : outerZipWith f a' b' as bs 

hoặc có thể

outerZipWith' :: (a -> b -> c) -> Maybe a -> Maybe b -> [a] -> [b] -> [c] 
outerZipWith' _ _ _ [] [] = [] 
outerZipWith' _ Nothing _ [] _ = [] 
outerZipWith' _ _ Nothing _ [] = [] 
outerZipWith' f a' b' [] (b:bs) = f (fromJust a') b : outerZipWith f a' b' [] bs 
outerZipWith' f a' b' (a:as) [] = f a (fromJust b') : outerZipWith f a' b' as [] 
outerZipWith' f a' b' (a:as) (b:bs) = f a b : outerZipWith f a' b' as bs 

Vì vậy, tôi có thể làm

outerZipWith (+) 0 0 [1..5] [10..20] == [11,13,15,17,19,15,16,17,18,19,20] 
outerZipWith (+) 0 0 [1..11] [10..14] == [11,13,15,17,19,6,7,8,9,10,11] 

tôi thấy mình cần nó bất cứ lúc nào, và tôi muốn sử dụng một thành ngữ phổ biến để làm cho mã của tôi dễ ghi hơn (và dễ bảo trì hơn) so với việc thực hiện outerZipWith hoặc thực hiện if length as < length bs then zipWith f (as ++ repeat a) bs else zipWith f as (bs ++ repeat b).

Answer 1

Điều này có vẻ khó xử vì bạn đang cố gắng bỏ qua đến cuối thay vì đối phó với các hoạt động nguyên thủy.

Trước hết, zipWith là khái niệm là zip, tiếp theo là map (uncurry ($)). Đây là một điểm quan trọng, bởi vì (un) currying là lý do tại sao zipWith là có thể ở tất cả. Đưa ra danh sách với các loại [a] và [b], để áp dụng hàm (a -> b -> c) và nhận được một số loại [c], bạn rõ ràng cần một trong mỗi đầu vào. Hai cách để làm điều này chính xác là hai trường hợp Applicative cho danh sách và zipWith là liftA2 cho một trong số các danh sách đó. (Ví dụ khác là một tiêu chuẩn, trong đó cung cấp cho các sản phẩm Descartes - một tham gia chéo, nếu bạn thích).

Ngữ nghĩa bạn muốn không tương ứng với bất kỳ trường hợp rõ ràng nào Applicative, đó là lý do tại sao điều này khó khăn hơn nhiều. Hãy xem xét đầu tiên một outerZip :: [a] -> [b] -> [?? a b] và loại nó sẽ có. Các phần tử của danh sách kết quả có thể là a, b hoặc cả hai. Điều này không chỉ không tương ứng với bất kỳ kiểu dữ liệu chuẩn nào, nó khó xử để thể hiện về chúng bởi vì bạn không thể yếu tố nào hữu ích trong biểu thức (A + B + A*B).

Loại dữ liệu như vậy có cách sử dụng riêng, đó là lý do tại sao tôi có my own package defining one. Tôi nhớ rằng có một trong những vụ tấn công là tốt (với ít chức năng phụ trợ hơn tôi, tôi nghĩ) nhưng tôi không thể nhớ nó được gọi là gì.

Gắn bó với các công cụ chuẩn, bạn cần một "giá trị mặc định" hợp lý, có nghĩa là có phiên bản Monoid và sử dụng giá trị nhận dạng để đệm danh sách. Dịch sang và từ một Monoid thích hợp sử dụng trình bao bọc newtype hoặc như vậy có thể không kết thúc đơn giản hơn so với việc triển khai hiện tại của bạn.

---

Ngoài ra, nhận xét của bạn về chỉ mục danh sách như các khóa thực sự có thể được phát triển thêm; bất kỳ Functor nào có khái niệm tương tự về khóa là đồng nhất với đơn vị Reader, một hàm rõ ràng từ khóa đến giá trị. Edward Kmett có, như mọi khi, một loạt các gói mã hóa các khái niệm trừu tượng, trong trường hợp này xây dựng từ the representable-functors package. Có thể hữu ích, nếu bạn không ngại viết một tá trường hợp chỉ để bắt đầu ít nhất ...

Answer 2

Thay vì điền vào danh sách ngắn hơn với hằng số, tại sao không cung cấp danh sách các giá trị cần thực hiện cho đến khi kết thúc danh sách dài hơn? Điều này cũng giúp loại bỏ sự cần thiết cho một Maybe vì danh sách có thể trống (hoặc có chiều dài hữu hạn).

tôi không thể tìm thấy bất cứ điều gì tiêu chuẩn, nhưng ngắn của một hoàn lại thực hiện zipWith dọc theo dòng bạn thấy, tôi đã phát triển phiên bản thử nghiệm length của bạn như thế này:

outerZipWith :: (a -> b -> c) -> [a] -> [b] -> [a] -> [b] -> [c] 
outerZipWith f as bs as' bs' = take n $ zipWith f (as ++ as') (bs ++ bs') 
    where n = max (length as) (length bs) 

Answer 3

Kiểu này mà đi lên rất nhiều. Đó là hoạt động cogroup của PACT algebra. Nơi tôi làm việc, chúng tôi sử dụng các loại lớp để phân biệt ba hoạt động này:

1. zip: Giao lộ kết cấu.
2. align: Công đoàn cấu trúc.
3. liftA2: Sản phẩm cấu trúc mạch vành.

Điều này được thảo luận bởi Paul Chiusano on his blog.