haskell - 如何使用类型同义词重载运算符？

Question

我想使用运算符构建一个规则，规则的定义如下:

type Rule a = [Symbol a]

符号的定义为:

data Symbol a = Empty | End | LangSym a

现在定义一个运算符 <.>可适用于以下四种情况:

(<.>)::Symbol a->Symbol a->Rule a
(<.>)::Rule a->Symbol a->Rule a
(<.>)::Symbol a->Rule a->Rule a
(<.>)::Rule a->Rule a->Rule a

显然，我们需要重载运算符 <.>使用类型类作为

class RuleOperator s1 s2 where
    (<.>)::s1 a->s2 a->Rule a

当实例化类型类为 Symbol 时没有问题如

instance RuleOperator Symbol Symbol where
    x <.> y = [x, y]

但是当实例有Rule a时，自 Rule a是类型同义词，我们不能这样做

instance RuleOperator Symbol Rule where
    ....

限制是我们不能更改 Rule a 的定义至

newtype Rule a = R [Symbol a]

由于其他模块依赖于 Rule a 的原始定义.

任何关于在不更改Rule的定义的情况下实现此类重载运算符的建议？

Answer 1

如果您不想使用新类型包装器，则可以使用类型系列:

{-# LANGUAGE TypeFamilies, FlexibleInstances, MultiParamTypeClasses #-}

type Rule a = [Symbol a]

data Symbol a = Empty | End | LangSym a

class RuleOperator t1 t2 where
   type Elem t1 t2
   (<.>) :: t1 -> t2 -> Rule (Elem t1 t2)

instance RuleOperator (Symbol a) (Symbol a) where
   type Elem (Symbol a) (Symbol a) = a
   s1 <.> s2 = [s1, s2]

instance RuleOperator (Symbol a) (Rule a) where
   type Elem (Symbol a) (Rule a) = a
   (<.>) = (:)

instance RuleOperator (Rule a) (Symbol a) where
   type Elem (Rule a) (Symbol a) = a
   r <.> s = r ++ [s]

instance RuleOperator (Rule a) (Rule a) where
   type Elem (Rule a) (Rule a) = a
   (<.>) = (++)

使类采用完全应用的类型，这样类型同义词就不再是问题，然后使用 Elem 类型族来恢复 a 参数。

<小时/>

这里有两种选择，允许从内向外和从外向内类型推理。一种使用类型族和约束:

{-# LANGUAGE TypeFamilies, FlexibleInstances, MultiParamTypeClasses #-}

type Rule a = [Symbol a]

data Symbol a = Empty | End | LangSym a

class (a ~ Elem t1 t2) => RuleOperator t1 t2 a where
   type Elem t1 t2
   (<.>) :: t1 -> t2 -> Rule (Elem t1 t2)

instance (a ~ b, a ~ c) => RuleOperator (Symbol a) (Symbol b) c where
   type Elem (Symbol a) (Symbol b) = a
   s1 <.> s2 = [s1, s2]

instance (a ~ b, a ~ c) => RuleOperator (Symbol a) (Rule b) c where
   type Elem (Symbol a) (Rule b) = a
   (<.>) = (:)

instance (a ~ b, a ~ c) => RuleOperator (Rule a) (Symbol b) c where
   type Elem (Rule a) (Symbol b) = a
   r <.> s = r ++ [s]

instance (a ~ b, a ~ c) => RuleOperator (Rule a) (Rule b) c where
   type Elem (Rule a) (Rule b) = a
   (<.>) = (++)

另一个使用函数依赖(其行为有点像带有约束的类型函数/族):

{-# LANGUAGE FunctionalDependencies, FlexibleInstances, MultiParamTypeClasses #-}

type Rule a = [Symbol a]
data Symbol a = Empty | End | LangSym a

class RuleOperator t1 t2 a | t1 -> a, t2 -> a where
  (<.>) :: t1 -> t2 -> Rule a
instance RuleOperator (Symbol a) (Symbol a) a where
   s1 <.> s2 = [s1, s2]
instance RuleOperator (Rule a) (Symbol a) a where
   r <.> s = r ++ [s]
instance RuleOperator (Symbol a) (Rule a) a where
  (<.>) = (:)
instance RuleOperator (Rule a) (Rule a) a where
  (<.>) = (++)

一些推理测试:

sym1, sym2 :: Symbol Int
sym1 = undefined
sym2 = undefined

rule :: Rule Int
rule = undefined

testInsideOut = sym1 <.> rule  -- type is inferred

polySym :: Show a => Symbol a
polySym = Empty

polyRule :: Show a => Rule a
polyRule = [Empty]

testOutSideIn :: Rule Int
testOutSideIn = polySym <.> polyRule  -- Show instances are resolved to Int