CODEWITHSUNDEEP
haskell
luochen1990
luochen1990

Reputation: 3847

Is there a better way to add attribute field into AST in Haskell?

At first, I have a original AST definition like this:

data Expr = LitI Int | LitB Bool | Add Expr Expr

And I want to generalize it so that each AST node can contains some extra attributes:

data Expr a = LitI Int a | LitB Bool a | Add (Expr a) (Expr a) a

In this way, we can easily attach attribute into each node of the AST:

type ExprWithType = Expr TypeRep
type ExprWithSize = Expr Int

But this solution makes it hard to visit the attribute field, we must use pattern matching and process it case by case:

attribute :: Expr a -> a
attribute e = case e of
    LitI _ a -> a
    LitB _ a -> a
    Add _ _ a -> a

We can image that if we can define our AST via a product type of the original AST and the type variable indicating attribute:

type ExprWithType = (Expr, TypeRep)
type ExprWithSize = (Expr, Int)

Then we can simplify the attribute visiting function like this:

attribute = snd

But we know that, the attribute from the outmost product type will not recursively appears in the subtrees.

So, is there a better solution for this problem?

Generally speaking, When we want to extract common field of different cases of a recursive sum type, we met this problem.

Upvotes: 3

Views: 254

Answers (2)

soupi
soupi

Reputation: 1013

You might want to take a look at Cofree where f will be your recursive data type after abstracting the concept of recursion as an f-algebra and a will be the type of your annotation.

Nate Faubion gave a very accesible talk about this and similar approaches and you can watch it here: https://www.youtube.com/watch?v=eKkxmVFcd74

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476739

You could "lift" the type of the Expr for example like:

data Expr e = LitI Int | LitB Bool | Add e e

Now we can define a data type like:

data ExprAttr a = ExprAttr {
    expression :: Expr (ExprAttr a),
    attribute :: a
  }

So here the ExprAttr has two parameters, the expression, which is thus an Expression that has ExprAttr as in the tree, and attribute which is an a.

You can thus process ExprAttrs, which is an AST of ExprAttrs. If you want to use a "simple" AST, you can define a type like:

newtype SimExpr = SimExpr (Expr SimExpr)

Upvotes: 3

Related Questions