cse230
Excerpt
UCSD CSE 230
Recap: Haskell Crash Course II
 Core program element is an expression
 Every valid expression has a type (determined at compiletime)
 Every valid expression reduces to a value (computed at runtime)
Recap: Haskell
Basic values & operators
Int
,Bool
,Char
,Double
+
,
,==
,/=
Execution / Function Calls
 Just substitute equals by equals
Producing Collections
 Pack data into tuples & lists
Consuming Collections
 Unpack data via patternmatching
Next: Creating and Using New Data Types

type
Synonyms: Naming existing types 
data
types: Creating new types
Type Synonyms
Synonyms are just names (“aliases”) for existing types
 think
typedef
inC
A type to represent Circle
A tuple (x, y, r)
is a circle with center at (x, y)
and radius r
type Circle = (Double, Double, Double)
A type to represent Cuboid
A tuple (length, depth, height)
is a cuboid
type Cuboid = (Double, Double, Double)
Using Type Synonyms
We can now use synonyms by creating values of the given types
circ0 :: Circle
circ0 = (0, 0, 100)  ^ circle at "origin" with radius 100
cub0 :: Cuboid
cub0 = (10, 20, 30)  ^ cuboid with length=10, depth=20, height=30
And we can write functions over synonyms too
area :: Circle > Double
area (x, y, r) = pi * r * r
volume :: Cuboid > Double
volume (l, d, h) = l * d * h
We should get this behavior
>>> area circ0
31415.926535897932
>>> volume cub0
6000
QUIZ
Suppose we have the definitions
type Circle = (Double, Double, Double)
type Cuboid = (Double, Double, Double)
circ0 :: Circle
circ0 = (0, 0, 100)  ^ circle at "origin" with radius 100
cub0 :: Cuboid
cub0 = (10, 20, 30)  ^ cuboid with length=10, depth=20, height=30
area :: Circle > Double
area (x, y, r) = pi * r * r
volume :: Cuboid > Double
volume (l, d, h) = l * d * h
What is the result of
A. 0
B. Type error
Beware!
Type Synonyms

Do not create new types

Just name existing types
And hence, synonyms
 Do not prevent confusing different values
Creating New Data Types
We can avoid mixing up by creating new data
types
  A new type `CircleT` with constructor `MkCircle`
data CircleT = MkCircle Double Double Double
  A new type `CuboidT` with constructor `MkCuboid`
data CuboidT = MkCuboid Double Double Double
Constructors are the only way to create values

MkCircle
createsCircleT

MkCuboid
createsCuboidT
QUIZ
Suppose we create a new type with a data
definition
  A new type `CircleT` with constructor `MkCircle`
data CircleT = MkCircle Double Double Double
What is the type of the MkCircle
constructor?
A. MkCircle :: CircleT
B. MkCircle :: Double > CircleT
C. MkCircle :: Double > Double > CircleT
D. MkCircle :: Double > Double > Double > CircleT
E. MkCircle :: (Double, Double, Double) > CircleT
Constructing Data
Constructors let us build values of the new type
circ1 :: CircleT
circ1 = MkCircle 0 0 100  ^ circle at "origin" w/ radius 100
cub1 :: Cuboid
cub1 = MkCuboid 10 20 30  ^ cuboid w/ len=10, dep=20, ht=30
QUIZ
Suppose we have the definitions
data CuboidT = MkCuboid Double Double Double
type Cuboid = (Double, Double, Double)
volume :: Cuboid > Double
volume (l, d, h) = l * d * h
What is the result of
>>> volume (MkCuboid 10 20 30)
A. 6000
B. Type error
Deconstructing Data
Constructors let us build values of new type … but how to use those values?
How can we implement a function
volume :: Cuboid > Double
volume c = ???
such that
>>> volume (MkCuboid 10 20 30)
6000
Deconstructing Data by Pattern Matching
Haskell lets us deconstruct data via patternmatching
volume :: Cuboid > Double
volume c = case c of
MkCuboid l d h > l * d * h
case e of Ctor x y z > e1
is read as as
IF  e
evaluates to a value that matches the pattern Ctor vx vy vz
THEN  evaluate e1
after naming x := vx
, y := vy
, z := vz
Pattern matching on Function Inputs
Very common to do matching on function inputs
volume :: Cuboid > Double
volume c = case c of
MkCuboid l d h > l * d * h
area :: Circle > Double
area a = case a of
MkCircle x y r > pi * r * r
So Haskell allows a nicer syntax: patterns in the arguments
volume :: Cuboid > Double
volume (MkCuboid l d h) = l * d * h
area :: Circle > Double
area (MkCircle x y r) = pi * r * r
Nice syntax plus the compiler saves us from mixing up values!
But … what if we need to mix up values?
Suppose I need to represent a list of shapes
 Some
Circle
s  Some
Cuboid
s
What is the problem with shapes
as defined below?
Where we have defined
circ1 :: CircleT
circ1 = MkCircle 0 0 100  ^ circle at "origin" with radius 100
cub1 :: Cuboid
cub1 = MkCuboid 10 20 30  ^ cuboid with length=10, depth=20, height=30
Problem: All list elements must have the same type
Solution???
QUIZ: Variant (aka Union) Types
Lets create a single type that can represent both kinds of shapes!
data Shape
= MkCircle Double Double Double  ^ Circle at x, y with radius r
 MkCuboid Double Double Double  ^ Cuboid with length, depth, height
What is the type of MkCircle 0 0 100
?
A. Shape
B. Circle
C. (Double, Double, Double)
Each Data Constructor of Shape
has a different type
When we define a data type like the below
data Shape
= MkCircle Double Double Double  ^ Circle at x, y with radius r
 MkCuboid Double Double Double  ^ Cuboid with length, depth, height
We get multiple constructors for Shape
MkCircle :: Double > Double > Double > Shape
MkCuboid :: Double > Double > Double > Shape
Now we can create collections of Shape
Now we can define
circ2 :: Shape
circ2 = MkCircle 0 0 100  ^ circle at "origin" with radius 100
cub2 :: Shape
cub2 = MkCuboid 10 20 30  ^ cuboid with length=10, depth=20, height=30
and then define collections of Shape
s
shapes :: [Shape]
shapes = [circ1, cub1]
EXERCISE
Lets define a type for 2D shapes
data Shape2D
= MkRect Double Double  ^ 'MkRect w h' is a rectangle with width 'w', height 'h'
 MkCirc Double  ^ 'MkCirc r' is a circle with radius 'r'
 MkPoly [Vertex]  ^ 'MkPoly [v1,...,vn]' is a polygon with vertices at 'v1...vn'
type Vertex = (Double, Double)
Write a function to compute the area
of a Shape2D
area2D :: Shape2D > Double
area2D s = ???
HINT
Area of a polygon
You may want to use this helper that computes the area of a triangle at v1
, v2
, v3
areaTriangle :: Vertex > Vertex > Vertex > Double
areaTriangle v1 v2 v3 = sqrt (s * (s  s1) * (s  s2) * (s  s3))
where
s = (s1 + s2 + s3) / 2
s1 = distance v1 v2
s2 = distance v2 v3
s3 = distance v3 v1
distance :: Vertex > Vertex > Double
distance (x1, y1) (x2, y2) = sqrt ((x2  x1) ** 2 + (y2  y1) ** 2)
Polymorphic Data Structures
Next, lets see polymorphic data types
which contain many kinds of values.
Recap: Data Types
Recall that Haskell allows you to create brand new data types
data Shape
= MkRect Double Double
 MkPoly [(Double, Double)]
QUIZ
What is the type of MkRect
?
data Shape
= MkRect Double Double
 MkPoly [(Double, Double)]
a. Shape
b. Double
c. Double > Double > Shape
d. (Double, Double) > Shape
e. [(Double, Double)] > Shape
Tagged Boxes
Values of this type are either two doubles tagged with Rectangle
>>> :type (Rectangle 4.5 1.2)
(Rectangle 4.5 1.2) :: Shape
or a list of pairs of Double
values tagged with Polygon
ghci> :type (Polygon [(1, 1), (2, 2), (3, 3)])
(Polygon [(1, 1), (2, 2), (3, 3)]) :: Shape
Data values inside special Tagged Boxes
Datatypes are BoxedandTagged Values
Recursive Data Types
We can define datatypes recursively too
data IntList
= INil  ^ empty list
 ICons Int IntList  ^ list with "hd" Int and "tl" IntList
deriving (Show)
(Ignore the bit about deriving
for now.)
QUIZ
data IntList
= INil  ^ empty list
 ICons Int IntList  ^ list with "hd" Int and "tl" IntList
deriving (Show)
What is the type of ICons
?
A. Int > IntList > List
B. IntList
C. Int > IntList > IntList
D. Int > List > IntList
E. IntList > IntList
Constructing IntList
Can only build IntList
via constructors.
>>> :type INil
INil:: IntList
>>> :type ICons
ICons :: Int > IntList > IntList
EXERCISE
Write down a representation of type IntList
of the list of three numbers 1
, 2
and 3
.
list_1_2_3 :: IntList
list_1_2_3 = ???
Hint Recursion means boxes within boxes
Recursively Nested Boxes
Trees: Multiple Recursive Occurrences
We can represent Int
trees like
data IntTree
= ILeaf Int  ^ single "leaf" w/ an Int
 INode IntTree IntTree  ^ internal "node" w/ 2 subtrees
deriving (Show)
A leaf is a box containing an Int
tagged ILeaf
e.g.
>>> it1 = ILeaf 1
>>> it2 = ILeaf 2
A node is a box containing two subtrees tagged INode
e.g.
>>> itt = INode (ILeaf 1) (ILeaf 2)
>>> itt' = INode itt itt
>>> INode itt' itt'
INode (INode (ILeaf 1) (ILeaf 2)) (INode (ILeaf 1) (ILeaf 2))
Multiple Branching Factors
e.g. 23 trees
data Int23T
= ILeaf0
 INode2 Int Int23T Int23T
 INode3 Int Int23T Int23T Int23T
deriving (Show)
An example value of type Int23T
would be
i23t :: Int23T
i23t = INode3 0 t t t
where t = INode2 1 ILeaf0 ILeaf0
which looks like
Integer 23 Tree
Parameterized Types
We can define CharList
or DoubleList
 versions of IntList
for Char
and Double
as
data CharList
= CNil
 CCons Char CharList
deriving (Show)
data DoubleList
= DNil
 DCons Char DoubleList
deriving (Show)
Don’t Repeat Yourself!
Don’t repeat definitions  Instead reuse the list structure across all types!
Find abstract data patterns by
 identifying the different parts and
 refactor those into parameters
A Refactored List
Here are the three types: What is common? What is different?
data IList = INil  ICons Int IList
data CList = CNil  CCons Char CList
data DList = DNil  DCons Double DList
Common: Nil
/Cons
structure
Different: type of each “head” element
Refactored using Type Parameter
data List a = Nil  Cons a (List a)
Recover original types as instances of List
type IntList = List Int
type CharList = List Char
type DoubleList = List Double
Polymorphic Data has Polymorphic Constructors
Look at the types of the constructors
>>> :type Nil
Nil :: List a
That is, the Empty
tag is a value of any kind of list, and
>>> :type Cons
Cons :: a > List a > List a
Cons
takes an a
and a List a
and returns a List a
.
cList :: List Char  list where 'a' = 'Char'
cList = Cons 'a' (Cons 'b' (Cons 'c' Nil))
iList :: List Int  list where 'a' = 'Int'
iList = Cons 1 (Cons 2 (Cons 3 Nil))
dList :: List Double  list where 'a' = 'Double'
dList = Cons 1.1 (Cons 2.2 (Cons 3.3 Nil))
Polymorphic Function over Polymorphic Data
Lets write the list length function
len :: List a > Int
len Nil = 0
len (Cons x xs) = 1 + len xs
len
doesn’t care about the actual values in the list  only “counts” the number of Cons
constructors
Hence len :: List a > Int
 we can call
len
on any kind of list.
>>> len [1.1, 2.2, 3.3, 4.4]  a := Double
4
>>> len "mmm donuts!"  a := Char
11
>>> len [[1], [1,2], [1,2,3]]  a := ???
3
Builtin Lists?
This is exactly how Haskell’s “builtin” lists are defined:
data [a] = []  (:) a [a]
data List a = Nil  Cons a (List a)
Nil
is called[]
Cons
is called:
Many list manipulating functions e.g. in [Data.List][1] are polymorphic  Can be reused across all kinds of lists.
(++) :: [a] > [a] > [a]
head :: [a] > a
tail :: [a] > [a]
Generalizing Other Data Types
Polymorphic trees
data Tree a
= Leaf a
 Node (Tree a) (Tree a)
deriving (Show)
Polymorphic 23 trees
data Tree23 a
= Leaf0
 Node2 (Tree23 a) (Tree23 a)
 Node3 (Tree23 a) (Tree23 a) (Tree23 a)
deriving (Show)
Kinds
List a
corresponds to lists of values of type a
.
If a
is the type parameter, then what is List
?
A typeconstructor that  takes as input a type a
 returns as output the type List a
But wait, if List
is a typeconstructor then what is its “type”?
 A kind is the “type” of a type.
>>> :kind Int
Int :: *
>>> :kind Char
Char :: *
>>> :kind Bool
Bool :: *
Thus, List
is a function from any “type” to any other “type”, and so
>>> :kind List
List :: * > *
QUIZ
What is the kind of >
? That, is what does GHCi say if we type
A. *
B. * > *
C. * > * > *
We will not dwell too much on this now.
As you might imagine, they allow for all sorts of abstractions over data.
If interested, see this for more information about kinds.