I was doing question I 238, when I thought it would be nice to parse these formulas into trees. I couldn’t really figure out how to parse with StateT String m a, so I decided to do things intuitively.
I convert a string containing parentheses into a list of actions (Direction String).
data Direction a = NewBranch | NewLeaf a | Up deriving Show
"((abc)(a))" would be made into [NewBranch, NewBranch, NewLeaf "abc", Up, NewBranch, NewLeaf "a", Up, Up] by the function stringToPath.
Once this is done I use the zipper not only to traverse the Tree, but to create it. Basically the zipper is the same type as the original (tip labeled) tree. But this comes with a problem: [NewBranch] ~ [NewBranch, Up] ~ [NewBranch, Up, Up] ~ etc. Since up only ‘rotates’ the tree. So I had to change the datatype from
data Tree a = Branch [Tree a] | Leaf a
to
data Tree a = Top [Tree a] | Branch [Tree a] | Leaf a
This enabled me to keep track of the top node, thus checking if there were the right amount of closing brackets. The rest of the code is a bit of a struggle with the Either e monad, but should be fairly obvious.
kmc on Haskell IRC was kind enough give me a proper solution to this problem
A Fixpoint of Identity 