Làm thế nào tôi có thể hợp nhất hai bản đồ trên cùng một danh sách?

Question

Chúng ta có thể hợp nhất hai traversals qua danh sách xs trong biểu thức

(map f xs, map g xs) 

như vậy

unzip (map (\x -> (f x, g x)) xs) 

Có reasearch trên thực hiện loại phản ứng tổng hợp tự động?

(Có một nguy cơ để tạo ra một sự rò rỉ không gian ở đây nếu một trong những danh sách quay trở lại được tiêu thụ trước kia tôi quan tâm nhiều hơn trong việc ngăn ngừa các traversal thêm trên xs hơn tiết kiệm không gian..)

Edit: Tôi thực sự không tìm cách áp dụng sự hợp nhất vào danh sách Haskell trong bộ nhớ thực tế, nơi phép biến đổi này có thể không có ý nghĩa tùy thuộc vào việc unzip có thể hợp nhất với (các) người tiêu dùng của nó hay không. Tôi có một thiết lập mà tôi biết unzip có thể hợp nhất (xem "FlumeJava: các đường ống song song dữ liệu dễ dàng, hiệu quả").

Answer 1

Cũng không hoàn toàn tự động, nhưng bạn có thể cung cấp cho GHC danh sách các quy tắc viết lại như vậy. Xem 7.14 Rewrite rules và Using rules. Sau đó trình biên dịch sử dụng các quy tắc này để tối ưu hóa chương trình của bạn khi biên dịch. (Lưu ý rằng trình biên dịch không có cách nào kiểm tra xem các quy tắc thực hiện bất kỳ ý nghĩa.)

Edit: Để đưa ra một ví dụ cho vấn đề cụ thể này, chúng ta có thể viết:

{-# OPTIONS_GHC -fenable-rewrite-rules -ddump-rule-firings -ddump-rule-rewrites #-} 

import Data.Char 

{-# RULES 
"map/zip" forall f g xs. (,) (map f xs) (map g xs) = unzip (map (\x -> (f x, g x)) xs) 
    #-} 

main :: IO() 
main = let x = "abCD" in 
     print $ (,) (map toUpper x) (map toLower x) 

(cấp cao nhất tên hàm trong quy tắc là (,) :: a -> b -> (a, b)). Khi biên dịch, bạn sẽ thấy các quy tắc được áp dụng như thế nào. Tùy chọn dump-rule-firings hiển thị thông báo khi quy tắc được áp dụng và -ddump-rule-rewrites hiển thị chi tiết từng ứng dụng quy tắc - xem 7.14.6. Controlling what's going on in rewrite rules.

Answer 2

Tôi đã quản lý để tìm hai tài nguyên đề cập đến các chức năng như tổng hợp, ít nhất một thời gian ngắn:

Josef Svenningsson. "Shortcut Fusion cho Tích lũy thông số chức năng & Zip-như" http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

Duncan Coutts. "Luồng kết hợp: Kết hợp phím tắt thực tế cho các loại chuỗi đồng cảm" https://community.haskell.org/~duncan/thesis.pdf

Không có tài nguyên nào đề cập đến loại "kết hợp anh chị em" này một cách rõ ràng.