4

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

コード：

{-# 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:*())
4

1 に答える 1

10

さて、まず第一に：コンパイラがfundepsの競合について不平を言う理由は...競合するからです。それ自体を回避する方法は実際にはありません。競合は、あなたがやろうとしていることに固有のものです。最初のタイプパラメータは「入力」であり、基本的に特定のタイプのパターンマッチングであり、オーバーラップするとデフォルトのフォールスルーケースが発生します。ただし、2番目の「出力」タイプのパラメーターは、特定のケースとデフォルトのケースで異なる方法で「入力」に応じて変化する必要があるため、競合が発生します。

これを回避するには、GHCがインスタンスを選択するときにインスタンスヘッドのみを調べ、後でコンテキストをチェックして追加の制約を適用するという事実を利用して、少し巧妙な方法を採用する必要があります。トリックの核心は、「出力」タイプを完全に指定しないままにすることです。これにより、インスタンス選択は最初のパラメーターのみを調べ、2番目のパラメーターをすべてのインスタンスで同一であると見なし、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

私がすべてのインスタンスに作成したパターンを説明するために、絶対に必要ではない場合でも、このトリックを使用します。必要な入力を定義できます。

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

そして、GHCiでは：

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

さて、なぜ私testがGHCiの外で定義したのか疑問に思われるかもしれません。残念ながら、上記のインスタンスはポリモーフィック入力タイプに適用された場合でも失敗し、ファイルからロードすると、単相制限とタイプのデフォルトがすべての数値リテラルをに変換しIntegerます。ただし、複数の入力に一致する可能性のある型パラメーターは実際にはあいまいであるため、このようなあいまいさについてできることは実際にはあまりありません。

~歴史的なメモとして、 GHCのfundepsと奇妙な癖だけを使用して、なしで同じトリックを行うことができます。これのいくつかのバージョンは、多くのばかげたタイプのハッカーに必要であり、オリジナルは（当然のことながら）Olegによって発明され、わずかに誤解を招く名前で呼ばれ、 HListなどの基礎となるTypeCast平等述語を実装するために使用されました。TypeEq

于 2012-01-07T03:30:07.527 に答える