爲什麼Haskell中的每個類型都不是Eq的一部分？

或者說，爲什麼不是每個數據類型都可以使用(==)？爲什麼我們必須得到Eq債券的最高限額？在其他語言中，比如Python，C++，當然還有其他語言，它對所有的東西都有一個默認實現！我想不出可以比較的類型。爲什麼Haskell中的每個類型都不是Eq的一部分？

來源

2012-06-08 L01man

+12

C++沒有'=='的默認實現。 – Pubby

請注意，在大多數確實具有==的默認實現的語言中，==會比較對象標識/指針值，在我的經驗中，絕大多數情況下不是您想要的。所以你仍然需要定義你自己的==，如果你想要它的行爲有用。 – sepp2k

+11

有一點需要注意：'=='在這些語言中意味着不同的東西。特別地，它是*引用*平等而不是*語義*平等（除了特殊情況下，例如它是語義的基元）。所以在Python或Java中，'x == y'只是告訴你'x'和'y'指向內存中的相同位置。（嘗試比較等價的lambda表達式）。在Haskell中，引用相等沒有意義，所以'=='* always *表示*語義*相等，這對某些類型的函數是不可判定的。例如，在Java中，您必須自己定義'.equals（）'以獲得類似的行爲。 –

在Python中，默認的相等實現比較標識，而不是值。這對於用戶定義的類非常有用，默認情況下它們是可變的，並且不必具有「值」的明確定義的概念。但即使在這種情況下，使用is運算符直接比較可變對象的身份也是比較正常的。

隨着Haskell的不變性和共享這個「身份」的概念沒有多大意義。如果你可以通過身份比較兩個術語，你可以找出他們是否被共享，但是一般來說，實現兩個可能共享的術語是否是共享的，這樣的信息不應該能夠影響該程序（除非你在之類的程序在不同的編譯器優化策略下改變它們的行爲）。

所以在哈斯克爾平等總是值平等;它告訴你兩個詞是否代表相同的值（不一定它們是否具有相同的結構;如果你實現了一個具有無序列表的集合，那麼兩個具有不同結構的列表可以代表同一集合）。

幾乎所有的內置類型都已經是Eq的成員;最大的例外是函數類型。對於函數來說，唯一真正合理的價值平等概念是擴展平等（它們是否爲每個輸入返回相同的輸出）。我們很想說我們會使用它，讓編譯器訪問函數定義的表示來計算它，但不幸的是，確定兩個任意算法（這裏用Haskell語法編碼）總是產生相同的輸出是一個已知的不可計算的問題;如果編譯器實際上可以做到這一點，它可以解決停機問題，我們將不必忍受作爲每種類型成員的最低值。

不幸的是，功能不能成爲Eq的成員意味着很多其他的東西也不能;可以比較整數列表是否相等，但函數列表不可以，並且每個其他conatiner-ish類型在包含函數時也是如此。這也適用於你編寫的ADT，除非有一個明確的平等概念，你可以爲這種類型定義不依賴於所包含函數的相等性（也許該函數只是實現中的一種方便，函數它不會影響您用ADT表示的值）。

因此，有（1）的類型是已經的Eq構件，（2）類型的不能是Eq成員，（3）的類型，可以是Eq成員的明顯的方式，（ 4）類型可以成爲Eq的成員，但僅以非顯而易見的方式，以及（5）類型可以以明顯的方式成爲Eq的成員，但程序員會喜歡另一種方式。我認爲Haskell處理這些案例的方式實際上是正確的。（1）和（2）不需要你的任何東西，（4）和（5）總是要求明確的實例聲明。編譯器可以幫助你多一點的唯一情況是（3），它可以爲你節省12個字符的鍵入（如果你已經是deriving其他的話）。

我認爲這將是一個相當小的成本贏。編譯器將不得不嘗試來構造一切的一個實例，並假定任何失敗的東西都不應該有一個Eq實例。目前，如果你想派生一個Eq實例並且意外地寫出了一個不起作用的類型，那麼編譯器會告訴你那裏和那裏有問題。隨着提議「隱含使所有的東西你可以」的策略，這個錯誤將顯示爲一個不明原因的「沒有Eq實例」的錯誤，在這一點上你去使用假設的實例。這也意味着，如果我想到的類型代表價值的合理平等關係不是簡單的結構相等（上面的情況（5）;請記住由無序列表表示的集合？），我忘記編寫我自己的Eq實例，那麼編譯器可能會自動爲我生成一個錯誤的實例。當我使用它時，我寧願被告知「你還沒有編寫一個Eq實例」，而不是編譯程序並編譯並運行編譯器引入的錯誤！

來源

2012-06-09 00:30:23 Ben

第一個Haskell標準實際規定，如果您省略了數據類型的派生子句，您將獲得儘可能多的類派生。這後來被改變了，因爲有些類是不可預測的。 – augustss

這顯然是迄今爲止最好的答案。我推薦它接受。 – usr

因爲值的比較方式可能是自定義的。例如，某些「字段」可能會被排除在比較之外。

或考慮表示不區分大小寫的字符串的類型。這種類型不想比較它包含的身份。

來源

2012-06-08 21:51:30 usr

謝謝。那麼，爲什麼沒有'（==）'的默認實現，或者另外一個運算符來檢查這兩個值是否完全相同，如'（===）'或'is'。我現在明白一些類型需要'（==）'的不同實現，但是並不是所有類型都需要至少缺省實現？有沒有比較不需要的特殊設計案例？ – L01man

@usr：yup除了理論上的答案，即不可能測試函數類型的平等，這是另一個更實際的答案，即「非函數類型怎麼樣？」的問題。另一個例子是表示集合（或地圖）的搜索樹：兩個不同的搜索樹可以表示相同的集合。 –

@ L01man：一旦添加模塊化和封裝，功能平等的不可判定性就有可能感染整個語言。我可以編寫一個庫來導出一個雙參數類型'Foo'，但不包含它的構造函數;使用'Foo'的唯一方法是我輸出的常量和函數。你不知道'Foo a b'類型的值是否包含一個隱藏的函數，我可以改變實現來使用一個適當的實現。然而，根據你的提議，如果'Foo'得到一個隱式的'Eq'實例，你可以編寫代碼，在稍後改變我的類型的實現。 –

你無法想象一個不可比擬的類型？那麼，經典的例子就是函數。考慮功能[()]->Bool。兩個這樣的函數在爲每個可能的輸入返回相同的值時是相等的。但是「不幸的是」，有無數的這樣的列表：由於Haskell是懶惰的，列表大小甚至沒有被內存限制。當然，您可以比較每個列表輸入的長度小於某個固定的長度，但您將在哪裏畫線？無法確定您比較的功能在經過1000000000次相同回報後，會突然返回replicate 1000000001()的不同結果。因此(==) :: ([()]->Bool) -> ([()]->Bool) -> Bool永遠不會實際返回True，只有False（如果發現功能不同的輸入）或⟂（如果功能實際上相同）。但是你不能評估⟂。

來源

2012-06-08 21:55:43 leftaroundabout

但是看着這些函數的實現，編譯器可以說它們是否相等？如果他不能，那麼'（==）'至少要確保對類型爲'*'的類型正確回答？ – L01man

僅僅因爲兩個函數有不同的實現，這並不意味着它們不相等。 – dave4420

例如考慮'heapSort，quickSort，bubbleSort :: [Int] - > [Int]'。它們都是平等的，即對於任何給定的輸入，它們都產生相同的輸出。但它們是具有不同性能特徵的不同實現。比較函數應該如何解決它們是平等的？ – dave4420

如何比較功能？或存在類型？還是MVars？

有無與倫比的類型。

編輯：MVar is in Eq！

instance Eq (MVar a) where 
     (MVar mvar1#) == (MVar mvar2#) = sameMVar# mvar1# mvar2#

但它需要一個神奇的primop使它如此。

來源

2012-06-08 23:33:53

['MVar'是'Eq'的一個實例。]（http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-MVar.html#g:1） –

它的確是！但這是新的（因爲西蒙的IO重寫） - 並且需要魔法才能實現。 –

我想不出無法比較的類型。

let infiniteLoop = infiniteLoop 

let iSolvedTheHaltingProblem f = f == infiniteLoop 
-- Oops!

來源

2012-06-09 04:41:31

男人，人們只是愛減少到停止問題：P在這種情況下，我認爲'=='返回，是一個無限循環是完全合理的。就像你做了[] == filter（not。sumOfTwoPrimes）[2，4 ..]'（注意這個*確實是* typecheck） –

當你說'let infiniteLoop = infiniteLoop'時，你的意思是，例如，'let infiniteLoop = [1 ..]'？ – L01man

不可以。拿出'[1 ..]'的'head'和'tail'，並且通常儘可能地計算它。如果您嘗試從中提取任何值，「infiniteLoop」將會掛起。 – hmp

考慮以下Python的例子：

>>> 2 == 2 
True 
>> {} == {} 
True 
>>> set() == set() 
True 
>>> [1,2,3] == [1,2,3] 
True 
>>> (lambda x: x) == (lambda x: x) 
False

假？ o_O這當然是有道理的，如果你意識到Python ==比較指針值，除非它不。

>>> f = (lambda x: x) 
>>> f == f 
True

哈斯克爾鼓勵==到總是代表結構相等（它總是會，如果你使用deriving Eq。因爲沒有人真正知道一個完全的聲音和易於處理的方式對某些聲明兩個函數是否是結構上等同，沒有Eq實例功能通過擴展，存儲在其中的功能不能是Eq實例的任何數據結構

來源

2012-06-09 09:30:49

說任何存儲一個*任意*函數的數據結構不能是Eq的一個實例，或者至少不是以一種自然的方式（很多類型有不嚴格的結構相等的Eq實例：當這是一個好主意的時候，例子是延遲的bytestrings，它們在比較時是不同的）。一些功能類型是可比的。 –

@benmachine「某些函數類型是可比較的」 - 哪些？ '（） - > Foo'就是我想的，只需定義（==）= on（==）（$（））'。還有更多有趣的可比較函數類型的例子嗎？ –

那麼，'布爾 - >布爾'，一個。一般而言，任何有限的可枚舉類型都可以使用任何equatable類型，儘管該域必須很小才能實現實現:)但是，更多的魔法是可能的 - 請參閱http://math.andrej.com/2007/09/ 28 /看似不可能的功能程序/（即使我在不同的評論線程中誤用了它） –

你可能不希望派生式。 - 你可能要編寫自己的實例

。

例如，在二叉樹的數據結構想象數據：

data Tree a = Branch (Tree a) (Tree a) 
      | Leaf a

你可以在你的Leaf S中的數據相同，但不同的平衡。例如：

balanced = Branch (Branch (Leaf 1) 
          (Leaf 2)) 
        (Branch (Leaf 3) 
          (Leaf 4)) 

unbalanced = Branch (Branch (Branch (Leaf 1) 
            (Leaf 2)) 
          (Leaf 3)) 
        (Leaf 4) 

shuffled = Branch (Branch (Leaf 4) 
          (Leaf 2)) 
        (Branch (Leaf 3) 
          (Leaf 1))

數據被存儲在一個樹可能僅是遍歷的效率，在這種情況下，你可能要說，balanced == unbalanced的事實。你甚至可以說這是balanced == shuffled。

來源

2012-06-10 03:25:01 amindfv

爲什麼Haskell中的每個類型都不是Eq的一部分？

回答

相關問題