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

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

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

Answer 1

But it does not give the precise definition of the Type I want.

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

你可以在这里使用Exp作为第一个参数，或者如果你想限制第一个操作数，你可以使用：

data Exp a = Single a | Mult <b>a</b> (Exp a)

确实，由于 Single a 只是包裹了一个 a，您可以使用 a 作为 Mult 的第一个参数。 Mult 数据构造函数上下文，明确了如何解释 a.

如果你想允许两个Exp a相乘，那么你可以定义为：

data Exp a = Single a | Mult <b>(Exp a)</b> (Exp a)

当两个表达式可以相乘时，您可以使用 generic abstract data types (GADTs) 来制定更精细的规范。

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

How to define a recursive data type that refers to its definition

haskell

recursive-datastructures