Haskell:递归数据类型(参数化类型)

Question

我有这个：

data Val s i a = S s | I i | A a deriving (Show)

在 Haskell 中使用非同质列表。所以我可以做类似的事情(只是一个示例函数(：

oneDown :: Val String Int [String]-> Either String String

但我实际上希望这是一个瓦尔斯列表，即：

oneDown :: Val String Int [Val]-> Either String String

Answer 1

你正在寻找的东西会导致无限的数据类型，Haskell明确不允许。但是，我们可以将这种无限性隐藏在 newtype 后面，编译器不会抱怨。

data Val s i a = S s | I i | A a deriving (Show)
newtype Val' = Val' (Val String Int [Val']) deriving (Show)

它仍然完全按照您的示例所做的操作(加上一些将在运行时进行优化的类型构造函数(，但现在我们可以无限递归，因为我们已经保护了递归类型。

这实际上是递归方案库所做的，以获取归纳定义的数据，我们可以定义通用递归技术。如果您对这样的通用数据类型感兴趣，可以查看该库。

要构造这个新制作的类型，我们必须使用Val'构造函数。

let myVal = A [Val' (I 3), Val' (S "ABC"), Val' (A [])]