Haskell 递归类型

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

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

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

最佳答案

第1部分:

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

第 2 部分:嗯……有点。不满意的答案是:您不应该想要，因为这样做的类型安全性较低。更直接的答案是 Elem 需要它自己的构造函数，但 Resp 很容易定义为上述类型的同义词。不过，我会推荐

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

这样您就不能将 Elem 的一些随机列表与 Resp 混淆。这也为您提供了 getElems 函数，因此您不必在单个构造函数上进行尽可能多的模式匹配。 newtype基本上让Haskell知道它应该在运行时消除构造函数的开销，因此没有多余的间接方法，这很好。

关于Haskell 递归类型，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17647414/