7

長さ 2 から 15 のタプルのEq事前定義されたインスタンスがあることを知っています。

タプルは、分解できるようなある種の再帰的データ型として定義されていないのはなぜ compareですか?

結局のところ、コンパイラは任意の長さのタプルをサポートしています。

4

4 に答える 4

10

その一般化された比較関数の型は何かと自問するかもしれません。まず、コンポーネント タイプをエンコードする方法が必要です。

data Tuple ??? = Nil | Cons a (Tuple ???)

疑問符を置き換えることができる有効なものは実際にはありません。結論として、通常の ADT では不十分なので、最初の言語拡張である GADT が必要です。

data Tuple :: ??? -> * where
    Nil  :: Tuple ???
    Cons :: a -> Tuple ??? -> Tuple ???

それでも、私たちは疑問符で終わります。穴を埋めるには、さらに 2 つの拡張機能 DataKinds と TypeOperators が必要です。

data Tuple :: [*] -> * where
    Nil  :: Tuple '[]
    Cons :: a -> Tuple as -> Tuple (a ': as)

ご覧のとおり、型をエンコードするためだけに 3 つの型システム拡張が必要でした。今比較できる？スタンドアロンの比較関数を作成する方法は、実際には明らかではないため、答えるのはそれほど簡単ではありません。幸いなことに、型クラスのメカニズムにより、単純な再帰的アプローチを取ることができます。ただし、今回は値レベルだけでなく、型レベルでも再帰しています。明らかに空のタプルは常に等しいです:

instance Eq (Tuple '[]) where
    _ == _ = True

しかし、コンパイラは再び不平を言います。なんで？'[]は具象型であるため、別の拡張機能 FlexibleInstances が必要です。これで、空のタプルを比較できますが、これはそれほど魅力的ではありません。空でないタプルはどうですか？ヘッドと残りのタプルを比較する必要があります。

instance (Eq a, Eq (Tuple as)) => Eq (Tuple (a ': as)) where
    Cons x xs == Cons y ys = x == y && xs == ys

理にかなっているようですが、ブーム！別の苦情があります。コンテキストに完全にポリモーフィックではない型があるため、コンパイラは FlexibleContexts を必要としますTuple as。

これは全部で 5 つの型システム拡張であり、そのうちの 3 つは単にタプル型を表現するためのものであり、GHC 7.4 より前には存在しませんでした。他の 2 つは比較のために必要です。もちろん見返りはあります。非常に強力なタプル型が得られますが、これらすべての拡張機能のために、そのようなタプル型を基本ライブラリに入れることは明らかにできません。

于 2013-02-04T15:27:30.137 に答える
8

任意の n タプルは、バイナリ タプルに関していつでも書き換えることができます。たとえば、次の 4 タプルがあるとします。

(1, 'A', "Hello", 20)

次のように書き換えることができます。

(1, ('A', ("Hello", (20, ()))))

(,)whereが(:)(つまり "cons")()の役割を果たし、[](つまり "nil")の役割を果たしているリストと考えてください。このトリックを使用すると、「バイナリ タプルのリスト」の観点から n タプルを定式化する限り、無限に拡張でき、正しいインスタンスEqとOrdインスタンスが自動的に導出されます。

于 2013-02-04T11:55:10.830 に答える
2

のタイプはcompareですa -> a -> Ordering。これは、両方の入力が同じタイプでなければならないことを示しています。異なるアリティのタプルは、定義上、異なるタイプです。

ただし、 HListまたはGADTのいずれかを使用して問題にアプローチすることで、問題を解決できます。

于 2013-02-04T11:12:42.353 に答える
0

これを行うために単一の拡張機能は必要ないというertesの回答に追加したかっただけです。次のコードは、haskell98 および 2010 に準拠する必要があります。また、その中のデータ型は、シングルトン タプルを除いて、タプルに 1 対 1 でマッピングできます。two-tuple の後に再帰を行うと、それを達成することもできます。

module Tuple (
    TupleClass,
    TupleCons(..),
    TupleNull(..)
    ) where

class (TupleClassInternal t) => TupleClass t

class TupleClassInternal t
instance TupleClassInternal ()
instance TupleClassInternal (TupleCons a b)

data (TupleClassInternal b) => TupleCons a b = TupleCons a !b deriving (Show)

instance (Eq a, Eq b, TupleClass b) => Eq (TupleCons a b) where
    (TupleCons a1 b1) == (TupleCons a2 b2) = a1 == a2 && b1 == b2

式を導出することもできます。もちろん、TypeOperators を使用すると少しクールに見えますが、haskell のリスト システムには構文糖衣も含まれています。

于 2014-09-01T16:29:24.613 に答える