タイプクラスの関数を特化したGHC書き換えルール

Question

GHC RULES pragmaを使用すると、特定のタイプの多型関数を特殊化することができます。 Haskellのレポートからの例：

genericLookup :: Ord a => Table a b -> a -> b 
intLookup  ::   Table Int b -> Int -> b 

{-# RULES "genericLookup/Int" genericLookup = intLookup #-} 

これは、GHCはintLookupはおそらく、より効率的である整数インデックステーブルとジェネリックそうでない場合は、上のintLookupを使用するだろう。

Iは、以下の（わずかに単純化された）もののような関数を使用して、同様の何かを達成したい：aであることを必要とlookupOrdが入力リストからMapを作成し、Map.lookupを使用

lookup :: Eq a => [(a, b)] -> a -> b 
lookupOrd :: Ord a => [(a, b)] -> a -> b 

をOrdのメンバー。

今私はaが実際Ord型クラスのメンバーである時はいつでもlookupOrdがlookupの代わりに使用する必要があることをGHCに伝えたいと思います。次のルールは、しかし、です。TypeCheckしません：

{-# RULES "lookup/Ord" lookup = lookupOrd #-} 

GHC（当然）それは文脈(Eq a)から(Ord a)を推測することができないと文句を言い。このような種類のクラスベースの特殊化を実行するためのリライトルールはありますか？

Answer 1

私はそこにあるとは思わない、それは簡単にGHCの現在の実装では不可能である理由があります：

あなたはHaskellの構文でルールを指定しますが、彼らはGHCのコア言語に適用しようとしています。機能

lookup :: Eq a => a -> [(a,b)] -> Maybe b 

は、あなたのlookupOrdがタイプ

lookupOrd :: forall a b. Ord a -> a -> [(a, b)] -> Maybe b 

Eq aとOrd a持ってを持っているだろうが、今

lookup :: forall a b. Eq a -> a -> [(a, b)] -> Maybe b 

型を持つのであり、型クラス制約は、辞書の引数になってきました通常のデータタイプになります。特に、この段階では、型の型クラスの概念はなくなりました。以前に解決されたすべて。

だから今、コンパイラはそれがでそれを置き換えるべきこと

lookup (dict :: Eq MyType) (x :: MyType) (list :: [(MyType, String)]) 

の発生を見つけたと仮定？ xとlistもlookupOrdに渡すことができますが、この機能では、ルールの左側には表示されないタイプOrd MyTypeが必要です。だからGHCはあきらめなければならない。

{-# RULES "lookup/Ord" forall a x. lookup a x = lookupOrd (a::()) x #-} 

作品のようなルールは、しかし、としてここに問題のある引数（Ord辞書）は、すでにルールで固定されており、ルールを適用する際に発見される必要はありません。

原則として、他のコンパイラデザインでは、必要なフォームのルールを許可する場合があります。

Answer 2

これは古い質問ですが、将来のGoogleの方は、ifcxtパッケージを使用して、OPが望んでいることを実行する方法があることを知ることに興味があるかもしれません。

多くの例についてはドキュメントをチェックアウトできますが、基本的には2番目の例であるを使用します。例2：コードを漸近的に効率的にするを基準にします。二つの機能で

、

lookup :: Eq a => [(a, b)] -> a -> b 
lookupOrd :: Ord a => [(a, b)] -> a -> b 

あなたは、あなたがどのあなたのデータ構造を実装する型クラスに応じて、最も効果的な機能を選択できるようになります

cxtLookup :: forall a. (Eq a, IfCxt (Ord a)) => [(a, b)] -> a -> b 
cxtLookup = ifCxt (Proxy::Proxy (Ord a)) lookupOrd lookup 

になるだろう。

パフォーマンスにどれだけ影響を与えるのか分かりませんが、ルックアップ関数の実行時間に比べて些細なものだと想像しています。