GHC重写规则专门用于类型类的函数

Question

使用GHC RULES编译指示,可以为特定类型专门化多态函数.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 lookupOrd应该使用而不是lookup什么时候a确实是Ord类型类的成员.但是,以下规则并未进行类型检查:

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

GHC(理所当然地)抱怨它不能(Ord a)从上下文中推断出来(Eq 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字典)已经在规则中修复,并且在应用规则时不需要找到.

原则上,其他编译器设计可能允许您需要的表单规则.

Answer 2

虽然这是一个老问题，但未来的 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

这将允许您根据数据结构实现的类型类选择最有效的函数。

请注意，我不知道它会对性能产生多大影响，但我认为它与查找函数的运行时相比微不足道，因此确实值得。