Haskell: Tại sao mẫu khớp với công việc cho các loại mà không phải là trường hợp bình đẳng?

Question

Tôi đã tự hỏi làm thế nào mô hình phù hợp trong các công trình Haskell, tôi nhận thức được thread này, nhưng không thể hoàn toàn hiểu được câu trả lời trong đó.

How does Haskell do pattern matching without us defining an Eq on our data types?

• Những câu trả lời nêu rõ rằng các loại được kết hợp bởi các biểu thức Boolean nhưng làm thế nào có thể như vậy.
• Điều khác tôi nhận được là đối sánh mẫu tổng quát hơn (==) và Eq được triển khai bằng cách sử dụng đối sánh mẫu.

Vì vậy, bạn có thể cho tôi biết tại sao match và match3 đang làm việc ngay cả khi tôi bỏ qua deriving (Eq) trong đoạn mã sau, (nó là rõ ràng lý do tại sao match2 là không).

data MyType = TypeA | TypeB 
      deriving (Eq) 

match :: MyType -> String 
match TypeA = "this is type A" 
match TypeB = "this is type B" 

match2 :: MyType -> String 
match2 a | a == TypeA = "this is type A matched by equality" 
     | a == TypeB = "this is type B matched by equality" 
     | otherwise = "this is neither type A nor type B" 

match3 :: MyType -> String 
match3 a = case a of TypeA -> "this is type A matched by case expression" 
        TypeB -> "this is type B matched by case expression" 

main :: IO() 
main = do 
    (print . match) TypeA 
    (print . match) TypeB 
    (print . match2) TypeA 
    (print . match2) TypeB 
    (print . match3) TypeA 
    (print . match3) TypeB 

Answer 1

Tôi chỉ muốn chỉ ra rằng các kiểu dữ liệu và đối sánh mẫu (tính xấp xỉ đầu tiên) chỉ là tính năng ngôn ngữ hữu ích nhưng dư thừa, có thể được triển khai hoàn toàn bằng cách sử dụng phép tính lambda. Nếu bạn hiểu cách triển khai chúng trong phép tính lambda, bạn có thể hiểu tại sao chúng không cần Eq để thực hiện khớp mẫu.

Thực hiện các loại dữ liệu trong phép tính lambda được gọi là "Giáo hóa mã hóa" chúng (sau khi Alonzo Church, người đã chứng minh làm thế nào để làm điều này). Các chức năng được mã hóa của Giáo hội còn được gọi là "Kiểu chuyển tiếp liên tục".

Nó được gọi là "kiểu chuyển tiếp liên tục" bởi vì thay vì cung cấp giá trị, bạn cung cấp một hàm sẽ xử lý giá trị. Vì vậy, ví dụ, thay vì đưa ra một người dùng một Int, tôi có thể thay vì cung cấp cho họ một giá trị của các loại sau đây:

type IndirectInt = forall x . (Int -> x) -> x 

Loại trên là "đẳng cấu" một Int. "Đẳng cấu" chỉ là một cách ưa thích để nói rằng chúng ta có thể chuyển đổi bất kỳ IndirectInt thành một Int:

fw :: IndirectInt -> Int 
fw indirect = indirect id 

... và chúng ta có thể chuyển đổi bất kỳ Int thành một IndirectInt:

bw :: Int -> IndirectInt 
bw int = \f -> f int 

... sao cho:

fw . bw = id -- Exercise: Prove this 
bw . fw = id -- Exercise: Prove this 

Sử dụng kiểu chuyển tiếp liên tục, chúng tôi có thể chuyển đổi bất kỳ loại dữ liệu nào thành thuật ngữ lambda-calculus.Hãy bắt đầu với một kiểu đơn giản như:

data Either a b = Left a | Right b 

Trong phong cách tiếp-đi qua, điều này sẽ trở thành:

type IndirectEither a b = forall x . (Either a b -> x) -> x 

Nhưng Alonzo Church là thông minh và nhận thấy rằng đối với bất kỳ loại với nhiều nhà xây dựng, chúng ta có thể chỉ cung cấp một hàm riêng biệt cho mỗi hàm tạo. Vì vậy, trong trường hợp của các loại trên, thay vì cung cấp một chức năng của loại (Either a b-> x), chúng tôi thay vì có thể cung cấp hai chức năng riêng biệt, một cho a, và một cho b, và đó sẽ là chỉ là tốt:

type IndirectEither a b = forall x . (a -> x) -> (b -> x) -> x 
-- Exercise: Prove that this definition is isomorphic to the previous one 

Điều gì về một loại như Bool nơi các nhà thầu không có đối số? Vâng, Bool là đẳng cấu với Either()() (Tập thể dục: Chứng minh điều này), vì vậy chúng tôi chỉ có thể mã hóa nó như:

type IndirectBool = forall x . (() -> x) -> (() -> x) -> x 

Và () -> x chỉ là đẳng cấu với x (Tập thể dục: Chứng minh điều này), vì vậy chúng tôi có thể tiếp tục viết lại nó như là :

type IndirectBool = forall x . x -> x -> x 

chỉ có hai chức năng mà có thể có các loại trên:

true :: a -> a -> a 
true a _ = a 

false :: a -> a -> a 
false _ a = a 

Do i định hình, chúng ta có thể đảm bảo rằng tất cả các bảng mã của Giáo hội sẽ có nhiều triển khai vì có thể có giá trị của kiểu dữ liệu gốc, vì vậy không có trùng hợp ngẫu nhiên rằng có hai hàm chính xác là IndirectBool, giống như có hai nhà xây dựng chính xác cho Bool.

Nhưng làm cách nào để chúng tôi khớp mẫu trên IndirectBool của chúng tôi? Ví dụ, với một bình thường Bool, chúng ta có thể chỉ cần viết:

expression1 :: a 
expression2 :: a 

case someBool of 
    True -> expression1 
    False -> expression2 

Vâng, với chúng tôi IndirectBool nó đã đi kèm với những công cụ để giải cấu trúc riêng của mình. Chúng tôi sẽ chỉ cần viết:

myIndirectBool expression1 expression2 

Chú ý rằng nếu myIndirectBool là true, nó sẽ chọn các biểu hiện đầu tiên, và nếu nó là false nó sẽ lấy biểu thức thứ hai, cũng giống như khi chúng tôi đã bằng cách nào đó mô hình kết hợp trên giá trị của nó .

Hãy thử làm điều tương tự với số IndirectEither. Sử dụng một bình thường Either, chúng tôi muốn viết:

f :: a -> c 
g :: b -> c 

case someEither of 
    Left a -> f a 
    Right b -> g b 

Với IndirectEither, chúng tôi chỉ cần viết:

someIndirectEither f g 

Nói tóm lại, khi chúng ta viết các loại trong phong cách tiếp-đi qua, các continuations là giống như các câu lệnh case của một trường hợp xây dựng, vì vậy tất cả những gì chúng ta đang làm là chuyển qua từng câu lệnh case khác nhau như các đối số cho hàm.

Đây là lý do bạn không cần bất kỳ ý nghĩa nào về số Eq đối với kiểu đối sánh trên một loại. Trong phép tính lambda, kiểu quyết định cái gì là "bằng" chỉ đơn giản bằng cách xác định đối số nào mà nó chọn ra từ đối số được cung cấp cho nó.Vì vậy, nếu tôi là một true, tôi chứng minh tôi "bằng" với true bằng cách luôn chọn đối số đầu tiên của tôi. Nếu tôi là false, tôi chứng minh rằng tôi "bằng" thành false bằng cách luôn chọn đối số thứ hai của mình. Trong ngắn hạn, hàm tạo "bình đẳng" tóm tắt thành "đẳng thức vị trí", luôn luôn được định nghĩa trong phép tính lambda, và nếu chúng ta có thể phân biệt một tham số là "đầu tiên" và khác là "thứ hai", đó là tất cả những gì chúng ta cần khả năng "so sánh" các nhà xây dựng.

Answer 2

Điều bạn đang thiếu là các nhà thầu trong Haskell có thể có đối số. Các thẻ loại "bản thân" có thể so sánh được bằng bình đẳng (ít nhất là nội bộ, đằng sau hậu trường), nhưng các giá trị đầy đủ chỉ có thể so sánh được nếu các đối số thành phần cũng có thể so sánh được.

Vì vậy, nếu bạn có một loại giống như

data Maybe a = Nothing | Just a 

sau đó mặc dù bạn có thể kiểm tra nếu thẻ loại là "Không có gì" hoặc "Chỉ" (tức .; mô hình phù hợp về giá trị có thể) nói chung bạn không thể so sánh đầy đủ có thể trừ khi giá trị của loại "a" đang được tổ chức bởi Chỉ cần cũng xảy ra để được so sánh.

--note that your first and third examples are 
--just syntactic sugar for each other... 
matchMaybe mb = case mb of 
    Nothing -> "Got a Nothing" 
    Just _ -> "Got a Just but ignored its value" 

Bây giờ cũng phải rõ ràng lý do tại sao không thể viết biến thể của match2 cho Maybes. Bạn sẽ sử dụng cái gì để kiểm tra sự bình đẳng trong trường hợp Chỉ cần?

matchMaybe_2 mb | mb == Nothing = "Got a Nothing" 
       | mb == Just {- ??? -} = "This case is impossible to write like this" 

Answer 3

Trước hết, match và match3 thực sự giống hệt nhau (bỏ qua các dây khác nhau): mô hình phù hợp trong các chức năng được khử đường một tuyên bố như vậy.

Tiếp theo, đối sánh mẫu hoạt động trên hàm tạo thay vì giá trị tùy ý. Kết hợp mẫu được xây dựng thành ngôn ngữ và không phụ thuộc vào các biểu thức boolean - nó chỉ hoạt động trực tiếp trên các hàm tạo. Điều này hiển nhiên nhất với các kết hợp phức tạp hơn bao gồm một số cụm từ phù hợp:

f :: MyType -> Int 
f (A a) = a + 1 
f (B a b) = a + b 

Bạn sẽ viết lại các mẫu này thành các biểu thức logic? Bạn không thể (không biết bất cứ điều gì khác về MyType).

Thay vào đó, đối sánh mẫu chỉ được thực hiện bởi hàm tạo. Mỗi mẫu phải được chỉ dẫn bởi một hàm tạo - bạn không thể viết một mẫu như f (a b c) trong Haskell. Sau đó, khi hàm nhận được một giá trị, nó có thể nhìn vào hàm tạo của giá trị và nhảy tới các trường hợp thích hợp ngay lập tức. Đây là cách nó phải làm việc cho các mẫu phức tạp hơn (như A a), và cũng là cách nó hoạt động cho các mẫu đơn giản mà bạn đã sử dụng.

Vì khớp mẫu chỉ hoạt động bằng cách đi tới hàm tạo thích hợp, nó không phụ thuộc vào Eqtại tất cả.Bạn không chỉ phải có một phiên bản Eq đối với đối sánh mẫu, mà còn có thể không thay đổi cách đối sánh mẫu hoạt động. Ví dụ, hãy thử này:

data MyType = TypeA | TypeB | TypeC 

instance Eq MyType where 
    TypeA == TypeA = True 
    TypeB == TypeC = True 
    TypeC == TypeB = True 
    _ == _   = False 

match :: MyType → String 
match TypeA = "this is type A" 
match TypeB = "this is type B" 
match TypeC = "this is type C" 

match2 :: MyType → String 
match2 a | a == TypeA = "this is type A matched by equality" 
     | a == TypeC = "this is type B matched by equality" 
     | a == TypeB = "this is type C matched by equality" 
     | otherwise = "this is neither type A nor type B" 

Bây giờ bạn đã xác định sự bình đẳng như vậy mà TypeB bằng TypeC nhưng không phải cho chính nó. (Trong thực tế, bạn nên đảm bảo rằng sự bình đẳng hoạt động hợp lý và tuân theo thuộc tính phản xạ, nhưng đây là ví dụ đồ chơi.) Bây giờ, nếu bạn sử dụng đối sánh mẫu, TypeB vẫn khớp với TypeB và TypeC khớp với TypeC. Nhưng nếu bạn sử dụng biểu thức bảo vệ, TypeB thực sự khớp với TypeC và TypeC khớp với TypeB. TypeA không thay đổi giữa hai.

Ngoài ra, lưu ý cách thể hiện Eq được xác định sử dụng kết hợp mẫu. Khi bạn sử dụng mệnh đề deriving, nó được định nghĩa theo cách tương tự với mã được tạo tại thời gian biên dịch. Vì vậy, mô hình phù hợp là cơ bản hơn Eq - nó là một phần của ngôn ngữ nơi Eq chỉ là một phần của thư viện chuẩn.

Tóm lại: kết hợp mẫu được tích hợp vào ngôn ngữ và hoạt động bằng cách so sánh hàm tạo và sau đó đối chiếu đệ quy trên phần còn lại của giá trị. Tính bình đẳng thường được thực hiện theo kiểu so khớp mẫu và so sánh toàn bộ giá trị chứ không chỉ là hàm tạo.

Answer 4

Cách tôi nghĩ về nó, khớp mẫu về cơ bản là bình đẳng bitwise. Nó dựa trên các loại, không phải một số khái niệm trừu tượng về giá trị.

Hãy ghi nhớ tuy nhiên, bạn nên nghĩ đến nói Int như

data Int = ... | -2 :: Int | -1 :: Int | 0 :: Int | 1 :: Int | 2 :: Int | ... 

Vì vậy, trong một cách, mỗi số nguyên có một kiểu khác nhau.

Đó là lý do bạn có thể đối sánh với số Int nói 2.

Eq đi xa hơn một chút, nó cho phép bạn thiết lập mọi thứ bằng nhau có thể không giống nhau.

Ví dụ: bạn có thể có cây nhị phân lưu trữ các phần tử được sắp xếp. Nói như sau:

A  A 
/\ /\ 
B C B D 
    \ \ 
     D C 

Có thể được coi là bình đẳng bởi Eq, vì chúng có chứa các yếu tố tương tự, nhưng bạn sẽ không thể để kiểm tra bình đẳng ở đây sử dụng kết hợp mô hình. Tuy nhiên, trong trường hợp các số, sự bình đẳng bit về cơ bản giống như bình đẳng logic (ngoại trừ có lẽ là dấu phẩy động và dương) 0.0) vì vậy ở đây Eq và mẫu phù hợp tương đương nhau.

---

Đối với một tương tự với C++, suy nghĩ của Eq như operator== và mô hình kết hợp như memcmp. Bạn có thể so sánh nhiều loại cho sự bình đẳng chỉ bằng cách sử dụng memcmp, nhưng một số bạn không thể, nếu chúng có thể có các biểu diễn khác nhau cho các giá trị "bằng nhau".