haskell - 函数依赖/类型族 - AST

Question

我最近接触到了函数依赖和类型族。对于一个类(class)项目，我用 Java 和 Haskell 编写(完成)了 C 子集的解释器。 Haskell 实现的术语求值函数需要通过显式模式匹配构建“函数表”并展开表示文字的值构造函数。一个不愉快的情况(但比 Java 漂亮得多)。

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

(使用函数依赖:注入(inject)和投影函数无需显式类型注释即可工作，就像使用 lit 注入(inject) 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. 通过使用类型系统证明您拥有的数据类型等于您想要的数据类型，在编译时投影值。

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