\begin{code}
{-# OPTIONS_GHC -Wall #-}
module Jan28 where
\end{code}
Learning objectives:
\begin{itemize}
\item algebraic data types
\item mutual recursion in types
\end{itemize}
\begin{code}
data Expr =
Lit Integer
| Expr :+: Expr
| Expr :-: Expr
deriving Show
ee1, ee2, ee3, ee4 :: Expr
ee1 = Lit 5 :+: (Lit 6 :-: Lit 12)
ee2 = (Lit 5 :+: Lit 6) :-: Lit 12
ee3 = (Lit 5 :+: Lit 6) :+: Lit 12
ee4 = (ee3 :+: ee3) :+: ee3
eval :: Expr -> Integer
eval (Lit i) = i
eval (e1 :+: e2) = eval e1 + eval e2
eval (e1 :-: e2) = eval e1 – eval e2
\end{code}
Recall: $+$ is associative.
Ex:
– (Lit 1 :+: Lit 2) :+: Lit 3 (1)
– Lit 1 :+: (Lit 2 :+: Lit 3) (2)
\begin{code}
assoc :: Expr -> Expr
assoc ((e1 :+: e2) :+: e3) = e1 :+: (e2 :+: e3)
assoc (Lit x) = Lit x
assoc (e1 :-: e2) = assoc e1 :-: assoc e2
assoc (e1 :+: e2) = e1 :+: assoc e2
\end{code}
A slight digression that feels like it helps:
\begin{code}
data Expr’ =
Lit’ Integer
| Add [Expr’]
| Sub’ Expr’ Expr’
deriving Show
\end{code}
Mostly moves the problem….
Introduces: Add [] ? A: Int 0
Also, Add [e1] == e1
The better way:
1. use Expr for external input
2. use Expr’ for internal representation, i.e. post-normalization
\begin{code}
type Name = String — type synonym
data Person = Adult Name Bio
| Child Name
data Bio = Parent String [Person]
| NonParent String
children_names :: Person -> [Name]
children_names (Adult _ b) = names b
children_names (Child _) = []
the_name :: Person -> Name
the_name (Adult n _) = n
the_name (Child n) = n
names :: Bio -> [Name]
names (Parent _ l) = map the_name l
names (NonParent _) = []
\end{code}