CSE230 Slides 02: Haskell Basics
Excerpt
UCSD CSE 230
From the Lambda Calculus to Haskell
Programming in Haskell
Computation by Calculation
Substituting equals by equals
Computation via Substituting Equals by Equals
(1 + 3) * (4 + 5)
 subst 1 + 3 = 4
==> 4 * (4 + 5)
 subst 4 + 5 = 9
==> 4 * 9
 subst 4 * 9 = 36
==> 36
Computation via Substituting Equals by Equals
EqualitySubstitution enables Abstraction via Pattern Recognition
Abstraction via Pattern Recognition
Repeated Expressions
31 * (42 + 56)
70 * (12 + 95)
90 * (68 + 12)
Recognize Pattern as λfunction
pat = \x y z > x * ( y + z )
Equivalent Haskell Definition
pat x y z = x * ( y + z )
Function Call is Pattern Instance
pat 31 42 56 =*> 31 * (42 + 56) =*> 31 * 98 =*> 3038
pat 70 12 95 =*> 70 * (12 + 95) =*> 70 * 107 =*> 7490
pat 90 68 12 =*> 90 * (68 + 12) =*> 90 * 80 =*> 7200
Key Idea: Computation is substitute equals by equals.
Programming in Haskell
Substitute Equals by Equals
Thats it! (Do not think of registers, stacks, frames etc.)
Elements of Haskell
 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)
Illtyped* expressions are rejected at compiletime before execution
 like in Java
 not like λcalculus or Python …
The Haskell EcoSystem

Batch compiler:
ghc
Compile and run large programs 
Interactive Shell
ghci
Shell to interactively run small programs online 
Build Tool
stack
Build tool to manage libraries etc.
Interactive Shell: ghci
$ stack ghci
:load file.hs
:type expression
:info variable
A Haskell Source File
A sequence of toplevel definitions x1
, x2
, …

Each has type
type_1
,type_2
, … 
Each defined by expression
expr_1
,expr_2
, …
x_1 :: type_1
x_1 = expr_1
x_2 :: type_2
x_2 = expr_2
.
.
.
Basic Types
ex1 :: Int
ex1 = 31 * (42 + 56)  this is a comment
ex2 :: Double
ex2 = 3 * (4.2 + 5.6)  arithmetic operators "overloaded"
ex3 :: Char
ex3 = 'a'  'a', 'b', 'c', etc. builtin `Char` values
ex4 :: Bool
ex4 = True  True, False are builtin Bool values
ex5 :: Bool
ex5 = False
QUIZ: Basic Operations
ex6 :: Int
ex6 = 4 + 5
ex7 :: Int
ex7 = 4 * 5
ex8 :: Bool
ex8 = 5 > 4
quiz :: ???
quiz = if ex8 then ex6 else ex7
What is the type of quiz
?
A. Int
B. Bool
C. Error!
QUIZ: Basic Operations
ex6 :: Int
ex6 = 4 + 5
ex7 :: Int
ex7 = 4 * 5
ex8 :: Bool
ex8 = 5 > 4
quiz :: ???
quiz = if ex8 then ex6 else ex7
What is the value of quiz
?
A. 9
B. 20
C. Other!
Function Types
In Haskell, a function is a value that has a type
A function that
 takes input of type
A
 returns output of type
B
For example
isPos :: Int > Bool
isPos = \n > (x > 0)
Define functionexpressions using \
like in λcalculus!
But Haskell also allows us to put the parameter on the left
isPos :: Int > Bool
isPos n = (x > 0)
(Meaning is identical to above definition with \n > ...
)
Multiple Argument Functions
A function that
 takes three inputs
A1
,A2
andA3
 returns one output
B
has the type
For example
pat :: Int > Int > Int > Int
pat = \x y z > x * (y + z)
which we can write with the params on the left as
pat :: Int > Int > Int > Int
pat x y z = x * (y + z)
QUIZ
What is the type of quiz
?
quiz :: ???
quiz x y = (x + y) > 0
A. Int > Int
B. Int > Bool
C. Int > Int > Int
D. Int > Int > Bool
E. (Int, Int) > Bool
Function Calls
A function call is exactly like in the λcalculus
where e1
is a function and e2
is the argument. For example
>>> isPos 12
True
>>> isPos (0  5)
False
Multiple Argument Calls
With multiple arguments, just pass them in one by one, e.g.
For example
EXERCISE
Write a function myMax
that returns the maximum of two inputs
myMax :: Int > Int > Int
myMax = ???
When you are done you should see the following behavior:
>>> myMax 10 20
20
>>> myMax 100 5
100
How to Return Multiple Outputs?
Tuples
A type for packing n
different kinds of values into a single “struct”
For example
tup1 :: ???
tup1 = ('a', 5)
tup2 :: (Char, Double, Int)
tup2 = ('a', 5.2, 7)
QUIZ
What is the type ???
of tup3
?
tup3 :: ???
tup3 = ((7, 5.2), True)
A. (Int, Bool)
B. (Int, Double, Bool)
C. (Int, (Double, Bool))
D. ((Int, Double), Bool)
E. (Tuple, Bool)
We can create a tuple of three values e1
, e2
, and e3
…
… but how to extract the values from this tuple?
Pattern Matching
fst3 :: (t1, t2, t3) > t1
fst3 (x1, x2, x3) = x1
snd3 :: (t1, t2, t3) > t2
snd3 (x1, x2, x3) = x2
thd3 :: (t1, t2, t3) > t3
thd3 (x1, x2, x3) = x3
QUIZ
What is the value of quiz
defined as
tup2 :: (Char, Double, Int)
tup2 = ('a', 5.2, 7)
snd3 :: (t1, t2, t3) > t2
snd3 (x1, x2, x3) = x2
quiz = snd3 tup2
A. 'a'
B. 5.2
C. 7
D. ('a', 5.2)
E. (5.2, 7)
Lists
Unbounded Sequence of values of type T
For example
chars :: [Char]
chars = ['a','b','c']
ints :: [Int]
ints = [1,3,5,7]
pairs :: [(Int, Bool)]
pairs = [(1,True),(2,False)]
QUIZ
What is the type of things
defined as
things :: ???
things = [ [1], [2, 3], [4, 5, 6] ]
A. [Int]
B. ([Int], [Int], [Int])
C. [(Int, Int, Int)]
D. [[Int]]
E. List
List’s Values Must Have The SAME Type!
The type [T]
denotes an unbounded sequence of values of type T
Suppose you have a list
There is no T
that we can use
 As last element is not
Int
 First two elements are not
Char
!
Result: Mysterious Type Error!
Constructing Lists
There are two ways to construct lists
[]  creates an empty list
h:t  creates a list with "head" 'h' and "tail" t
For example
>>> 3 : []
[3]
>>> 2 : (3 : [])
[2, 3]
>>> 1 : (2 : (3 : []))
[1, 2, 3]
Cons Operator :
is Right Associative
x1 : x2 : x3 : x4 : t
means x1 : (x2 : (x3 : (x4 : t)))
So we can just avoid the parentheses.
Syntactic Sugar
Haskell lets you write [x1, x2, x3, x4]
instead of x1 : x2 : x3 : x4 : []
Functions Producing Lists
Lets write a function copy3
that
 takes an input
x
and  returns a list with three copies of
x
copy3 :: ???
copy3 x = ???
When you are done, you should see the following
>>> copy3 5
[5, 5, 5]
>>> copy3 "cat"
["cat", "cat", "cat"]
PRACTICE: Clone
Write a function clone
such that clone n x
returns a list with n
copies of x
.
clone :: ???
clone n x = ???
When you are done you should see the following behavior
>>> clone 0 "cat"
[]
>>> clone 1 "cat"
["cat"]
>>> clone 2 "cat"
["cat", "cat"]
>>> clone 3 "cat"
["cat", "cat", "cat"]
>>> clone 3 100
[100, 100, 100]
How does clone
execute?
(Substituting equalsbyequals!)
EXERCISE: Range
Write a function range
such that range i j
returns the list of values [i, i+1, ..., j]
range :: ???
range i j = ???
When we are done you should get the behavior
>>> range 4 3
[]
>>> range 3 3
[3]
>>> range 2 3
[2, 3]
>>> range 1 3
[1, 2, 3]
>>> range 0 3
[0, 1, 2, 3]
Functions Consuming Lists
So far: how to produce lists.
Next how to consume lists!
Example
Lets write a function firstElem
such that firstElem xs
returns the first element xs
if it is a nonempty list, and 0
otherwise.
firstElem :: [Int] > Int
firstElem xs = ???
When you are done you should see the following behavior:
>>> firstElem []
0
>>> firstElem [10, 20, 30]
10
>>> firstElem [5, 6, 7, 8]
5
QUIZ
Suppose we have the following mystery
function
mystery :: [a] > Int
mystery [] = 0
mystery (x:xs) = 1 + mystery xs
What does mystery [10, 20, 30]
evaluate to?
A. 10
B. 20
C. 30
D. 3
E. 0
EXERCISE: Summing a List
Write a function sumList
such that sumList [x1, ..., xn]
returns x1 + ... + xn
sumList :: [Int] > Int
sumList = ???
When you are done you should get the following behavior:
>>> sumList []
0
>>> sumlist [3]
3
>>> sumlist [2, 3]
5
>>> sumlist [1, 2, 3]
6
Recap
 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)
Execution

Basic values & operators

Execution / Function Calls just substitute equals by equals

Pack data into tuples & lists

Unpack data via patternmatching