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

Question

I want to write a data type to evaluate the expressions like this:

a is evaluated to a

a + b * c / d -e is evaluated to a + (b * (c / (d - e)))

So the first argument is always a number and the second one is either a number or an expression

I have tried to define a data type like this

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

But it gives me this compilation error:

    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 
  |            

I can define it like this:

data Exp  = Single Integer
          | Mult Exp  Exp

But it does not give the precise definition of the Type I want. How can I define this?

Answer 1

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

Single a is not a type. Single is a data constructor. So Single a does not make much sense.

You can use Exp here as first parameter, or if you want to restrict the first operand, you can use:

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

Indeed, since Single a just wraps an a, you can use an a as first parameter of Mult. The Mult data constructor context, makes it clear how to interpret that a.

If you want to allow multiplying two Exp as, then you can define this as:

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

You can use generic abstract data types (GADTs) to make finer specifications when two expressions can be multiplied.