XOR nào của XOR được coi là tốt hơn trong Haskell

Question

Tôi muốn biết cách tiêu chuẩn nhất trong Haskell là gì.

Trường hợp đầu tiên nêu rõ rằng chúng tôi muốn hai đối số (phần lớn thời gian).

Thứ hai liên quan đến một cuộc gọi hàm (id) trong mệnh đề thứ hai, vì vậy nó sẽ kém hiệu quả hơn vì trong lần triển khai đầu tiên chúng ta có thể trả về đối số thứ hai.

Vì vậy, tôi có xu hướng nghĩ rằng đầu tiên là tốt hơn và nên là một trong những lựa chọn: dễ đọc và để tìm ra những gì nó [1], và một cuộc gọi chức năng tiết kiệm.

Nhưng tôi là người mới đến Haskell, có thể trình biên dịch tối ưu hóa cuộc gọi bổ sung này.

xor :: Bool -> Bool -> Bool 

xor True x = not x 
xor False x = x 

xor True = not 
xor False = id 

Ngoài ra, tôi muốn biết nếu tôi có thể thay thế cả hai False bằng ký tự đại diện ở đó.

Vì vậy, thực hành tốt trong Haskell là gì. Có thể triển khai khác không?

[1] Chúng tôi bỏ qua ở đó rằng nó là một chức năng nổi tiếng, hãy tưởng tượng nó là một chức năng không tầm thường.

Cảm ơn

Answer 1

Tất nhiên nó phụ thuộc vào trình biên dịch và các tùy chọn được chuyển đến trình biên dịch.

Ví dụ cụ thể này, nếu bạn biên dịch mà không cần tối ưu hóa, GHC sẽ tạo mã như bạn đã viết, vì vậy phiên bản thứ hai chứa một cuộc gọi đến id resp. đến not. Đó là hơi kém hiệu quả hơn so với phiên bản đầu tiên, sau đó chỉ chứa các cuộc gọi đến not:

Xors.xor1 :: GHC.Types.Bool -> GHC.Types.Bool -> GHC.Types.Bool 
[GblId, Arity=2] 
Xors.xor1 = 
    \ (ds_dkm :: GHC.Types.Bool) (x_aeI :: GHC.Types.Bool) -> 
    case ds_dkm of _ { 
     GHC.Types.False -> x_aeI; 
     GHC.Types.True -> GHC.Classes.not x_aeI 
    } 

Xors.xor2 :: GHC.Types.Bool -> GHC.Types.Bool -> GHC.Types.Bool 
[GblId, Arity=1] 
Xors.xor2 = 
    \ (ds_dki :: GHC.Types.Bool) -> 
    case ds_dki of _ { 
     GHC.Types.False -> GHC.Base.id @ GHC.Types.Bool; 
     GHC.Types.True -> GHC.Classes.not 
    } 

(các cuộc gọi vẫn nằm trong lắp ráp sản xuất, nhưng cốt lõi là dễ đọc hơn, vì vậy tôi chỉ đăng bài).

Nhưng với optimisations, cả hai chức năng biên dịch để cùng một lõi (và từ đó đến mã cùng một máy),

Xors.xor2 = 
    \ (ds_dkf :: GHC.Types.Bool) (eta_B1 :: GHC.Types.Bool) -> 
    case ds_dkf of _ { 
     GHC.Types.False -> eta_B1; 
     GHC.Types.True -> 
     case eta_B1 of _ { 
      GHC.Types.False -> GHC.Types.True; 
      GHC.Types.True -> GHC.Types.False 
     } 
    } 

GHC eta-mở rộng phiên bản thứ hai và inlined các cuộc gọi đến id và not, bạn sẽ có được phù hợp với mô hình thuần túy.

Phương trình thứ hai sử dụng False hoặc ký tự đại diện không có sự khác biệt trong cả hai phiên bản, có hoặc không có tối ưu hóa.

có thể trình biên dịch tối ưu hóa cuộc gọi bổ sung này.

Nếu bạn yêu cầu tối ưu hóa, trong những trường hợp đơn giản như thế này, GHC sẽ loại bỏ cuộc gọi thêm.

hãy tưởng tượng nó là một chức năng không tầm thường.

Đây là vấn đề có thể xảy ra. Nếu mã này không đủ tầm thường, trình biên dịch có thể không thể loại bỏ tất cả các cuộc gọi được giới thiệu bằng cách định nghĩa hàm không phải tất cả các đối số được cung cấp.Mặc dù vậy, GHC khá tốt trong việc thực hiện điều đó và vì vậy bạn cần một số lượng không đáng kể để GHC không loại bỏ các lời gọi đến các hàm đơn giản mà nó biết khi biên dịch mã của bạn. 't biết việc thực hiện khi biên dịch các mô-đun trong câu hỏi).

Nếu mã quan trọng, luôn kiểm tra mã trình biên dịch tạo ra, đối với GHC, các cờ có liên quan là -ddump-simpl để lấy lõi được tạo sau khi tối ưu hóa và -ddump-asm để có được cụm được sản xuất.

Answer 2

Vì vậy, tôi có xu hướng nghĩ rằng đầu tiên là tốt hơn và nên là một trong những chọn: dễ đọc hơn và tìm ra những gì nó làm

Tôi đồng ý về khả năng đọc. Tuy nhiên, thứ hai là rất nhiều Haskell thành ngữ và khá dễ dàng hơn để đọc cho các lập trình viên có kinh nghiệm: không thực hiện việc giảm thiểu eta tầm thường là khá đáng ngờ và thực sự có thể mất tập trung từ ý định. Vì vậy, cho một phiên bản được tối ưu hóa, Tôi muốn viết nó ra hoàn toàn theo hình thức rõ ràng:

True `xor` False = True 
False `xor` True = True 
_  `xor` _  = False 

Tuy nhiên, nếu một sự thay thế như vậy là đáng kể ít có thể đọc hơn so với một thành ngữ nhất bạn nên xem xét không thay thế nó, nhưng thêm gợi ý để trình biên dịch vẫn có thể tối ưu hóa nó thành phiên bản lý tưởng. Như được chứng minh bởi Daniel Fischer, GHC khá thông minh và sẽ thường xuyên nhận được nó mà không cần trợ giúp; khi nó không có thể giúp thêm một số INLINE và/hoặc RULES pragmas. Nó không phải dễ dàng để tìm ra cách để làm điều này để có được hiệu suất tối ưu, nhưng điều này cũng đúng cho việc viết mã Haskell98 nhanh.

Answer 3

Để dễ đọc, tôi sẽ cố gắng tránh khớp mẫu và xác định hàm bằng một phương trình biểu thị điều gì đó thú vị về hàm được xác định. Đó không phải là lúc nào cũng có thể, nhưng ví dụ này, có rất nhiều lựa chọn:

• xor = (/=)
• xor a b = a /= b
• xor a b = not (a == b)
• xor a b = (a && not b) || (not a && b)
• xor a b = (a || b) && not (a && b)
• xor a b = odd (fromEnum a + fromEnum b)