Haskell's Stream Fusion

Question

Stream Fusion của Haskell là gì và cách sử dụng?

Answer 1

Giấy mà Logan trỏ đến là tuyệt vời, nhưng có một chút khó khăn. (Chỉ cần hỏi học sinh của tôi.) Nó cũng là một vấn đề lớn về 'cách hoạt động của quá trình tổng hợp dòng chảy' và chỉ một phần nhỏ 'hợp nhất dòng chảy là gì và cách bạn có thể sử dụng nó'.

Vấn đề mà dòng fusion giải quyết là mã chức năng như viết thường phân bổ danh mục trung gian, ví dụ, để tạo ra một danh sách vô hạn các số nút, bạn có thể viết

nodenames = map ("n"++) $ map show [1..] 

đang Naive sẽ phân bổ một danh sách vô hạn của số nguyên [1, 2, 3, ...], danh sách vô hạn các chuỗi ["1", "2", "3", ...] và cuối cùng là danh sách vô hạn các tên ["n1", "n2", "n3", ...]. Đó là quá nhiều phân bổ.

Sự hợp nhất dòng nào thực hiện việc dịch một định nghĩa như nodenames thành thứ gì đó sử dụng hàm đệ quy phân bổ chỉ những gì cần thiết cho kết quả. Nói chung, việc loại bỏ phân bổ danh sách trung gian được gọi là phá rừng.

Để sử dụng dòng phản ứng tổng hợp, bạn cần phải viết chức năng không đệ quy danh sách sử dụng các chức năng từ thư viện dòng-fusion được mô tả trong GHC ticket 915 (map, foldr, và vân vân) thay vì đệ quy rõ ràng. Thư viện này chứa các phiên bản mới của tất cả các hàm Prelude đã được viết lại để khai thác hợp nhất luồng. Rõ ràng công cụ này được dự kiến ​​đưa nó vào bản phát hành GHC tiếp theo (6.12) nhưng không có trong phiên bản ổn định hiện tại (6.10). Nếu bạn muốn sử dụng thư viện Porges có một lời giải thích đơn giản tốt đẹp trong câu trả lời của mình.

Nếu bạn thực sự muốn có giải thích về cách hoạt động của luồng nhiệt hạch, hãy đăng câu hỏi khác --- nhưng điều đó khó hơn nhiều.

Answer 2

Theo như tôi biết, và trái với những gì Norman nói, luồng kết hợp là không hiện được triển khai trong cơ sở của GHC (nghĩa là bạn không thể chỉ sử dụng hàm Prelude). Để biết thêm thông tin, xem GHC ticket 915.

Để sử dụng kết hợp luồng, bạn cần phải cài đặt thư viện kết hợp luồng, nhập Data.List.Stream (bạn cũng có thể nhập Control.Monad.Stream) và chỉ sử dụng các chức năng từ mô-đun đó thay vì chức năng Prelude. Điều này có nghĩa là nhập Prelude ẩn tất cả các hàm danh sách mặc định và không sử dụng cấu trúc [x..y] hoặc danh sách hiểu.

Answer 3

Không đúng, khi GHC trong 6.12 sử dụng các chức năng mới theo mặc định, chúng cũng sẽ thực hiện [x..y] và danh sách hiểu theo cách không đệ quy? Vì lý do duy nhất họ không đúng hàng, là họ là nội bộ và không thực sự được viết bằng Haskell, nhưng giống như từ khóa hơn, vì lợi ích của tốc độ và/hoặc vì bạn sẽ không thể xác định lại cú pháp đó.