インスタンスをオーバーラップしてタプルを平坦化する

Question

タプルチェーンから空のタプルを削除するコードを作成しようとしています。コンパイラは、プログラムを拒否：

コード：

{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE FunctionalDependencies #-} 
{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE OverlappingInstances #-} 
{-# LANGUAGE UndecidableInstances #-} 
{-# LANGUAGE TypeOperators #-} 

infixr 9 :* 
data a :* b = a :* !b 
    deriving (Show, Eq, Ord) 

class Flatten a b | a -> b where 
    flatten :: a -> b 

instance Flatten a a where 
    flatten = id 

instance Flatten a b => Flatten (() :* a) b where 
    flatten (() :* y) = flatten y 

instance Flatten b c => Flatten (a :* b) (a :* c) where 
    flatten (x :* y) = x :* flatten y 


test :: Int :*() 
test = flatten $ 0 :*() 

---

[1 of 1] Compiling Main    (Test\Test.hs, interpreted) 

Test\Test.hs:26:8: 
    Overlapping instances for Flatten (Int :*()) (Int :*()) 
     arising from a use of `flatten' 
    Matching instances: 
     instance [overlap ok] Flatten a a 
     -- Defined at Test\Test.hs:15:10-20 
     instance [overlap ok] Flatten b c => Flatten (a :* b) (a :* c) 
     -- Defined at Test\Test.hs:21:10-49 
    In the expression: flatten 
    In the expression: flatten $ 0 :*() 
    In an equation for `test': test = flatten $ 0 :*() 
Failed, modules loaded: none. 

目標：

flatten (0:*():*1:*2:3:*():*():*4:*()) == (0:*1:*2:*3:*4:*()) 

Answer 1

さて、まず第一に：コンパイラは矛盾fundeps文句理由があります... を実行するとが競合するためです。あなたのやりたいことには本質的な葛藤があります。最初の型パラメータは "入力"であり、重複してデフォルトのフォールスルーケースを与えることで、特定の型に対して本質的にパターンマッチングを行います。しかし、第2の「出力」タイプのパラメータは、特定のケースとデフォルトのケースとで異なる方法で「入力」に応じて変化する必要があり、したがって競合する。これを回避するには

、インスタンスを選択するときにGHCだけインスタンスヘッドを調べるという事実を利用詐欺のビットを採用する必要があり、その後、追加の制約を適用するためにコンテキスト後でチェックします。このトリックの核心は、 "出力"型を完全に特定しないようにすることです。そのため、インスタンス選択では最初のパラメータのみが検査され、2番目のパラメータはすべてのインスタンスで同一であると考えられ、事実の後に「出力」します。

現在のGHCバージョンでこの手法を使用する最も簡単な方法は、タイプファミリを有効にして~等価制約機能を取得することです。ここでは例です：

instance (() ~ r) => Flatten (() :*()) r where 
    flatten _ =() 

instance (Flatten a r) => Flatten (() :* a) r where 
    flatten (_ :* rest) = flatten rest 

instance (a ~ r) => Flatten (a :*()) r where 
    flatten (x :* _) = x 

instance ((a :* c) ~ r, Flatten b c) => Flatten (a :* b) r where 
    flatten (x :* rest) = (x :* flatten rest) 

instance (a ~ r) => Flatten a r where 
    flatten x = x 

ても、絶対に必要ではない、私はすべてのインスタンスは、このトリックを使用し作ったパターンを説明するために。 GHCiの中で、その後

test = (0 :*() :* 1 :* 2 :* 3 :*() :*() :*4 :*()) 

そして、：：私たちは、あなたが望むの入力を定義することができ

∀x. x ⊢ flatten test 
0 :* (1 :* (2 :* (3 :* 4))) 

を今、私はGHCiののtest外を定義し、なぜあなたは不思議に思われるかもしれません。残念ながら、多相入力型に適用された場合、上記の例はがまだになりません。ファイルからロードすると、単相性制限が発生し、すべての数値リテラルをIntegerに変更します。しかし、実際には、複数の入力に一致する可能性のある型パラメータがあいまいであるため、このようなあいまいさについてはほとんどできません。

---

は、歴史的な注意点として、あなただけのfundepsとGHCの奇妙な癖を使用して、~せずに、同じトリックを行うことができます。 Olegがオリジナルで作成したのは、やや誤解を招くような名前のTypeCastであり、HListのようなものの根底にある等価述語TypeEqの実装に使用されていました。