Algebraic Data Types

10.1 Sum Types (Enumerations and Variants)

data Color = Red | Green | Blue
  deriving (Show, Eq, Ord, Enum, Bounded)

-- [minBound .. maxBound] :: [Color] == [Red, Green, Blue]
-- succ Red == Green

data Shape
  = Circle Double                 -- constructor with a field
  | Rectangle Double Double
  | Triangle Double Double Double
  deriving (Show, Eq)

area :: Shape -> Double
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
area (Triangle a b c) = sqrt (s * (s - a) * (s - b) * (s - c))
  where
    s = (a + b + c) / 2

10.2 Product Types and Parameterized Types

data Point = Point Double Double deriving (Show, Eq)   -- type and constructor can share a name

data Pair a b = Pair a b deriving Show                  -- parameterized

-- Recursive data types
data List a = Nil | Cons a (List a) deriving Show

data Tree a = Leaf | Node (Tree a) a (Tree a)
  deriving Show

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x t@(Node l v r)
  | x < v = Node (insert x l) v r
  | x > v = Node l v (insert x r)
  | otherwise = t

toList :: Tree a -> [a]
toList Leaf = []
toList (Node l v r) = toList l ++ [v] ++ toList r

fromList :: Ord a => [a] -> Tree a
fromList = foldr insert Leaf

depth :: Tree a -> Int
depth Leaf = 0
depth (Node l _ r) = 1 + max (depth l) (depth r)

-- toList (fromList [5, 3, 8, 1, 4]) == [1,3,4,5,8]

10.3 Expression Trees (a Classic Example)

data Expr
  = Lit Integer
  | Add Expr Expr
  | Mul Expr Expr
  | Neg Expr
  | Var String
  deriving (Show, Eq)

eval :: [(String, Integer)] -> Expr -> Maybe Integer
eval _ (Lit n) = Just n
eval env (Add a b) = (+) <$> eval env a <*> eval env b
eval env (Mul a b) = (*) <$> eval env a <*> eval env b
eval env (Neg a) = negate <$> eval env a
eval env (Var v) = lookup v env

simplify :: Expr -> Expr
simplify (Add (Lit 0) e) = simplify e
simplify (Add e (Lit 0)) = simplify e
simplify (Mul (Lit 1) e) = simplify e
simplify (Mul e (Lit 1)) = simplify e
simplify (Mul (Lit 0) _) = Lit 0
simplify (Add a b) = Add (simplify a) (simplify b)
simplify (Mul a b) = Mul (simplify a) (simplify b)
simplify e = e

10.4 newtype

Algebra of types: sum types add (Either a b has |a| + |b| values), product types multiply ((a, b) has |a| × |b|), and functions exponentiate (a -> b has |b|^|a|).

Make illegal states unrepresentable: design types so invalid combinations can't be constructed.

newtype UserId = UserId Int deriving (Show, Eq, Ord)
newtype Email = Email String deriving Show
-- newtype: exactly one constructor with one field; zero runtime cost; a distinct type for safety
sendEmail :: Email -> String -> IO ()
sendEmail (Email addr) body = putStrLn ("To " ++ addr ++ ": " ++ body)