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

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

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

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

当实例类型类为Symbolas时没有问题

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

如果您不想使用 newtype 包装器，则可以为此使用类型系列：

{-# 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