Haskell 递归类型

Question

我试图在 Haskell 中创建一个函数，返回 Resp下面以 BNF 和 Haskell 类型之间的奇怪组合说明了类型。

elem ::= String | (String, String, Resp)
Resp ::= [elem]

我的问题是(a)如何在 Haskell 中定义这种类型，以及(b)是否有一种方法可以在不强制使用自定义构造函数的情况下这样做，例如，Node ，而只使用元组和数组。

Answer 1

你说“各种各样的关键字(数据、类型、新类型)让我感到困惑”。这是 Haskell 中数据构造关键字的快速入门。

数据

创建新类型的规范方法是使用 data关键词。 Haskell 中的一般类型是产品类型的联合，每个产品类型都用构造函数标记。例如，一个 Employee可能是一线 worker (有姓名和薪水)或经理(有姓名、薪水和报告 list )。

我们使用 String表示员工姓名的类型，以及 Int类型来表示一个薪水。报告列表只是 Employee 的列表s。

data Employee = Worker  String Int
              | Manager String Int [Employee]

类型
type关键字用于创建类型同义词，即相同类型的替代名称。这通常用于使来源更易于理解。例如，我们可以声明一个类型 Name对于员工姓名(实际上只是一个 String )和 Salary工资(只有 Int s)和 Reports获取报告列表。

type Name    = String
type Salary  = Int
type Reports = [Employee]

data Employee = Worker  Name Salary
              | Manager Name Salary Reports

新型
newtype关键字类似于 type关键字，但它增加了额外的类型安全性。前一段代码的一个问题是，尽管一个 worker 是 Name 的组合。和一个 Salary ，没有什么可以阻止您使用任何旧的 String在 Name字段(例如，地址)。编译器不区分 Name s 和普通的旧 String s，它引入了一类潜在的错误。

与 newtype关键字我们可以让编译器强制执行唯一的 String可以在 Name 中使用的 s字段是明确标记为 Name 的字段秒

newtype Name    = Name String
newtype Salary  = Salary Int
newtype Reports = Reports [Employee]

data Employee = Worker  Name Salary
              | Manager Name Salary Reports

现在，如果我们尝试输入 String在 Name字段没有明确标记它，我们得到一个类型错误

>>> let kate = Worker (Name "Kate") (Salary 50000)     -- this is ok
>>> let fred = Worker "18 Tennyson Av." (Salary 40000) -- this will fail

<interactive>:10:19:
    Couldn't match expected type `Name' with actual type `[Char]'
    In the first argument of `Worker', namely `"18 Tennyson Av."'
    In the expression: Worker "18 Tennyson Av." (Salary 40000)
    In an equation for `fred':
        fred = Worker "18 Tennyson Av." (Salary 40000)

这样做的好处在于，因为编译器知道 Name真的只是一个String ，它优化掉了额外的构造函数，所以这和使用 type 一样有效。声明——额外的类型安全是“免费的”。这需要一个重要的限制—— newtype正好有一个构造函数，只有一个值 .否则编译器将不知道哪个构造函数或值是正确的同义词!

使用 newtype 的一个缺点声明是现在一个 Salary不再只是 Int ，你不能直接把它们加在一起。例如

>>> let kate'sSalary = Salary 50000
>>> let fred'sSalary = Salary 40000
>>> kate'sSalary + fred'sSalary

<interactive>:14:14:
    No instance for (Num Salary)
      arising from a use of `+'
    Possible fix: add an instance declaration for (Num Salary)
    In the expression: kate'sSalary + fred'sSalary
    In an equation for `it': it = kate'sSalary + fred'sSalary

有点复杂的错误消息告诉您 Salary不是数字类型，因此您不能将它们加在一起(或者至少，您没有告诉编译器如何将它们加在一起)。一种选择是定义一个函数来获取底层 Int来自 Salary

getSalary :: Salary -> Int
getSalary (Salary sal) = sal

但事实上，如果你在声明 newtype 时使用记录语法，Haskell 会为你写这些。秒

data Salary = Salary { getSalary :: Int }

现在你可以写

>>> getSalary kate'sSalary + getSalary fred'sSalary
90000