GHC重寫規則專用於類型類的函數

使用GHC RULES pragma，可以爲特定類型專門化多態函數。從哈斯克爾報告舉例：GHC重寫規則專用於類型類的函數

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

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

這將使GHC上一個整數索引表和仿製藥，否則其中intLookup很可能是更有效地利用intLookup。

我想完成類似的東西，使用如下（略微簡化的）那些功能：

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

其中lookupOrd創建從輸入列表中Map，然後使用Map.lookup，這要求a是Ord的成員。

現在我想告訴GHC，lookupOrd應該用來代替lookup，只要a確實是Ord類型類的成員。下面的規則，但是，不進行類型檢查：

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

GHC（理所當然）抱怨說，它不能從上下文推斷(Eq a)(Ord a)。是否有一個重寫規則可以讓我執行這種基於類的專業化？

來源

2013-11-02 Jannis Limperg

這幾乎是運行到舊的[開放世界的問題]（http://stackoverflow.com/a/1072523/745903）：你試圖根據是否在某種類型作出決定類型的類。 _但Haskell沒有** not **的概念在類型class_中！總是假設任何類型都可能在任何類中（即使沒有遇到過這樣的實例，有人可能會在後面添加它）。 – leftaroundabout

@leftaroundabout該問題不是太嚴重;可以想象應用這種規則的最佳方法（如果GHC首先支持它）。 –

我不覺得有什麼，還有一個原因是不容易實現與GHC的當前實現：

雖然你在Haskell語法中指定的規則，他們將被應用到GHC的核心語言。在那裏，類型類的約束已經變成字典參數，因此函數

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

現在鍵入

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

，而你的lookupOrd將有型

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

其中Eq a和Ord a有變成普通數據類型。特別是在這個階段，這個類型的類再也沒有概念了;所有已經解決的問題。

所以現在假設編譯器發現的

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字典）已固定在規則，並不需要一個規則，運用規則時被發現。

原則上，其他編譯器設計可能允許您想要的表單規則。

來源

2013-11-03 00:11:48

如果你編寫'{ - ＃RULES'lookup/Ord'forall（e :: Ord k => k）（l :: [（k，a）]），GHC 8.0.1不會抱怨。 lookup e l = lookupOrd e l＃ - }'，但該規則似乎並未實際觸發。 –

如果GHC在類型檢查後堅持其實例解析機制，那麼面對GADT時的這種和專業化可能會變得易於處理。 – dfeuer

儘管這是一個老問題，但未來的Google人可能會對使用ifcxt軟件包知道OP有用的方法感興趣。

您可以查看文檔以獲得更多示例，但基本上可以使用第二個示例示例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

，讓您選擇最有效的功能，這取決於類型類數據結構工具。

請注意，我不知道它會對性能產生多大影響，但我認爲它與查找函數的運行時相比並不重要，因此確實值得。

來源

2018-01-12 16:15:16 Tehnix

GHC重寫規則專用於類型類的函數

回答

相關問題