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?

Argentum

But it does not give the precise definition of the Type I want. What is the type you want then? Your first version fails because Single a is a value, not a type. The second one looks correct to me, if it differs from what you need then please explain what the difference is. (Well if you want it polymorphic it should be data Exp a = Single a | Mult (Exp a) (Exp a)) – Ablaut

Single a is not a type. You can either define it as a Mult a Exp, or Mult Expr Expr. – Intercommunicate

@WillemVanOnsem in this case Mult a Expr is closest to what I want. I was thinking, How can I tell compiler that the first argument should be a specific definition, instead of Mult Exp Exp – Argentum

What's wrong with data Exp = Single Int | Mult Int Exp? – Hetrick

@DanielWagner Nothing, except we do not have Mult Int Exp in the language, I'm trying to evaluate. It has 'Mult Single Int Exp' . The next best option is Mult Exp Exp , but it allows Mult Exp (Single Int) which is illegal. – Argentum

@Argentum What is the difference between what you want Mult (Single Int) Exp to mean and what Mult Int Exp actually means? – Hetrick

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.

Intercommunicate

You are write, but I want somthing like this: data exp a = Red a | Blue a | Op (Red a) Exp, How can define it? – Argentum

@Ali: You can not do that, or at least not directly, you can however define some extra types, and use GADTs to enforce constraints. For example newtype Red = Red, newtype Blue = Blue, newtype Op = Op and then data Expr a b where; Red :: a -> Expr a Red; Blue :: a -> Expr a Blue; Op :: Expr a Red -> Expr a c -> Expr a Op for example. – Intercommunicate