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。这是名义上的打字，而不是结构打字。当我们希望在引擎盖下具有相同结构的值时，它非常有用，但在类型系统中是不同的，例如，

data SecondsAfterMidnight = SecondsAfterMidnight Int
data PenniesPerHour = PenniesPerHour Int

这使我们无法做像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]