Haskell递归类型

Question

我试图在Haskell中创建一个函数,Resp在BNF和Haskell类型之间的奇怪混合中返回下面说明的类型.

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

我的问题是(a)如何在Haskell中定义这种类型,以及(b)如果有一种方法这样做而不必强制使用自定义构造函数,例如Node,而是仅使用元组和数组.

Answer 1

你说"各种关键词(数据,类型,新类型)让我感到困惑".这是Haskell中数据构造关键字的快速入门.

数据

创建新类型的规范方法是使用data关键字.Haskell中的一般类型是产品类型的联合,每个产品类型都用构造函数标记.例如,Employee可能是行工作者(具有名称和工资)或经理(具有名称,工资和报告列表).

我们使用String类型来表示员工的姓名,以及Int表示salaray 的类型.报告列表只是一个列表Employee.

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

类型

该type关键字用于创建类型同义词,即相同类型的备用名称.这通常用于使源更容易理解.例如,我们可以Name为员工姓名(实际上只是一个String)和Salary工资(只是Ints)以及Reports报告列表声明一个类型.

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

data Employee = Worker  Name Salary
              | Manager Name Salary Reports

NEWTYPE

该newtype关键字与关键字类似type,但它增加了额外的类型安全性.随着代码的前一个块的一个问题是,虽然工人的组合Name和Salary,没有什么可以阻止你使用任何旧String的Name字段(例如,地址).编译器不区分Names和普通旧Strings,这引入了一类潜在的bug.

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

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)

这有什么好处是因为编译器知道a Name实际上只是a String,它会优化掉额外的构造函数,所以这和使用type声明一样有效- 额外的类型安全性"免费".这需要一个重要的限制 - 一个newtype只有一个构造函数只有一个值.否则编译器将不知道哪个构造函数或值是正确的同义词!

使用newtype声明的一个缺点是现在a 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

但事实上,如果你在声明你的newtypes 时使用记录语法,Haskell会为你写这些

data Salary = Salary { getSalary :: Int }

现在你可以写了

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

Answer 2

第1部分:

data Elem = El String | Node String String Resp
type Resp = [Elem]

第2部分:嗯......有点儿.不满意的答案是:你不应该这样做,因为这样做不太安全.更直接的答案是Elem需要它自己的构造函数,但Resp很容易定义为上面的类型同义词.但是,我会建议

newtype Resp = Resp { getElems :: [Elem] }

所以你不能混淆一些随机的Elems 列表Resp.这也为您提供了功能,getElems因此您无需在单个构造函数上进行尽可能多的模式匹配.在newtype基本上让哈斯克尔知道它应该在运行时摆脱构造的开销,所以没有额外的间接这是很好的.