Rewriting trees

Question

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.

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

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.

Answer 1

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).