如何定义引用其定义的递归数据类型

Question

我想编写一种数据类型来评估像这样的表达式：

a 被评估为 a

a + b * c / d -e 被评估为 a + (b * (c / (d - e)))

因此，第一个参数始终是数字，第二个参数是数字或表达式

我试图定义这样的数据类型

 data Exp  = Single Int
          | Mult (Single Int) Exp

但这给了我这个编译错误：

    Not in scope: type constructor or class ‘Single’
    A data constructor of that name is in scope; did you mean DataKinds?
  |         
9 |           | Mult (Single Integer ) Exp 
  |            

我可以这样定义：

data Exp  = Single Integer
          | Mult Exp  Exp

但是它没有给出我想要的类型的精确定义。我该如何定义？

Answer 1

但它并没有给出我想要的 Type 的精确定义。

Single a不是一个类型。Single是一个数据构造函数。所以Single a没有多大意义。

您可以在此处使用Exp作为第一个参数，或者如果您想限制第一个操作数，您可以使用：

data Exp a = Single a | Mult a (Exp a)

事实上，由于Single a只包装了 an a，因此您可以使用 ana作为 的第一个参数Mult。数据Mult构造函数上下文清楚地表明了如何解释该数据a。

如果您想允许两个Exp as 相乘，那么您可以将其定义为：

data Exp a = Single a | Mult (Exp a) (Exp a)

当两个表达式可以相乘时，您可以使用通用抽象数据类型 (GADT)来制定更精细的规范。