Haskell AST与递归类型

我目前正在尝试构建一个lambda微积分求解器，并且在构建AST时遇到了一些小问题。甲演算术语感应定义为：Haskell AST与递归类型

1）一种可变

2）的λ，变量，一个点，一个lambda表达式。

3）括号，lambda表达式，lambda表达式和括号。

我想怎么做（在第一次尝试）是这样的：

data Expr = 
    Variable 
    | Abstract Variable Expr 
    | Application Expr Expr

现在很明显这是行不通的，因为变量是不是一个类型的，和抽象变Expr的期望类型。所以，我的哈克解决方案，这是有：

type Variable = String 

data Expr = 
    Atomic Variable 
    | Abstract Variable Expr 
    | Application Expr Expr

现在，这实在是烦人，因为我不喜欢自己的原子变量，但摘要采取字符串，而不是EXPR。有什么办法可以让这个更优雅，并且像第一个解决方案那样做？

来源

2016-11-13 user2850249

您发现令人厌恶的第二个定义是执行此操作的标准方法。我的建议是，习惯它。你的思维方式与Haskell的类型系统不兼容，所以请继续并训练自己。 – luqui

你的第一个解决方案只是一个没有意义的错误定义。 Variable不是那里的一个类型，它是一个空值构造函数。您不能在类型定义中引用Variable，就像您不能引用任何值一样，如True,False或100。

第二种解决方案是实际上的东西，我们可以在BNF编写直接翻译：

var ::= <string> 
term ::= λ <var>. <term> | <term> <term> | <var>

因而存在不妥的地方。

来源

2016-11-13 10:12:47

你到底想要的是有某种类型的像

data Expr 
    = Atomic Variable 
    | Abstract Expr Expr 
    | Application Expr Expr

但是限制第一Expr在Abstract构造是唯一Atomic。在Haskell中没有直接的方法可以做到这一点，因为某些类型的值可以由任何这种类型的构造函数创建。因此，唯一的方法是为现有类型创建一些单独的数据类型或类型别名（例如Variable类型别名）并将所有通用逻辑移入其中。你的解决方案与Variable似乎对我很好。

但是。您可以使用Haskell中的其他一些高级功能以不同的方式实现您的目标。您可以从glambda包中获得灵感，它使用GADT来创建类型化的lambda演算。也看到这个答案：https://stackoverflow.com/a/39931015/2900502

我能拿出一个解决方案，以实现您的最小目标（如果你只是想约束的Abstract第一个参数）：

{-# LANGUAGE GADTs   #-} 
{-# LANGUAGE KindSignatures #-} 

data AtomicT 
data AbstractT 
data ApplicationT 

data Expr :: * -> * where 
    Atomic  :: String -> Expr AtomicT 
    Abstract :: Expr AtomicT -> Expr a -> Expr AbstractT 
    Application :: Expr a -> Expr b -> Expr ApplicationT

而下面的例子正常工作：

ex1 :: Expr AbstractT 
ex1 = Abstract (Atomic "x") (Atomic "x")

但由于类型不匹配的这个例子不会编译：

ex2 :: Expr AbstractT 
ex2 = Abstract ex1 ex1

来源

2016-11-13 10:28:35 Shersh

不够公平，如果我做一个函数来检查（Abstract Expr Expr）的每个实例只有一个原子值作为第一个Expr，expr解决方案可能就足够了。想想我会在我的问题中采用第二种解决方案，因为它似乎是最受欢迎的。 – user2850249

@ user2850249你可能没有看到我的下半部分答案。如果您使用'GADT'，则不需要创建函数来检查每个“Abstract Expr Expr”是否具有原子值作为第一个'Expr'。如果你使用非原子作为第一个'Expr'，你的代码就不会编译。并且在运行时保证你的第一个'Expr'永远是'Atomic'。 – Shersh

Haskell AST与递归类型

回答

相关问题