2

I was recently introduced to functional dependencies and type families. For a class project I wrote (completed) an interpreter for a subset of C in Java and Haskell. The Haskell implementation of an evaluation function for terms required building "function tables" with explicit pattern matching and unwrapping of value constructors representing literals. An unhappy situation (but much prettier than the Java).

After searching for a while, I came across the "collections" example, wondering if I could apply this to my abstract syntax to produce generic "inject to" and "project from" functions for literals. I came up with two initial test attempts:

(Using functional dependencies: the injection and projection functions work without explicit type annotations, as does injection into Lit with lit. However, the projection function from Lit will not type, giving the error "couldn't match expected type l against inferred type 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

(Using type families. The problem here is that I can't get Haskell to infer from an argument the correct return type without explicit annotation, and I can't write the generic functions lit :: Val l -> E and 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

I don't understanding type families well, and have a flimsy grasp on functional dependencies. But I'd like to know two things: (a) if the functions I want can be typed and implemented; (b) If I am misunderstanding something fundamental here. It almost works, but I've been fighting with the type checker for a while now.

EDIT This is a simple model of what I want, since it was unclear. The class Bin implements the functionality I want, basically. But I can't collect the various "wrappable and unwrappable" values together to make an AST out of this.

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)
4

2 回答 2

4

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

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

Lit :: Prim l => l -> E

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

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

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

有理由使用编译时证明，但看起来你没有任何这些理由。

于 2010-12-10T04:49:47.520 回答
1

如果您仍然想坚持多态的想法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。Val l但是除了使用一些Data.Dynamic（如果这是我的想法）之外，您没有其他方法可以使用。

于 2011-02-08T08:00:19.450 回答