Haskell : 元组的递归定义

Question

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

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

所以环境E的定义是：

E = (x, N, E) · E.

所以一个环境是一个元组列表。每个元组包含一个 Var (String)、一个 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。这是 nominitive 打字，而不是 structural 打字。当我们想要拥有在引擎盖下具有相同结构但在类型系统中不同的值时，它非常有用，例如

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]

Haskell : 元组的递归定义

Haskell : Recursive definition of a tuple

recursion

haskell

lambda-calculus