Interleaving danh sách các chức năng

Question

phép nói rằng tôi đang cho hai chức năng:

f :: [a] -> b 
g :: [a] -> c 

Tôi muốn viết một hàm có nghĩa là tương đương với việc này:

h x = (f x, g x) 

Nhưng khi tôi làm điều đó, cho lớn danh sách chắc chắn tôi hết bộ nhớ.

Một ví dụ đơn giản như sau:

x = [1..100000000::Int] 
main = print $ (sum x, product x) 

Tôi hiểu đây là trường hợp vì danh sách x đang được lưu trữ trong bộ nhớ mà không bị thu gom rác thải. Nó sẽ tốt hơn thay vì f và g làm việc trên x trong, tốt, "song song".

Giả sử tôi không thể thay đổi f và g, và cũng không muốn thực hiện một bản sao riêng của x (giả x là tốn kém để sản xuất) làm thế nào tôi có thể viết h mà không cần chạy vào ra các vấn đề bộ nhớ?

Answer 1

Bạn có thể sử dụng nhiều chuỗi để đánh giá song song f x và g x.

Ví dụ:

x :: [Int] 
x = [1..10^8] 

main = print $ let a = sum x 
        b = product x 
       in a `par` b `pseq` (a,b) 

Cách tốt nhất để khai thác thời gian chạy song song của GHC để ngăn chặn rò rỉ không gian bằng cách thực hiện hai việc cùng một lúc.

Hoặc, bạn cần phải hợp nhất f và g thành a single pass.

Answer 2

Câu trả lời ngắn gọn là bạn không thể. Vì bạn không có quyền kiểm soát trên f và g, bạn không đảm bảo rằng các chức năng xử lý đầu vào của chúng theo tuần tự. Một hàm như vậy cũng có thể giữ toàn bộ danh sách được lưu trữ trong bộ nhớ trước khi tạo kết quả cuối cùng.

Tuy nhiên, nếu chức năng của bạn được biểu thị dưới dạng nếp gấp, thì tình huống sẽ khác. Điều này có nghĩa là chúng tôi biết cách từng bước áp dụng từng bước, vì vậy chúng tôi có thể song song các bước đó trong một lần chạy.

Có rất nhiều tài nguyên về lĩnh vực này. Ví dụ:

• Haskell: Can I perform several folds over the same lazy list without keeping list in memory?
• cổ điển Beautiful folding
• More beautiful fold zipping

---

Các mô hình tiêu thụ một chuỗi các giá trị với giới hạn không gian đúng quy định được giải quyết tổng quát hơn với các thư viện ống giống như như vậy ống dẫn, iteratees o r ống.Ví dụ, trong ống dẫn, bạn có thể thể hiện sự kết hợp của các khoản tiền tính toán và các sản phẩm như

import Control.Monad.Identity 
import Data.Conduit 
import Data.Conduit.List (fold, sourceList) 
import Data.Conduit.Internal (zipSinks) 

product', sum' :: (Monad m, Num a) => Sink a m a 
sum'  = fold (+) 0 
product' = fold (*) 1 

main = print . runIdentity $ sourceList (replicate (10^6) 1) $$ 
           zipSinks sum' product' 

Answer 3

Nếu bạn có thể tắt chức năng của bạn vào nếp gấp, bạn có thể sau đó chỉ cần sử dụng chúng với một quét:

x = [1..100000000::Int] 
main = mapM_ print . tail . scanl foo (a0,b0) . takeWhile (not.null) 
     . unfoldr (Just . splitAt 1000) -- adjust the chunk length as needed 
     $ x 

foo (a,b) x = let a2 = f' a $ f x ; b2 = g' b $ g x 
       in a2 `seq` b2 `seq` (a2, b2) 

f :: [t] -> a   -- e.g. sum 
g :: [t] -> b   --  (`rem` 10007) . product 
f' :: a -> a -> a  -- e.g. (+) 
g' :: b -> b -> b  --  ((`rem` 10007) .) . (*) 

chúng tôi tiêu thụ đầu vào theo khối để có hiệu suất tốt hơn. Biên dịch với -O2, điều này sẽ chạy trong một không gian liên tục. Các kết quả tạm thời được in như là dấu hiệu của sự tiến bộ.

Nếu bạn không thể biến chức năng của mình thành nếp gấp, điều này có nghĩa là có để tiêu thụ toàn bộ danh sách để tạo ra bất kỳ đầu ra nào và mẹo này không áp dụng.