khi nào tôi nên sử dụng dạng mẫu để xác định các biểu thức con chung?

Question

Tôi tự hỏi mình phải lo lắng đến mức nào khi tối ưu hóa vi mô các biểu thức con phổ biến trong Haskell (sử dụng GHC) đặc biệt là đối với việc phá hủy dữ liệu.

Ví dụ, hãy xem xét mã này cho việc sáp nhập hai danh sách có thứ:

merge :: Ord a => [a] -> [a] -> [a] 
merge [] bs = bs 
merge as [] = as 
merge (a:as) (b:bs) = 
    case compare a b of 
    LT -> a : merge as (b:bs) -- (1) 
    EQ -> a : merge as bs 
    GT -> b : merge (a:as) bs -- (2) 

GHC sẽ nhận ra rằng (a:as) ở (2) và (b:bs) tại (1) cũng giống như các thông số đầu vào? Hoặc tôi nên sử dụng "là" mô hình, ví dụ .:

merge a'@(a:as) b'@(b:bs) = 
    ... 
    LT -> a : merge as b' 
    ... 
    GT -> b : merge a' bs 

Và nói chung khi GHC có thể nhận ra chung tiểu biểu trong trong công trình xây dựng dữ liệu và khi nào tôi cần phải giúp nó?

Answer 1

Điều đó tùy thuộc. Nếu bạn biên dịch mà không cần tối ưu hóa, chắc chắn là một hình phạt không sử dụng như-mô hình, nhưng nếu bạn biên dịch đoạn mã sau

module Test where 


merge1 :: Ord a => [a] -> [a] -> [a] 
merge1 [] bs = bs 
merge1 as [] = as 
merge1 (a:as) (b:bs) = case compare a b of 
    LT -> a : merge1 as (b:bs) 
    EQ -> a : merge1 as bs 
    GT -> b : merge1 (a:as) bs 


merge2 :: Ord a => [a] -> [a] -> [a] 
merge2 [] bs = bs 
merge2 as [] = as 
merge2 xs@(a:as) ys@(b:bs) = case compare a b of 
    LT -> a : merge2 as ys 
    EQ -> a : merge2 as bs 
    GT -> b : merge2 xs bs 

với -O2 và -ddump-simpl, và sau rất nhiều chỉnh sửa đúng đắn, đổi tên của biến, tước của siêu dữ liệu và chú thích, và thủ đoạn khác nhau, bạn có thể đi đến một cái gì đó giống như

merge2_2 :: Ord a => a -> [a] -> [a] -> [a] 
merge2_2 = \ ordInst x y z -> case z of _ { 
     [] -> (x:y); 
     (w:v) -> case compare ordInst x w of _ { 
      LT -> x : merge2_1 ordInst y w v; 
      EQ -> x : merge2 ordInst y v; 
      GT -> w : merge2_2 ordInst x y v 
     } 
    } 

merge2_1 :: Ord a => [a] -> a -> [a] -> [a] 
merge2_1 = \ ordInst x y z -> case x of _ { 
     [] -> (y:z); 
     (w:v) -> case compare ordInst w y of _ { 
      LT -> w : merge2_1 ordInst v y z; 
      EQ -> w : merge2 ordInst v z; 
      GT -> y : merge2_2 ordInst w v z 
     } 
    } 

merge2 :: Ord a => [a] -> [a] -> [a] 
merge2 = \ ordInst x y -> case x of wild { 
     [] -> y; 
     (w:v) -> case y of _ { 
      [] -> wild; 
      (z:zs) -> case compare ordInst w z of _ { 
       LT -> w : merge2_1 ordInst v z zs; 
       EQ -> w : merge2 ordInst v zs; 
       GT -> z : merge2_2 ordInst w v zs 
      } 
     } 
    } 


merge1_2 :: Ord a => a -> [a] -> [a] -> [a] 
merge1_2 = \ ordInst x y z -> case z of _ { 
     [] -> (x:y); 
     (w:v) -> case compare ordInst x w of _ { 
      LT -> x : merge1_1 ordInst y w v; 
      EQ -> x : merge1 ordInst y v; 
      GT -> w : merge1_2 ordInst x y v 
     } 
    } 

merge1_1 :: Ord a => [a] -> a -> [a] -> [a] 
merge1_1 = \ ordInst x y z -> case x of _ { 
     [] -> (y:z); 
     (w:v) -> case compare ordInst w y of _ { 
      LT -> w : merge1_1 ordInst v y z; 
      EQ -> w : merge1 ordInst v z; 
      GT -> y : merge1_2 ordInst w v z 
     } 
    } 

merge1 :: Ord a => [a] -> [a] -> [a] 
merge1 = \ ordInst x y -> case x of wild { 
     [] -> y; 
     (w:v) -> case y of _ { 
      [] -> wild; 
      (z:zs) -> case compare ordInst w z of _ { 
       LT -> w : merge1_1 ordInst v z zs; 
       EQ -> w : merge1 ordInst v zs; 
       GT -> z : merge1_2 ordInst w v zs 
      } 
     } 
    } 

nào, sau khi so sánh với một công cụ diffing, nói với tôi rằng sự khác biệt duy nhất giữa hai khái niệm này là những con số ở hai đầu của merge tên hàm. Vì vậy, có, sau khi áp dụng tối ưu hóa, GHC có thể tìm ra các mẫu này cho bạn, ít nhất là trong trường hợp danh sách. Tuy nhiên, tôi vẫn khuyên bạn nên sử dụng chúng bởi vì luôn có các trường hợp cạnh, và nếu bạn sử dụng chúng thì bạn không cần phải tin tưởng trình biên dịch để làm một cái gì đó phức tạp. Điều này cũng có nghĩa là ngay cả khi tối ưu hóa không được bật, mã của bạn sẽ vẫn có tối ưu hóa đó trong đó. Nó có vẻ giống như một thay đổi nhỏ, nhưng nếu chức năng này kết thúc trong một vòng lặp bên trong hoặc các cấu trúc bạn đang làm việc trên là rất lớn nó có thể có một tác động hiệu suất đáng kể. Ngoài ra, tôi thấy rằng đối với các nhà xây dựng có số lượng lớn các trường, thường thì thuận tiện hơn khi có tên để tham khảo biểu mẫu "được xây dựng".

Here's the full core dump if you're interested. Về cơ bản, tôi bắt đầu bằng cách nối các dòng với nhau để chiếm ít không gian hơn, sau đó loại bỏ các ký hiệu loại, loại bỏ các tên module đủ điều kiện, tất cả các chú thích [Something], đổi tên những thứ như merge2_$smerge2 thành merge2_2, xóa tất cả chữ ký kiểu địa phương, sau đó bắt đầu đổi tên sử dụng tính năng con trỏ tuyệt vời của Sublime Text. Tôi bắt đầu với những cái tên kiểu, đổi tên họ tất cả để chỉ a, sau đó đổi tên thành tên biến để x, y, z, w, v, và zs (Tôi sáng tạo, không phải là tôi?), Làm tất cả các ứng dụng của : infix nhà điều hành, loại bỏ các khu vực Rec, và một vài chi tiết về kiểu dáng sau này tôi đã nhận được kết quả bạn nhìn thấy ở trên.