Có cấu trúc dữ liệu trung gian nào được tạo trong danh sách hay không

Question

Có vẻ như foldr thực hiện một số loại phản ứng tổng hợp với khả năng đọc danh sách, do đó yêu cầu phân bổ bộ nhớ ít hơn (11mb) so với foldl (21mb).

myfunc = sum $ foldr g acc [ f x | x <- xs ] 
f x = .. 
g x y = .. 

Có ai giải thích tại sao không? Ngoài ra làm thế nào đánh giá lười biếng giúp đỡ trong việc này.

Answer 1

Một lần trái không thể tạo ra bất kỳ đầu ra nào (một phần của kết quả) trước khi nó vượt qua toàn bộ danh sách. Tùy thuộc vào chức năng bạn gấp, có thể tạo cấu trúc dữ liệu lớn hoặc một đoạn lớn, sử dụng nhiều bộ nhớ (bộ nhớ có thể chạy trong bộ nhớ không đổi nếu bạn gấp (+) trong danh sách Int). Có thể, với các chức năng thích hợp (như vậy có thể tạo ra kết quả [một phần] mà không kiểm tra đối số thứ hai) tạo kết quả của chúng theo từng bước, sao cho kết quả được sử dụng phù hợp và danh sách đầu vào được tạo ra một cách thích hợp, toàn bộ tính toán có thể chạy trong không gian liên tục nhỏ. Như sclv đã nói, nó làm giảm cơ bản thành một vòng lặp trong những trường hợp đó.

Answer 2

Chúng tôi có thể desugar hiểu được về cơ bản là map f xs. Nếu bạn đang biên dịch điều này thì ghc thực sự có thể hợp nhất tổng, nếp gấp và bản đồ thành một đường chuyền: http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion. Nhưng ngay cả khi bạn không, thì lười biếng là bạn của bạn để sử dụng bộ nhớ. Danh sách do bản đồ tạo ra là lười - f chỉ được áp dụng khi được yêu cầu. Và f sẽ chỉ được yêu cầu khi foldr yêu cầu nó. Và kể từ khi foldr của bạn rõ ràng là sản xuất một danh sách (lười biếng) khác, sau đó mỗi bước của lần lượt chỉ yêu cầu bằng tổng số lần lượt. Vì vậy, bạn vẫn có từng chức năng được áp dụng lần lượt, nhưng bạn không cần phải tạo ra các cấu trúc dữ liệu trung gian đầy đủ cùng một lúc. Trong khi bạn đã viết một tập hợp các thành phần chức năng, mô hình đánh giá sẽ có xu hướng xử lý tập hợp mã cụ thể này, điều chỉnh một chuỗi toàn bộ vẫy tay, giống như một vòng lặp (mặc dù, không kết hợp, một vòng lặp với số lượng hợp lý) của indirection).

Answer 3

Đây là một tính năng của trình biên dịch GHC. Về cơ bản, GHC có thể nhận ra khi một danh sách được sử dụng trong một "đường ống", và có thể chuyển đổi toàn bộ cấu trúc thành tương đương với while vòng trong C mà không phân bổ một danh sách nào cả.

Lý do tại sao tính năng này hoạt động với foldr và không foldl phụ thuộc vào chức năng g mà bạn đang sử dụng trong ví dụ của mình. Kể từ foldr, trái ngược với foldl, tích lũy kết quả của hàm được đưa ra làm tham số (aka: foldl cần toàn bộ danh sách trước khi nó có thể bắt đầu thực sự đánh giá hàm g, do đó, nó tạo ra một lượng lớn các hàm không được đánh giá và phần tử cuối cùng trong danh sách là kết quả của nó - đó là lý do tại sao nó sử dụng nhiều bộ nhớ hơn trong trường hợp này - trong khi foldr có thể bắt đầu đánh giá g ngay khi nó nhận được bất kỳ đầu vào danh sách nào), nó được gọi là "nghiêm ngặt" trong bộ tích lũy của nó, và một số giả định có thể được thực hiện bởi trình biên dịch có thể dẫn đến tối ưu hóa.

Nếu, ví dụ, hàm g mang lại giá trị là danh sách, nó có thể tiếp tục chiến lược tối ưu hóa "đường ống" nói trên, về cơ bản xử lý foldr như map và tạo toàn bộ cấu trúc (từ danh sách tạo danh sách) thành một vòng lặp nghiêm ngặt. Điều này chỉ có thể bởi vì các foldr sản lượng chính xác một yếu tố danh sách cho mỗi yếu tố danh sách nó tiêu thụ, mà foldl không được đảm bảo để làm (đặc biệt là cho danh sách vô hạn).