CODEWITHSUNDEEP
haskellabstract-syntax-tree
Konstantin Solomatov
Konstantin Solomatov

Reputation: 10352

Syntax tree with parent in Haskell

I want to implement an AST in Haskell. I need a parent reference so it seems impossible to use a functional data structure. I've seen the following in an article. We define a node as:

type Tree = Node -> Node

Node allows us to get attribute by key of type Key a. Is there anything to read about such a pattern? Could you give me some further links?

Upvotes: 1

Views: 725

Answers (1)

C. A. McCann
C. A. McCann

Reputation: 77424

If you want a pure data structure with cyclic self-references, then as delnan says in the comments the usual term for that is "tying the knot". Searching for that term should give you more information.

Do note that data structures built by tying the knot are difficult (or impossible) to "update" in the usual manner--with a non-cyclic structure you can keep pieces of the original when building a new structure based on it, but changing any piece of a cycle requires you to rebuild the entire cycle as well. Depending on what you're doing, this may or may not be a problem, of course.

Upvotes: 2

Related Questions