Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rewriting trees

I have a data structure that represents a type signature, this data structure is a tree exemplified in the first picture as the red one. I would like to get the black one and so far I've only got the orange one (second picture), which is the type tree but associated to the left.

enter image description here

Here's the orange tree I've got so far (follow the orange arrows)

enter image description here

I had solved this problem by pretty printing the tree and then parsing it with a parser combinator, but this inefficiency is not desired. I think I can have another algorithm to convert from the orange tree to the black one, but it would be better if instead of composing two algorithms, I could write only one.

I will tag this as Haskell as I am writing my solution on it. I could provide code to get a data structure like the red tree but I think it would only complicate the attempt at the solution..

I would like to know if there is a name for this algorithm and/or what the name of the operator position in the red tree is. Is it prefix?

Thanks.

like image 726
Carlos López-Camey Avatar asked Oct 04 '22 05:10

Carlos López-Camey


1 Answers

Have a look into recursion schemes. There's a related question here that includes loads of links:

Recursion schemes for dummies?

All of the links on that question are excellent, but I'd particularly look at Tim Williams' slides (link in my answer to that question) for concrete implementations of the various different recursion patterns (most of which are demo'd on tree structures).

like image 96
Ben Ford Avatar answered Oct 11 '22 08:10

Ben Ford