Please advise on Haskell libraries to compare trees in textual representation.
I need to compare both structure and node contents of two trees, find similar sub-trees, and need some metric to measure distance between two trees.
Also need advice on simple parser to convert textual tree representation into a data type convenient for tree manipulation (comparison, matching, etc.) What data type to use for trees with arbitrary structure?
Example trees:
*** Tree 1:
(ROOT
(S
(NP (DT The) (NN voice) (NN quality))
(VP (VBD was)
(ADJP (JJ clear) (RB too)))
(. .)))
*** Tree 2:
(ROOT
(S
(SBAR (IN Although)
(S
(NP (DT the) (NN battery) (NN life))
(VP (VBD was) (RB not)
(ADJP (JJ long)))))
(, ,)
(NP (DT that))
(VP (VBZ is)
(VP (VBN ok)
(PP (IN for)
(NP (PRP me)))))
(. .)))
Thanks!
Dmitri