CODEWITHSUNDEEP
haskellfunctional-programmingtreeabstract-syntax-treegadt
OctarineSorcerer
OctarineSorcerer

Reputation: 445

How to evaluate this generic abstract syntax tree in Haskell?

I've been interested in seeing if I can make a very simple AST that consists of operations and leaf nodes. But more specifically, I'd like to be able to use any type as the leaf node, as opposed to explicitly specifying it in the AST data type itself, like this.

-- Instead of this
data Tree = Number Int | Word String | Operation Tree (Tree -> Tree -> Tree) Tree

-- I'd like something along the lines of this
data Tree a = Leaf a | Operation Tree (Tree -> Tree -> Tree) Tree

This isn't necessarily of great practicality, but it's something that I want to see if it's possible. The closest I've managed thus far has required me to fumble about some with the concept of GADTs:

{-# LANGUAGE GADTs #-}

data Tree l where
  Leaf :: l -> Tree l
  Operation :: Tree a -> (a -> b -> c) -> Tree b -> Tree c

let fivePlus2 = Operation (Leaf 5) (+) (Leaf 2)

eval (Leaf l) = l
eval (Operation left op right) = op (eval left) (eval right)

With the idea that I could run eval fivePlus2, and get 7. However, the defining eval for Operation (that last line) results in the following very obscure error:

<interactive>:187:38: error:
    • Couldn't match type ‘a’ with ‘p’
      ‘a’ is a rigid type variable bound by
        a pattern with constructor:
          Operation :: forall a b c.
                       Tree a -> (a -> b -> c) -> Tree b -> Tree c,
        in an equation for ‘eval’
        at <interactive>:187:7-29
      ‘p’ is a rigid type variable bound by
        the inferred type of eval :: Tree p -> p
        at <interactive>:187:1-60
      Expected type: Tree a -> a
        Actual type: Tree p -> p
    • In the first argument of ‘op’, namely ‘(eval left)’
      In the expression: op (eval left) (eval right)
      In an equation for ‘eval’:
          eval (Operation left op right) = op (eval left) (eval right)
    • Relevant bindings include
        op :: a -> b -> p (bound at <interactive>:187:22)
        left :: Tree a (bound at <interactive>:187:17)
        eval :: Tree p -> p (bound at <interactive>:187:1)

<interactive>:187:50: error:
    • Couldn't match type ‘b’ with ‘p’
      ‘b’ is a rigid type variable bound by
        a pattern with constructor:
          Operation :: forall a b c.
                       Tree a -> (a -> b -> c) -> Tree b -> Tree c,
        in an equation for ‘eval’
        at <interactive>:187:7-29
      ‘p’ is a rigid type variable bound by
        the inferred type of eval :: Tree p -> p
        at <interactive>:187:1-60
      Expected type: Tree b -> b
        Actual type: Tree p -> p
    • In the second argument of ‘op’, namely ‘(eval right)’
      In the expression: op (eval left) (eval right)
      In an equation for ‘eval’:
          eval (Operation left op right) = op (eval left) (eval right)
    • Relevant bindings include
        right :: Tree b (bound at <interactive>:187:25)
        op :: a -> b -> p (bound at <interactive>:187:22)
        eval :: Tree p -> p (bound at <interactive>:187:1)

I'm honestly not sure at all what this means, and I'm rather out of my depth here, having initially tried this in F# and finding it wasn't expressive enough. I've not done functional programming in a while, and am very much a beginner in Haskell, so I'd greatly appreciate it if answers were explained like I was 5.

If it turns out evaluating such a tree isn't possible, that's fine, but I'd very much like to know what the logic behind it is. Thank you!

Upvotes: 4

Views: 447

Answers (1)

Li-yao Xia
Li-yao Xia

Reputation: 33419

Add a type signature to top-level functions:

eval :: Tree l -> l

This is generally considered good practice, but this is especially crucial with GADTs because that type is not inferred otherwise.

Upvotes: 12

Related Questions