How to parse a tree-like structure using PArrows?

104 views Asked by At

I'm trying to learn arrows, as well as how PArrows can replace Parsec, but there is an almost nonexistent number of tutorials. I believe we could benefit a lot from simple examples, so, given the binary tree:

data Tree = Node Tree Tree | A | B deriving Show

How can PArrow be used to parse a string similar to:

"((A B) (A (B A)))" 

So that it becomes:

Node (Node A B) (Node A (Node B A))
1

There are 1 answers

0
MaiaVictor On

This is probably not the cleanest answer, but I managed to do it with:

import Text.ParserCombinators.PArrow
import Control.Arrow

data Tree = Node Tree Tree | A | B deriving Show

text = "((B A) (A B))"

fromToken :: Char -> Tree
fromToken 'A' = A
fromToken 'B' = B

token = anyOf "AB" >>> arr fromToken
node = arr (uncurry Node) 
    <<< ((char '(' >>> token <+> node)   -- left side
    >>! white                            -- whitespace
    &&& ((token <+> node) >>! char ')')) -- right side

main = print $ runParser node text

Mind I'm still working on my arrow familiarity.