Haskell Các vấn đề với Parameter Passing Phong cách Heap

Question

Dưới đây là một chương trình đơn giản mà thổi đống của tôi để Kingdom Come:

intersect n k z s rs c 
    | c == 23 = rs 
    | x == y = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1) 
    | x < y  = intersect (n+1) k (z+1) s rs c 
    | otherwise = intersect n (k+1) z s rs c 
    where x = (2*n*n) + 4 * n 
      y = (k * k + k) 
      f = (z, (x `div` 2), (z+s)) 
p = intersect 1 1 1 0 [] 0 

main = do 
    putStr (show p) 

gì chương trình làm là tính toán giao điểm của hai chuỗi dài vô tận, dừng lại khi nó đạt đến 23 yếu tố. Nhưng điều đó không quan trọng với tôi.

Điều thú vị là theo như tôi có thể nói, không nên có nhiều ở đây đang ngồi trên đống. Các chức năng giao nhau là đệ quy với tất cả các cuộc thám hiểm được viết như cuộc gọi đuôi. Nhà nước được tích lũy trong các đối số, và không có nhiều của nó. 5 số nguyên và một danh sách nhỏ các bộ dữ liệu.

Nếu tôi là một cá cược, tôi sẽ cá rằng một số phần được xây dựng trong các đối số khi tôi thực hiện đệ quy, đặc biệt là đối số không được đánh giá trên đệ quy đã cho. Nhưng đó chỉ là một linh cảm hoang dã.

Vấn đề thực sự ở đây là gì? Và làm thế nào để sửa chữa nó?

Answer 1

Nếu bạn gặp rắc rối với đống, chạy the heap profiler, như vậy:

$ ghc -O2 --make A.hs -prof -auto-all -rtsopts -fforce-recomp 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A.exe ... 

nào khi chạy:

$ ./A.exe +RTS -M1G -hy 

Tạo một file A.hp đầu ra:

$ hp2ps -c A.hp 

Giống như vậy:

Vì vậy, đống của bạn đầy Integer, cho biết một số vấn đề trong thông số tích lũy của các chức năng của bạn - nơi tất cả các Integer là.

Sửa đổi chức năng để nó là nghiêm ngặt trong Integer luận lười biếng (dựa trên thực tế, bạn không bao giờ kiểm tra giá trị của họ), như vậy:

{-# LANGUAGE BangPatterns #-} 

intersect n k !z !s rs c 
    | c == 23 = rs 
    | x == y = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1) 
    | x < y  = intersect (n+1) k (z+1) s rs c 
    | otherwise = intersect n (k+1) z s rs c 
    where x = (2*n*n) + 4 * n 
      y = (k * k + k) 
      f = (z, (x `div` 2), (z+s)) 

p = intersect 1 1 1 0 [] 0 

main = do 
    putStr (show p) 

Và chương trình của bạn bây giờ chạy trong không gian liên tục với danh sách đối số bạn đang sản xuất (mặc dù không chấm dứt cho c == 23 trong bất kỳ thời điểm hợp lý nào).

Answer 2

Nếu đó là OK để có được danh sách kết quả đảo ngược, bạn có thể tận dụng lợi thế của sự lười biếng Haskell và trở lại danh sách vì nó được tính toán, thay vì đi qua nó một cách đệ quy như một đối số tích lũy. Điều này không chỉ cho phép bạn tiêu thụ và in danh sách vì nó đã được tính toán (do đó loại bỏ một không gian rò rỉ ngay tại đó), bạn cũng có thể yếu tố ra quyết định về bao nhiêu yếu tố mà bạn muốn từ intersect:

{-# LANGUAGE BangPatterns #-} 

intersect n k !z s 
    | x == y = f : intersect (n+1) (k+1) (z+1) (z+s) 
    | x < y  = intersect (n+1) k (z+1) s 
    | otherwise = intersect n (k+1) z s 
    where x = (2*n*n) + 4 * n 
      y = (k * k + k) 
      f = (z, (x `div` 2), (z+s)) 
p = intersect 1 1 1 0 

main = do 
    putStrLn (unlines (map show (take 23 p))) 

Như Don lưu ý, chúng ta cần phải cẩn thận để các đối số tích lũy đánh giá kịp thời thay vì xây dựng các khối lớn. Bằng cách làm cho đối số z nghiêm ngặt, chúng tôi đảm bảo rằng tất cả các đối số sẽ được yêu cầu.

By xuất ra một yếu tố trên mỗi dòng, chúng ta có thể xem kết quả được sản xuất:

$ ghc -O2 intersect.hs && ./intersect 
[1 of 1] Compiling Main    (intersect.hs, intersect.o) 
Linking intersect ... 
(1,3,1) 
(3,15,4) 
(10,120,14) 
(22,528,36) 
(63,4095,99) 
(133,17955,232) 
(372,139128,604) 
(780,609960,1384) 
...