CS计算机代考程序代写 flex \begin{code}

\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)