Haskell：元组的递归定义

Question

在其中，我尝试创建Krivine抽象机。我需要构建的数据类型之一是环境。这样构建环境：

我们有x，一个“ Var”（这只是字符串的同义词）我们有N，一个“ Term”（这是一个Lambda项）

因此，环境E的定义为：

E =（x，N，E）·E.

因此，环境就是元组列表。每个元组包含一个Var（字符串），一个Term和一个环境列表（可能为空）。

我正在定义“ Env”，如下所示：

data Env = Env (Var, Term, [Env])

在我看来，这似乎应该起作用。但是，当我尝试使用Env时，我得到：

*Main> ("y", Lambda "z" (Variable "z"), []) :: Env

<interactive>:166:1: error:
* Couldn't match expected type `Env'
              with actual type `([Char], Term, [a0])'
* In the expression: ("y", Lambda "z" (Variable "z"), []) :: Env
  In an equation for `it':
      it = ("y", Lambda "z" (Variable "z"), []) :: Env

“ y”肯定是[Char]

Lambda“ z”（变量“ z”）绝对是Term类型的

空列表绝对是列表！

我觉得问题可能出在空列表上，但绝对不可缺少的是环境中可以存在一个空列表（这是基本情况）。

我现在一直在努力工作几个小时，一点也​​不运气。任何帮助是极大的赞赏。

Answer 1

data Env = Env (Var, Term, [Env])

在这里定义类型Env和数据构造函数Env。它们具有相同的名称，但是数据构造函数Env是具有以下类型的值：

ghci> :t Env
Env :: (Var, Term, [Env]) -> Env

构造函数定义从元组到Env值的映射。它也可以用于模式匹配，以将Env值映射到元组：

ghci> :t \(Env t) -> t
\(Env t) -> t :: Env -> (Var, Term, [Env])

诀窍在于，尽管类型的值Env与元组同构(Var, Term, [Env])，但它们具有不同的类型。Env。这是名词性类型，而不是结构性类型。当我们想要在内部具有相同结构但在类型系统中不同的值时，这非常有用

ghci> :t Env
Env :: (Var, Term, [Env]) -> Env

这使我们无法执行类似的操作fiveCentsPerHour + oneFifteenAM。

也就是说，有时您只是想为复杂类型使用一个更方便的名称，而又不想与复杂类型区分开。Haskell具有类型别名来处理这种情况。例如，String是[Char]（一个char列表）的类型别名；它们是相同类型的两个名称。

如果它不是递归的，并且您不想打扰构造函数，则可以通过使用type关键字使用类型别名：

type Env = (Var, Term, [SomethingElse])

但是您不能使用类型别名来定义递归类型，因为它们将在编译时无限扩展。

您可以采用的另一种方法是放弃元组并拥抱您的Env构造函数：

data Env = Env Var Term [Env]

现在，Env构造函数采用三个参数，而不是元组。

ghci> :t Env
Env :: Var -> Term -> [Env] -> Env

您还可以使用记录语法来获取各个字段的getter：

data Env = Env { var :: Var, term :: Term, env :: [Env] }

这些可能非常方便：

ghci> :t var
var :: Env -> Var
ghci> :t term
term :: Env -> Term
ghci> :t env
env :: Env -> [Env]