Tại sao foldr sử dụng chức năng trợ giúp?

Question

Trong giải thích foldr để Haskell người mới, định nghĩa kinh điển là

foldr   :: (a -> b -> b) -> b -> [a] -> b 
foldr _ z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

Nhưng trong GHC.Base, foldr được định nghĩa là

foldr k z = go 
      where 
      go []  = z 
      go (y:ys) = y `k` go ys 

Dường như định nghĩa này là một tối ưu hóa cho tốc độ, nhưng tôi don không thấy lý do tại sao sử dụng chức năng trợ giúp go sẽ làm cho nó nhanh hơn. Các ý kiến ​​nguồn (see here) đề cập đến nội tuyến, nhưng tôi cũng không thấy cách định nghĩa này sẽ cải thiện nội tuyến.

Answer 1

Tôi có thể thêm một số chi tiết quan trọng về hệ thống tối ưu hóa của GHC.

Định nghĩa ngây thơ của foldr chuyển xung quanh một hàm. Có một chi phí vốn có trong việc gọi một hàm - đặc biệt khi hàm không được biết tại thời gian biên dịch. Nó sẽ được thực sự tốt đẹp để có thể inline định nghĩa của hàm nếu nó được biết đến tại thời gian biên dịch.

Có các thủ thuật có sẵn để thực hiện nội tuyến đó trong GHC - và đây là một ví dụ về chúng. Đầu tiên, cần foldr nội tuyến (tôi sẽ giải thích lý do sau). foldr 's thực hiện ngây thơ là đệ quy, vì vậy không thể được inlined. Vì vậy, một chuyển đổi công nhân/wrapper được áp dụng cho định nghĩa. Người lao động là đệ quy, nhưng wrapper thì không. Điều này cho phép foldr được inlined, mặc dù đệ quy về cấu trúc của danh sách.

Khi số foldr được gạch chân, nó cũng tạo bản sao của tất cả các liên kết cục bộ của nó. Đó là nhiều hơn hoặc ít hơn một văn bản trực tiếp nội tuyến (modulo một số đổi tên, và xảy ra sau khi vượt qua desugaring). Đây là nơi mà mọi thứ trở nên thú vị. go là một ràng buộc địa phương, và trình tối ưu hóa được nhìn vào bên trong nó. Nó nhận thấy rằng nó gọi một hàm trong phạm vi cục bộ, có tên là k. GHC thường sẽ xóa hoàn toàn biến số k và chỉ thay thế bằng biểu thức k. Và sau đó, nếu ứng dụng chức năng có khả năng thích hợp với nội tuyến, nó có thể được sắp xếp tại thời điểm này - loại bỏ toàn bộ phí gọi hàm đầu tiên hoàn toàn.

Hãy xem xét một ví dụ đơn giản, cụ thể. Chương trình này sẽ echo một dòng đầu vào với tất cả trailing 'x' ký tự loại bỏ:

dropR :: Char -> String -> String 
dropR x r = if x == 'x' && null r then "" else x : r 

main :: IO() 
main = do 
    s <- getLine 
    putStrLn $ foldr dropR "" s 

Đầu tiên, tôi ưu hoa sẽ inline foldr 's định nghĩa và đơn giản hóa, kết quả là mã mà trông giống như sau:

main :: IO() 
main = do 
    s <- getLine 
    -- I'm changing the where clause to a let expression for the sake of readability 
    putStrLn $ let { go [] = ""; go (x:xs) = dropR x (go xs) } in go s 

Và đó là điều chuyển đổi công nhân-wrapper cho phép .. Tôi sẽ bỏ qua các bước còn lại, nhưng nó phải được rõ ràng rằng GHC bây giờ có thể inline định nghĩa của dropR, loại bỏ các chức năng gọi trên không. Đây là nơi chiến thắng hiệu suất lớn đến từ.

Answer 2

Theo các ý kiến ​​nói:

-- Inline only in the final stage, after the foldr/cons rule has had a chance 
-- Also note that we inline it when it has *two* parameters, which are the 
-- ones we are keen about specialising! 

Đặc biệt, lưu ý "chúng tôi inline nó khi nó có hai thông số, mà là những người chúng ta đều mong về chuyên!"

Điều này được nói là khi foldr được gạch chân, nó chỉ được sắp xếp cho lựa chọn cụ thể của f và z, không phải cho lựa chọn danh sách được xếp. Tôi không phải là chuyên gia, nhưng nó sẽ có vẻ nó sẽ làm cho nó có thể inline nó trong những tình huống như

map (foldr (+) 0) some_list 

để các inline xảy ra trong dòng này và không phải sau khi map đã được áp dụng. Điều này làm cho nó tối ưu hóa trong nhiều tình huống và dễ dàng hơn. Tất cả các chức năng trợ giúp làm là mặt nạ đối số thứ 3 để {-# INLINE #-} có thể làm điều đó.

Answer 3

GHC không thể inline chức năng đệ quy, vì vậy

foldr   :: (a -> b -> b) -> b -> [a] -> b 
foldr _ z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

không thể được inlined. Nhưng

foldr k z = go 
     where 
     go []  = z 
     go (y:ys) = y `k` go ys 

không phải là hàm đệ quy. Nó là một hàm không đệ quy với định nghĩa đệ quy cục bộ!

Điều này có nghĩa rằng, như @bheklilr viết, trong map (foldr (+) 0) các foldr thể được inlined và do đó f và z thay thế bằng (+) và 0 trong mới go, và điều tuyệt vời có thể xảy ra, chẳng hạn như unboxing giá trị trung gian.

Answer 4

Một chi tiết quan trọng nhỏ không được đề cập trong câu trả lời khác là GHC, đưa ra một định nghĩa hàm như

f x y z w q = ... 

không thể inline f cho đến khi tất cả các đối số x, y, z, w, và q được áp dụng. Điều này có nghĩa là thường có lợi khi sử dụng phép biến đổi công nhân/trình bao bọc để hiển thị một tập các đối số hàm tối thiểu phải được áp dụng trước khi nội tuyến có thể xảy ra.