Tại sao thêm dấu ngã vào trước một mẫu khớp làm chậm chức năng của tôi?

Question

Tôi có hai chức năng quy định tại một đoạn mã Haskell:

lengthwtilde [] = 0 
lengthwtilde ~(_:xs) = 1 + lengthwtilde xs 

lengthwotilde [] = 0 
lengthwotilde (_:xs) = 1 + lengthwotilde xs 

Khi tôi kiểm tra chúng cả trong ghci (sử dụng :set +s), tôi thấy rằng lengthwtilde (một với một dấu ngã ở phía trước của mô hình phù hợp) thực hiện chậm hơn đáng kể so với lengthwotilde khoảng ba giây.

*Main> lengthwtilde [1..10000000] 
10000000 
(19.40 secs, 1731107132 bytes) 
*Main> lengthwotilde [1..10000000] 
10000000 
(16.45 secs, 1531241716 bytes) 

Tại sao điều này?

Answer 1

Thêm ~ trước một mẫu khớp làm cho khớp đó khớp với không thể chối cãi. Bạn có thể nghĩ về điều này khi bổ sung thêm sự lười biếng vào một mẫu, để nó không bao giờ không khớp nếu không có sự phù hợp hoàn toàn để đánh giá. Dưới đây là ví dụ đơn giản:

Prelude> (\ (_:_) -> "non-empty") [] 
"*** Exception: <interactive>:2:2-23: Non-exhaustive patterns in lambda 

Prelude> (\ ~(_:_) -> "oops") [] 
"oops" 

Với kết hợp mẫu không thể chối cãi, mặc dù không có biến mẫu nào được đánh giá, không có lỗi. Về cơ bản, phù hợp với mô hình không thể chối cãi biến đổi chức năng:

\ xs -> let (_:_) = xs in "oops" 

Đó là gói phụ này của sự lười biếng làm chậm chức năng chiều dài của bạn. Nếu bạn áp dụng cùng một phép biến đổi ràng buộc thành lengthwtilde bạn nhận được

lengthwtilde [] = 0 
lengthwtilde xs' = let (_:xs) = xs' in 1 + lengthwtilde xs 

Hãy suy nghĩ về cách đánh giá này. Ở cấp cao nhất, bạn nhận được 1+lengthwtilde xs. Nhưng xs thậm chí không được đánh giá, vì nó là một biến cho phép. Vì vậy, ở bước tiếp theo đầu tiên, xs được đánh giá để xác định nó khớp với trường hợp thứ hai là lengthwtilde và quá trình lặp lại.

Tương phản điều này với lengthwotilde. Trong hàm này, hành vi khớp với trường hợp thứ hai của hàm cũng buộc đối số được đánh giá là tốt. Kết quả cuối cùng là như nhau, nhưng nó có hiệu quả hơn để có thể cởi nó sớm hơn là để lại một miếng khác bị ép buộc.

Về mặt kỹ thuật lengthwtilde là hơi phức tạp hơn: các đối số là đã đánh giá trong chi nhánh thứ hai vì đó là cách chúng tôi xác định chi nhánh, chúng tôi đang ở, tuy nhiên nó được tái quấn khi chuyển vào cuộc gọi đệ quy.

Thật hữu ích khi có thể thấy lõi sản xuất. Dưới đây là kết quả của lengthwotilde (sản xuất từ ​​ghc -O0:

Foo.lengthwotilde = 
    \ (@ t_afD) 
    (@ a_afE) 
    ($dNum_afF :: GHC.Num.Num a_afE) 
    (eta_B1 :: [t_afD]) -> 
    letrec { 
     lengthwotilde1_af2 [Occ=LoopBreaker] :: [t_afD] -> a_afE 
     [LclId, Arity=1] 
     lengthwotilde1_af2 = 
     \ (ds_dgd :: [t_afD]) -> 
      case ds_dgd of _ { 
      [] -> GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 0); 
      : ds1_dge xs_af1 -> 
       GHC.Num.+ 
       @ a_afE 
       $dNum_afF 
       (GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 1)) 
       (lengthwotilde1_af2 xs_af1) 
      }; } in 
    lengthwotilde1_af2 eta_B1 

Lưu ý chức năng lengthwotilde1_af2 ngay lập tức thực hiện một case trên lập luận ds_dgd (đây là danh sách đầu vào), và sau đó recurses bên trong trường hợp, tạo thành một thunk (với một số mở rộng):

1 + len [2..] 
1 + (1 + len [3..]) 
1 + (1 + (1 + len [4..]) 

mà cuối cùng yêu cầu đánh giá 1 + (1 + (1 + (1 + ..)))

Dưới đây là lengthwtilde

Foo.lengthwtilde = 
    \ (@ t_afW) 
    (@ a_afX) 
    ($dNum_afY :: GHC.Num.Num a_afX) 
    (eta_B1 :: [t_afW]) -> 
    letrec { 
     lengthwtilde1_afM [Occ=LoopBreaker] :: [t_afW] -> a_afX 
     [LclId, Arity=1] 
     lengthwtilde1_afM = 
     \ (ds_dgh :: [t_afW]) -> 
      case ds_dgh of wild_X9 { 
      [] -> GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 0); 
      : ipv_sgv ipv1_sgw -> 
       GHC.Num.+ 
       @ a_afX 
       $dNum_afY 
       (GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 1)) 
       (lengthwtilde1_afM 
        (case wild_X9 of _ { 
         [] -> 
         (Control.Exception.Base.irrefutPatError 
          @() "foo.hs:(3,1)-(4,42)|(_ : xs)") 
         `cast` (UnsafeCo() [t_afW] ::() ~# [t_afW]); 
         : ds1_dgk xs_aeH -> xs_aeH 
        })) 
      }; } in 
    lengthwtilde1_afM eta_B1 

Thẩm định này tạo thành một thunk khác nhau:

len [1..] 
1 + (len (if null [1..] then error else [2..])) 
1 + (len [2..]) 
1 + (1 + len (if null [2..] then error else [3..])) 

mà cuối cùng kết quả trong cùng một chuỗi của bổ sung nào bạn có thời gian đầu tiên, nhưng với một số phụ logic để xử lý các mẫu thất bại không thể chối cãi. Bây giờ, nếu bạn đang chạy mã được biên dịch với bất kỳ tối ưu hóa nào, ghc gần như chắc chắn sẽ nhận ra rằng các đối số không thể là rỗng, vì chúng đã được đánh giá và được biết là sử dụng hàm tạo (:) tại thời điểm này. Và khi tôi biên dịch mã với ghc -O2 và chạy nó, cả hai hàm đều thực thi trong cùng một khoảng thời gian. Cả hai đều khá tệ, bởi vì một trong hai cách đều dẫn đến một chuỗi các khối. Định nghĩa tiêu chuẩn của length là tốt hơn nhiều, như là một định nghĩa tốt foldl'.