函数依赖/类型族 - AST

Question

最近向我介绍了函数依赖性和类型族。在一个班级项目中，我用 Java 和 Haskell 编写（完成）了 C 子集的解释器。 Haskell 实现的术语求值函数需要通过显式模式匹配构建“函数表”并展开表示文字的值构造函数。一个不愉快的情况（但比 Java 漂亮得多）。

经过一段时间的搜索后，我遇到了“集合”示例，想知道是否可以将其应用于我的抽象语法来为文字生成通用的“注入”和“项目”函数。我提出了两个初步测试尝试：（

使用函数依赖关系：注入和投影函数无需显式类型注释即可工作，就像使用 lit 注入 Lit 一样。但是， Lit 中的投影函数不会键入，给出错误“无法将预期类型 l 与推断类型 l' 匹配”。）

class Prim l a | l -> a, a -> l where
 inj  :: a -> l
 proj :: l -> a

instance Prim LB Bool where inj = LB; proj = lb
instance Prim LI Int  where inj = LI; proj = li

data LB = LB {lb :: Bool}
data LI = LI {li :: Int}

data E where Lit :: Prim l a => l -> E

lit :: Prim l a => l -> E
lit = Lit

unlit :: Prim l a => E -> l
unlit (Lit a) = a

（使用这里的问题是我无法让 Haskell 在没有显式注释的情况下从参数推断出正确的返回类型，并且我无法编写泛型函数 lit :: Val l -> E 和 unlit :: E -> Val l。）

class Show l => Prim l where
 type Val l :: *
 inj  :: Val l -> l
 proj :: l -> Val l

data LB a = LB {lb :: Bool}
data LI a = LI {li :: Int }

instance Prim (LB a) where type Val (LB a) = Bool; inj = LB; proj = lb
instance Prim (LI a) where type Val (LI a) = Int;  inj = LI; proj = li;

data E where
 Lit :: Prim l => l -> E
 Bin :: Op -> E -> E -> E

我不太了解类型族，并且对函数依赖关系的掌握很薄弱。但我想知道两件事：（a）我想要的功能是否可以键入并实现； (b) 如果我误解了一些基本的东西。它几乎可以工作，但我已经与类型检查器斗争了一段时间了。

编辑这是我想要的一个简单模型，因为它还不清楚。 Bin 类基本上实现了我想要的功能。但我无法将各种“可包装和不可包装”值收集在一起来制作 AST。

class L t l => Bin t l where
 bAp :: (t -> t -> t) -> l -> l -> l
 bAp f l r = inj (proj l `f` proj r)

class Show l => L t l | t -> l, l -> t where
  inj  :: t -> l
  proj :: l -> t
  typ  :: l -> T

instance Bin Int LI
instance Bin Bool LB

instance L Int  LI where inj = LI; proj = li; typ = const TI
instance L Bool LB where inj = LB; proj = lb; typ = const TB

data LI = LI {li :: Int}  deriving (Eq, Show)
data LB = LB {lb :: Bool} deriving (Eq, Show)

data T = TI | TB | TC | TF | TU deriving (Eq, Show)

Answer 1

无论您如何定义投影函数，定义 Lit 构造函数的方式都会阻止您投影出它包含的值。

让我们看看构造函数的类型：

Lit :: Prim l => l -> E

类型变量l出现在参数中，但没有返回类型。这意味着当您构造 Lit 时，您放入了一个属于 Prim 成员的某种类型的值，然后永远忘记了它的类型是什么。

我不确定您想如何消除模式匹配和值构造函数的展开。对于如何进行投影，您基本上有两种选择：

1. 在运行时投影值、使用模式匹配或等效的东西。
2. 通过使用类型系统证明您拥有的数据类型等于您想要的数据类型，在编译时投影值。

有理由进行编译时证明，但看起来您没有任何这些理由。

Answer 2

如果您仍然想坚持多态 E 的想法。您可以使用多态函数：

withUnlit :: E -> (forall l . Prim l => l -> b) -> b
withUnlit (Lit a) f = f a

但您唯一可以做的事情（使用您赋予 Prim l 的特征）是：

showE :: E -> String
showE e = withUnlit e show

以及 inj 和 proj。但是，除了使用一些 Data.Dynamic （如果我是这么认为的话），您无法使用 Val l 。