Abstract syntax tree implementation on functions

Question

I'm trying to draw an abstract tree for the following Haskell function:

f t = t + t
twice f t = f(f(t))
twice f 1

The examples I've found online (e.g. below image) are quite simple to understand, but I think I'm getting lost when it comes to the names of functions.

The tree I currently have is:

But it just seems a bit incomplete or that I'm missing something?

If anyone could help/point me in the right direction or share any good resources I'd be grateful. Thanks in advance.

You want an AST of what exactly? There is no such thing as an AST of a function. A function is a Haskell value (a run-time entity). Syntax entities are e.g. declarations and expressions. This fragment has two declarations and one expression. — n. 1.8e9-where's-my-share m.
I want to represent "twice f 1" in an AST, I obviously didn't word the question correctly but I'm not sure how to do that either. Thanks for the comment. — Lucy S.
A syntactic analysis of twice f 1 does not include the definition of f. It doesn't even matter whether any of the constituents have definitions; the tree for dingo koala wombat has the same structure. — molbdnilo

chepner chepner · Accepted Answer · 2020-11-12T13:43:01

The expression twice f 1 is parsed as a pair of applications: first twice is applied to f, then that result is applied to 1.

There is no token in the expression that corresponds to application, as application is just represented by juxtaposition (two tokens next to each other). That doesn't mean, though, that there is no node in the tree to represent application. So, we start with a root node that represents the act of applying:

                  apply

This node has two children; the thing being applied, which is another application, and the thing being applied to.

                  apply
                /       \
               /         \
            apply       value
           /     \        |
          /       \       number "1"
         /         \
      value       value
        |           |
     identifier    identifier
      "twice"         "f"

The structure of the tree encodes the precedence of function application. If your expression were twice (f 1), there would be no parentheses explicitly stored in the tree; rather, the structure of the tree itself would change.

                  apply
                /       \
               /         \
            value      apply
              |       /     \
       identifier    /       \
        "twice"     /         \
                 value       value
                   |           |
               identifier    number "1"
                  "f"

Abstract syntax tree implementation on functions

1 Answers