Algebraic Data Types

The data keyword defines your own types. Haskell's data types are called algebraic data types (ADTs), because they're built from two operations: "or" (sum types) and "and" (product types).

Sum types: one of several choices

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

describe :: Color -> String
describe Red = "warm"
describe Green = "natural"
describe Blue = "cool"

main :: IO ()
main = do
  print Red
  putStrLn (describe Blue)
  print (Red == Green)
  print (map describe [Red, Green, Blue])

Red
cool
False
["warm","natural","cool"]

Red, Green, and Blue are constructors — the only possible values of type Color. deriving (Show, Eq) asks GHC to generate code so the values can be printed and compared. Bool itself is defined in the standard library as data Bool = False | True.

Constructors with fields

Each constructor can carry data:

data Shape
  = Circle Double
  | Rectangle Double Double
  | Triangle Double Double Double
  deriving (Show)

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

main :: IO ()
main = do
  let shapes = [Circle 1, Rectangle 3 4, Triangle 3 4 5]
  mapM_ print shapes
  print (map area shapes)
  print (sum (map area shapes))

Circle 1.0
Rectangle 3.0 4.0
Triangle 3.0 4.0 5.0
[3.141592653589793,12.0,6.0]
21.141592653589793

• A constructor is also a function: Rectangle :: Double -> Double -> Shape. So map Circle [1, 2] builds a list of circles.
• Pattern matching pulls the fields back out.
• If you add a new constructor and forget to handle it, -Wall warns you in every function that pattern matches on Shape.

Recursive types

A type can refer to itself. Here is a binary search tree:

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 left v right)
  | x < v = Node (insert x left) v right
  | x > v = Node left v (insert x right)
  | otherwise = t

toList :: Tree a -> [a]
toList Leaf = []
toList (Node left v right) = toList left ++ [v] ++ toList right

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

main :: IO ()
main = do
  let tree = foldr insert Leaf [5, 2, 8, 1, 9, 3 :: Int]
  print (toList tree)
  print (depth tree)
  print (insert 'b' (insert 'a' Leaf))

[1,2,3,5,8,9]
4
Node Leaf 'a' (Node Leaf 'b' Leaf)

Tree a is a parameterized type: a can be any type, so the same code builds trees of numbers, characters, or strings. Ord a => says the elements must be orderable, because insert uses <.

type and newtype

type Name = String

newtype UserId = UserId Int
  deriving (Show, Eq)

greet :: Name -> String
greet n = "Hi, " ++ n

lookupUser :: UserId -> String
lookupUser (UserId 1) = "admin"
lookupUser (UserId _) = "guest"

main :: IO ()
main = do
  putStrLn (greet "Ada")
  putStrLn (lookupUser (UserId 1))
  print (UserId 7)

Hi, Ada
admin
UserId 7

• type creates an alias — Name and String are interchangeable.
• newtype creates a genuinely new type with exactly one constructor and one field. It costs nothing at runtime, but the compiler won't let you pass a plain Int (or an OrderId) where a UserId is expected.

Practice

Define data Suit = Hearts | Diamonds | Clubs | Spades and a function isRed :: Suit -> Bool, then print the red suits from a list of all four.

data Suit = Hearts | Diamonds | Clubs | Spades
  deriving (Show, Eq, Enum, Bounded)

isRed :: Suit -> Bool
isRed Hearts = True
isRed Diamonds = True
isRed _ = False

main :: IO ()
main = print (filter isRed [minBound .. maxBound])

[Hearts,Diamonds]