16

間違った用語を使用している場合はご容赦ください。私は haskell 型操作の初心者です... HList を使用して型レベルのプログラミングを行うために、関数の依存関係を持つ重複するインスタンスを使用しようとしています。

ここでの私の目的は、 typeclass を試して書くことですHNoNils l l'。これは、リスト型 (例: ) である場合、特定の空の型を持たない対応するリスト型( example: の結果) であるHNoNils l l'ことを意味します。lInt : String : EmptyNil : Int : HNill'EmptyNilInt:String:Int:HNil

{-# LANGUAGE ExistentialQuantification,
  FunctionalDependencies,
  FlexibleInstances,
  UndecidableInstances,
  OverlappingInstances,
  TypeFamilies #-}

import Data.HList 
import Data.TypeLevel.Bool

--Type Equality operators
--usedto check if a type is equal to another
class TtEq a b eq | a b -> eq
instance     TtEq a a True
instance eq~False => TtEq a b eq 


data EmptyNil = EmptyNil deriving (Show) --class representing empty channel
--class intended to generate a list type with no type of EmptyNil
-- Example: HCons Int $ HCons EmptyNil HNil should give HCons Int HNil
class (HList list, HList out) => HNoNils list out | list -> out 
    where  hNoNils :: list -> out 

-- l gives l' means (HCons EmptyNil l) gives l'
instance (HNoNils l l',TtEq e EmptyNil True ) => HNoNils (HCons e l) l'
    where hNoNils (HCons e l) = hNoNils l

-- l gives l' means (HCons e l) gives (HCons e l') for all e 
instance (HNoNils l l') => HNoNils (HCons e l) (HCons e l')
    where hNoNils (HCons e l) = hCons e $ hNoNils l

--base case
instance  HNoNils HNil HNil
    where hNoNils _ = hNil

testList  = HCons EmptyNil $ HCons EmptyNil HNil
testList1 = HCons "Hello"  $ HCons EmptyNil HNil 
testList2 = HCons EmptyNil $ HCons "World"  HNil
testList3 = HCons "Hello"  $ HCons "World"  HNil

main:: IO ()
main = do
    print $ hNoNils testList  -- should get HNil
    print $ hNoNils testList1 -- should get HCons "Hello" HNil
    print $ hNoNils testList2 -- should get HCons "World" HNil
    print $ hNoNils testList3 -- should get HCons "Hello" (HCons "World" HNil)

ただし、このコードをそのまま実行すると、すべてのhNoNils呼び出しが、最も具体的でない 2 番目のインスタンス宣言によって解決されるように見えlますHNoNils l l

私が読んだことに基づいて、OverlappingInstances拡張機能を使用すると、システムは常に最も具体的なインスタンスに解決されるはずです。

ここ

  • 最初のインスタンスには制約があります(HNoNils l l',TtEq e EmptyNil True )

  • 2 番目のインスタンスには制約がありますHNoNils l l'

私が間違っていたらすみませんが、最初のインスタンスは 2 番目のインスタンスよりも具体的なようです。

オーバーラップを取り除くために制約を追加しようとしました。つまり、2 番目のインスタンスに別の反対の等式制約を追加してみました。

-- l gives l' means (HCons EmptyNil l) gives l'
instance (HNoNils l l',TtEq e EmptyNil True ) => HNoNils (HCons e l) l'
    where hNoNils (HCons e l) = hNoNils l

-- l gives l' means (HCons e l) gives (HCons e l') for all e 
-- added constraint of TtEq e EmptyNil False
instance (HNoNils l l',TtEq e EmptyNil False) => HNoNils (HCons e l) (HCons e l')
    where hNoNils (HCons e l) = hCons e $ hNoNils l

ここで重複するインスタンス拡張機能を削除しようとしましたが、重複エラーが発生しています。

Overlapping instances for HNoNils
                                (HCons EmptyNil (HCons [Char] HNil)) (HCons EmptyNil l')
Matching instances:
      instance (HNoNils l l', TtEq e EmptyNil True) =>
               HNoNils (HCons e l) l'
        -- Defined at /home/raphael/Dropbox/IST/AFRP/arrow.hs:32:10
      instance (HNoNils l l', TtEq e EmptyNil False) =>
               HNoNils (HCons e l) (HCons e l')
        -- Defined at /home/raphael/Dropbox/IST/AFRP/arrow.hs:36:10

2戦目はわかりません。結局のところ、この解像度では、e は EmptyNil に等しいので、TtEq e EmptyNil True... ですよね? さらに言えば、型システムがこの質問をしている状況にどのように到達するのでしょうか。結局のところ、制約があるため、そのような状況になることは決してありHNoNils (Hcons EmptyNil l) (HCons EmptyNil l'))ません。

OverlappingInstances を追加し直すと、理解できないさらに奇妙なエラーが発生します。

 Couldn't match type `True' with `False'
    When using functional dependencies to combine
      TtEq a a True,
        arising from the dependency `a b -> eq'
        in the instance declaration at /home/raphael/Dropbox/IST/AFRP/arrow.hs:23:14
      TtEq EmptyNil EmptyNil False,
        arising from a use of `hNoNils'
        at /home/raphael/Dropbox/IST/AFRP/arrow.hs:53:13-19
    In the second argument of `($)', namely `hNoNils testList2'
    In a stmt of a 'do' block: print $ hNoNils testList2

2 番目のステートメント はTtEq EmptyNil EmptyNil False、関数呼び出しによってインスタンスが生成されたと言っているようです...? どこから来たのか少し混乱しています。

だから、これを理解しようとして、私は疑問に思っていました:

  • Haskell がインスタンスでどのように機能するかについて、より詳細な情報を得ることができますか? これらの組み合わせのいくつかは不可能に思えます。メカニズムを説明するドキュメントへのリンクだけでもいただければ幸いです

  • どのように機能するかについて、より具体的な定義はありOverlappingInstancesますか? 私は何かが欠けているように感じます(おそらく「特異性」引数は、制約の数ではなく、型変数でのみ機能します...)

編集:したがって、CA McCannの提案の1つ(制約の一部を削除)を次のように試しました:

instance (HNoNils l l') => HNoNils (HCons EmptyNil l) l'

instance (HNoNils l l') => HNoNils (HCons e l) (HCons e l')

instance  HNoNils HNil HNil

これを行うと、いくつかの厄介な重複インスタンスエラーが発生します:

Overlapping instances for HNoNils
                                (HCons EmptyNil (HCons [Char] HNil)) (HCons EmptyNil l')
      arising from a use of `hNoNils'
    Matching instances:
      instance [overlap ok] HNoNils l l' => HNoNils (HCons EmptyNil l) l'
        -- Defined at /Users/raphael/Dropbox/IST/AFRP/arrow.hs:33:10
      instance [overlap ok] HNoNils l l' =>
                            HNoNils (HCons e l) (HCons e l')
        -- Defined at /Users/raphael/Dropbox/IST/AFRP/arrow.hs:37:10

解決方法がボトムアップではなくトップダウンであるかのように感じます (システムがこのようなインスタンスを見つけようとしない場合)。

編集 2 : 2 番目の条件に小さな制約を追加することで、期待どおりの動作が得られました (McCann の回答に関するコメントを参照してください)。

-- l gives l' means (HCons EmptyNil l) gives l'
instance (HNoNils l l') => HNoNils (HCons EmptyNil l) l'
    where hNoNils (HCons EmptyNil l) = hNoNils l

-- l gives l' means (HCons e l) gives (HCons e l') for all e 
instance (HNoNils l l',r~ HCons e l' ) => HNoNils (HCons e l) r
    where hNoNils (HCons e l) = hCons e $ hNoNils l

ここで追加さr~HCons e l'れたのは、2 番目のインスタンスに対する制約です。

4

1 に答える 1

15

Haskell がインスタンスでどのように機能するかについて、より詳細な情報を得ることができますか? これらの組み合わせのいくつかは不可能に思えます。メカニズムを説明するドキュメントへのリンクだけでもいただければ幸いです

Haskellがインスタンスを操作する方法は非常に単純です。GHC が提供する複数の実験的な言語拡張を扱っているため、主な情報源はGHC User's Guideです。

OverlappingInstances がどのように機能するかについて、より具体的な定義はありますか? 私は何かが欠けているように感じます(おそらく「特異性」引数は、制約の数ではなく、型変数でのみ機能します...)

あなたの推測は正しいです。説明するユーザーズガイドセクションOverlappingInstancesから:

GHC がたとえば制約を解決しようとするときC Int Bool、インスタンス宣言の先頭をインスタンス化することによって、すべてのインスタンス宣言を制約と一致させようとします。たとえば、次の宣言を考えてみましょう。

instance context1 => C Int a     where ...  -- (A)
instance context2 => C a   Bool  where ...  -- (B)
instance context3 => C Int [a]   where ...  -- (C)
instance context4 => C Int [Int] where ...  -- (D)

インスタンス (A) と (B) は制約C Int Boolに一致しますが、(C) と (D) は一致しません。context1マッチングの際、GHC はインスタンス宣言 (など)のコンテキストを考慮しません。

パターンとガードのようなものと考えてください:

instanceOfC Int a | context1 Int a = ...
instanceOfC a Bool | context2 a Bool = ...

型クラスは「オープン」であるため、関数の場合のように明確に定義された一致順序はありません。そのため、代わりに同じ引数に一致する「パターン」に制限があります。パターンとガードへの類推については、以前の回答でさらに詳しく説明しました。

上記のアナロジーを使用してインスタンスを疑似関数に変換すると、結果は次のようになります。

hNoNils (e:l) | e == EmptyNil = hNoNils l
hNoNils (e:l) = e : hNoNils l
hNoNils [] = []

「パターン」を選択するときに「ガード」が無視されることを知っているので、最初の 2 つのパターンを区別できないことは明らかです。


しかし、現在機能していない理由だけでなく、物事を機能させる方法を知りたいと思うでしょう。(NB -- 私は現在 GHC を手元に持っていないので、これはすべて記憶によるものであり、テストされていません。いくつかの詳細が間違っている可能性があります。)

この種の処理にはいくつかの方法があります。おそらく最も一般的なのは、最初にジェネリック インスタンスのコンテキストで型関数を使用し、その後、追加のパラメーターを受け取る補助クラスの特定のインスタンスを延期するという 2 段階のプロセスです。

class FooConstraint a b r | a b -> r  -- some sort of type predicate


-- the "actual" type function we want
class (FooConstraint a b result, FooAux a b result c) => Foo a b c | a b -> c

-- a single maximally generic instance
instance (FooConstraint a b result, FooAux a b result c) => Foo a b c 


-- this class receives the original a and b as arguments, but also the 
-- output of the predicate FooConstraint
class FooAux a b result c | a b result -> c

-- which lets us indirectly choose instances based on a constraint
instance ( ... ) => FooAux a b True c 
-- more instances, &c.

ご覧のとおり、これは非常に面倒ですが、時にはそれだけで十分な場合もあります。

幸いなことに、あなたのケースははるかに簡単です。上記の疑似関数への変換を思い出してください。実際にその関数をそのように記述しますか? もちろん、そうではありません。次のように明確になるからです。

hNoNils (EmptyNil:l) = hNoNils l
hNoNils (e:l) = e : hNoNils l
hNoNils [] = []

はコンストラクターであるためEmptyNil、パターン マッチを行うことができ、コードを簡素化し、余分なEq制約を回避できます。

同じことが型レベルの等価物にも当てはまります: 型等価述語を単純EmptyNilにインスタンス ヘッドで使用するように置き換えます。

instance (HNoNils l l') => HNoNils (HCons EmptyNil l) l'

instance (HNoNils l l') => HNoNils (HCons e l) (HCons e l')

instance  HNoNils HNil HNil

このバージョンでも 1 つの状況で失敗しますが、これを回避する良い方法はありません。型リストに潜在的に統合できる型変数が含まれてEmptyNilいる場合 -- この時点では制約は無視され、GHC は後で追加される任意のインスタンスを考慮しなければならないことに注意してEmptyNilください -- 最初の 2 つのインスタンスは不可避的にあいまいです。

この最後の種類のあいまいさの問題は、関連するすべてのケースを確実に区別できるようにすることで、部分的に回避できます。たとえば、 のような型を削除するのではなく、EmptyNil代わりに次のような型コンストラクタを使用できます。

data Some a
data None

そして、型レベルのバージョンの を書きますcatMaybes:

class CatOptions l l'
instance (CatOptions l l') => CatOptions (HCons None l) l'
instance (CatOptions l l') => CatOptions (HCons (Some e) l) (HCons e l')
instance CatOptions HNil HNil

Numこれにより、あいまいさの問題は、リストに任意のインスタンスを表すポリモーフィック型などを含む場合ではなく、真にあいまいな状況のみに制限されます。

于 2012-12-26T14:44:23.567 に答える