15

使用 GHC RULESpragma，可以为特定类型专门化多态函数。Haskell 报告中的示例：

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

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

这将使 GHCintLookup在整数索引表和通用版本上使用，否则intLookup可能会更有效。

我想完成类似的事情，使用类似以下（稍微简化）的功能：

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

where从输入列表中lookupOrd创建 aMap然后使用Map.lookup，这要求它a是 的成员Ord。

现在我想告诉 GHClookupOrd应该使用lookup什么时候代替a确实是Ord类型类的成员。但是，以下规则不进行类型检查：

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

GHC（理所当然地）抱怨它无法(Ord a)从上下文中推断出来(Eq a)。是否有重写规则允许我执行这种基于类型的专业化？

4

2 回答 2

14

我认为没有，并且有一个原因是 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

whereEq a和Ord a都变成了普通的数据类型。特别是，在这个阶段，类型不再有类型类的概念。所有的事情都早先解决了。

所以现在假设编译器发现了

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

它应该用什么代替它？你告诉他xandlist也可以传递给lookupOrd，但是该函数还需要一个 type 的值Ord MyType，它不会出现在规则的左侧。所以GHC不得不放弃。

像这样的规则

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

但是有效，因为这里有问题的参数（Ord字典）已经在规则中固定，并且在应用规则时不需要找到。

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

于 2013-11-03T00:11:48.250 回答
6

虽然这是一个老问题，但未来的谷歌人可能有兴趣知道有一种方法可以使用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-12T16:15:16.183 回答