{-# OPTIONS_GHC -fglasgow-exts #-}

module CST where


data CST token
  = Branch [CST token]
  | Leaf token

type CSTAlg token r = ([r] -> r, token -> r)

foldCST :: CSTAlg symbol r -> CST symbol -> r
foldCST (f1, f2) = f where
  f (Branch cs) = f1 (map f cs)
  f (Leaf t) = f2 t

flatten :: CST token -> [token]
flatten = foldCST (concat, (:[]))




data PTree a
  = PLeaf a
  | PBranch (PList a)

data PList a
  = PNil
  | forall b. PCons (PTree (b -> a)) (PList b)


data P a
  = PUnit a
  | forall b. PApply (b -> a) (P b)
  | forall b. PSeq (P (b -> a)) (P b)

value :: P a -> a
value (PUnit x) = x
value (PApply f px) = f $ value px
value (PSeq pf px) = value pf $ value px




type Parser symbol result  =  [symbol] -> [(result,[symbol])]


(<|>)         :: Parser s a      -> Parser s a -> Parser s a
(p <|> q) xs  =  p xs ++ q xs

(<*>)         :: Parser s (b -> a) -> Parser s b -> Parser s a
(p <*> q) xs  =  [(f x,zs)
                 |(f  ,ys) <- p xs
                 ,(  x,zs) <- q ys
                 ]

(<$>)         :: (a -> b) -> Parser s a -> Parser s b
(f <$> p) xs  =  [(f y,ys)
                 |(  y,ys) <- p xs
                 ]