GHC重写规则专门为一个类型类的函数 [英] GHC rewrite rule specialising a function for a type class

问题描述

使用GHC RULES pragma ，可以针对特定类型专门开发一个多态函数。来自Haskell报告的例子：

  genericLookup :: Ord a =>表a b  - > a  - > b 
 intLookup :: Table Int b  - > Int  - > b 
 $ b { - ＃RULESgenericLookup / IntgenericLookup = 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 c $ c> Ord 类型类。但是，以下规则不会检查：

  { - ＃RULESlookup / Ordlookup = lookupOrd＃ - } 
  

GHC（正确地）抱怨它不能推断出（Ord a）来自上下文（方程a）。是否有一个重写规则，允许我执行这种类型的基于类的专业化？ 我不认为有一个原因，为什么GHC当前的实现不容易实现：

虽然您在Haskell语法中指定了规则，但它们将被应用于GHC的核心语言。在那里，类型约束已经变成了字典参数，所以函数

  lookup :: Eq a => a  - > [（a，b）]  - >也许b 
  

现在已经输入

  lookup :: forall a b。公式a  - > a  - > [（a，b）]  - >也许b 
  

，而您的 lookupOrd

  lookupOrd :: forall a b。 Ord a  - > a  - > [（a，b）]  - >也许b 
  

其中等式a 和 Ord a 已成为普通数据类型。具体来说，在这个阶段，对于一个类型来说，没有 类型类的概念;所有已经解决的问题。

所以现在假设编译器发现一个

  lookup（dict :: Eq MyType）（x :: MyType）（list :: [（MyType，String）]）
  

应该用什么来代替它？您告诉他可以将 x 和 list 传递给 lookupOrd ，但该函数也希望类型 Ord MyType 的值不出现在规则的左侧。所以GHC不得不放弃。

一条规则就像

  { - ＃RULESlookup / Ordforall a x。尽管如此，lookup ax = lookupOrd（a：:(））x＃ - } 
  

有问题的参数（ Ord 字典）已经在规则中修复，并且在应用规则时不需要找到。

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

Using the GHC RULES pragma, it is possible to specialise a polymorphic function for specific types. Example from the Haskell report:

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

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

This would make GHC use intLookup on an integer-indexed table and the generic version otherwise, where intLookup would probably be more efficient.

I would like to accomplish something similar, using functions like the following (slightly simplified) ones:

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

where lookupOrd creates a Map from the input list and then uses Map.lookup, which requires that a be a member of Ord.

Now I would like to tell GHC that lookupOrd should be used instead of lookup whenever a is indeed a member of the Ord type class. The following rule, however, does not typecheck:

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

GHC (rightfully) complains that it cannot deduce (Ord a) from the context (Eq a). Is there a rewrite rule that would allow me to perform this sort of type class-based specialisation?

解决方案

I don’t think there is, and there is a reason why it is not easily possible with GHC’s current implementation:

Although you specify rules in Haskell syntax, they are going to be applied to GHC’s Core language. There, type class constraints have been turned into dictionary arguments, so the function

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

has now type

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

while your lookupOrd would have type

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

where Eq a and Ord a have become ordinary data types. In particular, at this stage, there is no notion of the type class for a type any more; all that has been resolved earlier.

So now assume the compiler finds an occurrence of

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

What should it replace it with? You told him that x and list can be passed to lookupOrd as well, but that function also wants a value of type Ord MyType, which does not occur on the left-hand side of the rule. So GHC has to give up.

A rule like

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

works, though, as here the problematic argument (the Ord dictionary) is already fixed in the rule, and does not need to be found when applying the rule.

In principal, other compiler designs might allow rules of the form that you want.

这篇关于GHC重写规则专门为一个类型类的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！