haskell - 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 可能会更有效。

我想使用以下函数(稍微简化)来完成类似的事情:

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

其中 lookupOrd 从输入列表创建一个 Map，然后使用 Map.lookup，这需要 a > 成为 Ord 的成员。

现在我想告诉 GHC，只要 a 确实是 的成员，就应该使用 lookupOrd 而不是 lookup Ord 类型类。但是，以下规则不会进行类型检查:

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

GHC(正确地)提示它无法从上下文 (Eq a) 中推导出 (Ord a)。是否有重写规则允许我执行这种基于类型的特化？

Answer 1

我认为不存在，并且在 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 字典)已经在规则中修复，并且在应用规则时不需要找到。

原则上，其他编译器设计可能允许您想要的形式的规则。