Nền tảng Haskell: chức năng lồng nhau và tối ưu hóa

Question

Có một mô hình rất phổ biến trong việc triển khai nhiều chức năng trong nền tảng haskell làm phiền tôi, nhưng tôi không thể tìm thấy lời giải thích. Đó là về việc sử dụng các hàm lồng nhau để tối ưu hóa.

Lý do cho hàm lồng nhau trong mệnh đề khi chúng nhắm đến đệ quy đuôi là rất rõ ràng đối với tôi (như trong length), nhưng mục đích là gì khi hàm bên trong có cùng kiểu như hàm cấp cao nhất ? Nó xảy ra, trong ví dụ, trong nhiều chức năng của Data.Set module, giống như một sau:

-- | /O(log n)/. Is the element in the set? 
member :: Ord a => a -> Set a -> Bool 
member = go 
    where 
    STRICT_1_OF_2(go) 
    go _ Tip = False 
    go x (Bin _ y l r) = case compare x y of 
      LT -> go x l 
      GT -> go x r 
      EQ -> True 
#if __GLASGOW_HASKELL__ >= 700 
{-# INLINABLE member #-} 
#else 
{-# INLINE member #-} 
#endif 

tôi nghi ngờ nó có thể có cái gì để làm với memoization, nhưng tôi không chắc chắn.

---

chỉnh sửa: Kể từ dave4420 cho thấy tính nghiêm minh, đây là định nghĩa cho STRICT_1_OF_2 vĩ mô có thể được tìm thấy trong các mô-đun tương tự:

-- Use macros to define strictness of functions. 
-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter. 
-- We do not use BangPatterns, because they are not in any standard and we 
-- want the compilers to be compiled by as many compilers as possible. 
#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined 

Tôi hiểu thế nào điều này công trình vĩ mô, tuy nhiên tôi vẫn không thấy lý do tại sao go cùng với STRICT_1_OF_2(go) không được di chuyển ở cấp cao nhất thay vì member.

Có thể nó không phải vì tối ưu hóa, mà đơn giản chỉ vì lựa chọn phong cách?

---

chỉnh sửa 2: Tôi thêm phần INLINABLE và INLINE từ các mô-đun bộ. Tôi đã không nghĩ rằng họ có thể có một cái gì đó để làm với nó ở cái nhìn đầu tiên.

Answer 1

Một lợi ích tức thì của việc có một trình bao bọc INLINABLE (hoặc INLINE) xung quanh nhân viên địa phương là chuyên môn hóa. Cách thức mà member được xác định, tại trang cuộc gọi, với loại phần tử cố định, từ điển Ord có thể bị hủy và hàm compare thích hợp được gạch chân hoặc ít nhất được truyền dưới dạng đối số tĩnh.

Với định nghĩa đệ quy trực tiếp, member trở thành trình ngắt vòng và không được gạch chân, vì vậy chuyên môn trang web không được thực hiện - ít nhất là câu chuyện trước INLINABLE pragma.

Với INLINABLE pragma, chuyên môn trang web cuộc gọi diễn ra, từ điển bị loại bỏ, nhưng tôi có một vài nỗ lực không được quản lý để viết trực tiếp đệ quy member hiệu quả như hiện tại. Nhưng với một pragma INLINE, luật vẫn đứng, một vòng lặp ngắt không được gạch chân; cho member điều đó có nghĩa là không có chuyên môn trang web để loại bỏ từ điển là có thể.

Vì vậy, có thể không còn cần thiết nữa để viết các chức năng theo phong cách đó, nhưng đó là, để nhận chuyên môn về trang web cuộc gọi.

Answer 2

GHC không thể thực hiện chức năng đệ quy nội tuyến. Cách member được xác định, đệ quy bị giới hạn ở số go và member chính nó không đệ quy và có thể được gạch chân.

Từ GHC user guide:

GHC đảm bảo rằng nội tuyến không thể tiếp tục mãi mãi: mỗi nhóm lẫn nhau-đệ quy được cắt bởi một hoặc nhiều bộ phận ngắt vòng lặp được bao giờ inlined (xem Bí mật của inliner GHC, JFP 12 (4) tháng 7 năm 2002). GHC cố gắng không chọn chức năng với một pragma INLINE dưới dạng vòng lặp ngắt, nhưng khi không có lựa chọn nào, ngay cả chức năng INLINE cũng có thể được chọn là , trong trường hợp đó, pragma INLINE bị bỏ qua. Ví dụ: đối với chức năng tự đệ quy, trình ngắt vòng lặp chỉ có thể là chức năng chính nó, do đó, một pragma INLINE luôn bị bỏ qua.