Khi nào tính năng ghi nhớ tự động trong GHC Haskell?

Question

Tôi không thể hiểu tại sao m1 được rõ ràng memoized khi m2 không nằm trong những điều sau đây:

m1  = ((filter odd [1..]) !!) 

m2 n = ((filter odd [1..]) !! n) 

m1 10000000 mất khoảng 1,5 giây trên cuộc gọi đầu tiên, và một phần nhỏ của chương trình trên các cuộc gọi tiếp theo (có lẽ nó lưu trữ danh sách), trong khi m2 10000000 luôn mất cùng một lượng thời gian (xây dựng lại danh sách với mỗi cuộc gọi). Có ai biết cái gì đang xảy ra không? Có bất kỳ quy tắc nào về việc liệu khi nào và khi nào GHC sẽ ghi nhớ một chức năng? Cảm ơn.

Answer 1

GHC không ghi nhớ chức năng.

Tuy nhiên, nó tính toán bất kỳ biểu thức đã cho nào trong mã một lần mỗi lần biểu thức lambda xung quanh của nó được nhập hoặc tối đa một lần nếu nó ở cấp cao nhất. Xác định nơi lambda-biểu thức là có thể là một chút khó khăn khi bạn sử dụng cú pháp đường như trong ví dụ của bạn, vì vậy hãy chuyển đổi các cú pháp khử đường tương đương:

m1' = (!!) (filter odd [1..])    -- NB: See below! 
m2' = \n -> (!!) (filter odd [1..]) n 

(Lưu ý: Báo cáo Haskell 98 thực sự mô tả một nhà khai thác trái phần như (a %) như tương đương với \b -> (%) a b, nhưng GHC desugars nó để (%) a. đây là những kỹ thuật khác nhau vì chúng có thể được phân biệt bởi seq. tôi nghĩ rằng tôi có thể đã đệ trình một vé GHC Trác về việc này.)

vì điều này, bạn có thể thấy rằng trong m1', biểu thức filter odd [1..] không được chứa i n bất kỳ biểu thức lambda nào, do đó, nó sẽ chỉ được tính một lần cho mỗi lần chạy chương trình của bạn, trong khi ở m2', filter odd [1..] sẽ được tính mỗi lần biểu thức lambda được nhập, tức là mỗi cuộc gọi của m2'. Điều đó giải thích sự khác biệt về thời gian bạn đang thấy.

---

Thực tế, một số phiên bản của GHC, với các tùy chọn tối ưu nhất định, sẽ chia sẻ nhiều giá trị hơn mô tả ở trên cho biết. Điều này có thể có vấn đề trong một số trường hợp. Ví dụ, hãy xem xét các chức năng

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x]) 

GHC thể nhận thấy rằng y không phụ thuộc vào x và viết lại các chức năng để

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x]) 

Trong trường hợp này, phiên bản mới là rất ít hiệu quả vì nó sẽ có để đọc khoảng 1 GB từ bộ nhớ trong đó y được lưu trữ, trong khi phiên bản gốc sẽ chạy trong không gian cố định và phù hợp với bộ nhớ cache của bộ xử lý. Thực tế, theo GHC 6.12.1, hàm f nhanh gấp hai lần khi biên dịch mà không cần tối ưu hóa so với được biên dịch bằng -O2.

Answer 2

m1 chỉ được tính một lần vì đó là Biểu mẫu áp dụng liên tục, trong khi m2 không phải là CAF và do đó được tính cho mỗi đánh giá.

Xem wiki GHC trên CAFS: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

Có một sự khác biệt quan trọng giữa hai hình thức: những hạn chế monomorphism áp dụng cho m1 nhưng không m2, vì m2 đã đưa ra một cách rõ ràng đối số. Vì vậy, loại m2 là chung nhưng m1 là cụ thể.Các loại họ được giao nhiệm vụ là:

m1 :: Int -> Integer 
m2 :: (Integral a) => Int -> a 

trình biên dịch Hầu hết Haskell và phiên dịch (tất cả trong số họ mà tôi biết trên thực tế) không memoize cấu trúc đa hình, vì vậy danh sách nội m2 được tái tạo mỗi lần nó được gọi là, nơi của m1 không phải là .

Answer 4

Tôi không chắc chắn, bởi vì tôi khá mới đối với Haskell, nhưng có vẻ như việc sử dụng chức năng thứ hai là không quan trọng và điều đầu tiên là không. Bản chất của hàm là, nó là kết quả phụ thuộc vào giá trị đầu vào và trong mô hình chức năng especailly nó phụ thuộc chỉ vào đầu vào. Rõ ràng ngụ ý là một hàm không có tham số trả về luôn luôn có cùng một giá trị hơn và hơn, không có vấn đề gì.

Có một cơ chế tối ưu hóa trong trình biên dịch GHC, khai thác thực tế này để tính toán giá trị của một hàm như vậy chỉ một lần cho toàn bộ thời gian chạy chương trình. Nó làm nó uể oải, để chắc chắn, nhưng dù sao đi nữa. Tôi tự nhận thấy, khi tôi viết chức năng sau:

primes = filter isPrime [2..] 
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n] 
     where f `divides` n = (n `mod` f) == 0 

Sau đó, để kiểm tra, tôi đã nhập GHCI và viết: primes !! 1000. Phải mất một vài giây, nhưng cuối cùng tôi đã nhận được câu trả lời: 7927. Sau đó, tôi gọi là primes !! 1001 và nhận câu trả lời ngay lập tức. Tương tự như vậy ngay lập tức tôi đã nhận được kết quả cho take 1000 primes, bởi vì Haskell đã phải tính toán toàn bộ danh sách nghìn phần tử để trả về phần tử 1001st trước đây.

Vì vậy, nếu bạn có thể viết hàm của mình sao cho không có tham số, bạn có thể muốn nó. ;)