\begin{code}
{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}
module Mar23 where
\end{code}
Learning objectives:
\begin{itemize}
\item traversals
\end{itemize}
\begin{code}
data E = I Integer | N E | A E E
deriving Show
— invariants built in to the syntax!
data EE = F Factor | AA EE EE
deriving Show
data Factor = II Integer | NN Integer
deriving Show
push_neg :: E -> EE
push_neg (I i) = F $ II i
push_neg (N (I i)) = F $ NN i
push_neg (N (N x)) = push_neg x
push_neg (N (A i j)) = AA (push_neg (N i)) (push_neg (N j))
push_neg (A i j) = AA (push_neg i) (push_neg j)
push_neg’ :: E -> E
push_neg’ e@(I _) = e
push_neg’ e@(N (I _)) = e
push_neg’ (N (N x)) = push_neg’ x
push_neg’ (N (A i j)) = A (push_neg’ (N i)) (push_neg’ (N j))
push_neg’ (A i j) = A (push_neg’ i) (push_neg’ j)
\end{code}
Can this be done in finally tagless style?
\begin{code}
data Ctx = Pos | Neg
class ESym e where
int :: Integer -> e
neg :: e -> e
add :: e -> e -> e
newtype Foo = FF {unF :: Integer}
instance ESym Foo where
int = FF
neg (FF i) = FF $ -i
add (FF x) (FF y) = FF $ x + y
instance ESym repr => ESym (Ctx -> repr) where
int i Pos = int i
int i Neg = neg (int i)
neg e Pos = e Neg
neg e Neg = e Pos
add e1 e2 ctx = add (e1 ctx) (e2 ctx)
instance ESym E where
int i = I i
neg x = N x
add x y = A x y
ee :: E
ee = (N (A (N (I 3)) (I 5)))
ff :: ESym repr => repr
ff = neg (add (neg (int 3)) (int 5))
\end{code}
Exercise: right-associating expressions. I.e.
A (A (I 4) (I 5)) (I 8) -> A (I 4) (A (I 5) (I 8))
Hint: “left context”
Q: pushing context up?
A: make instance out of pairs (e , info)