CMPT383 Comparative Programming Languages
Lecture 2: Syntax in Functions
Yuepeng Wang
Spring 2025
1
Overview
• Pattern matching
• Conditionals
• List comprehensions
• Let and where
• Recursion
• Mutual recursion
• Tail recursion
2
Pattern Matching
• Pattern matching specifies patterns to which the data should conform and
to deconstruct the data according to those patterns
• When defining functions in Haskell, we can create separate function
bodies for different patterns
• It leads to simple, readable code
• Intuitively, we can express “if the argument looks like this, the result is …”
3
Pattern Matching: Example
• A function for logical and
myAnd :: Bool -> Bool -> Bool
myAnd True b = b
myAnd False _ = False
• First line of the implementation says: if the first argument is True, the result
is the same as the second argument
• The named argument (e.g., b) matches anything and captures its value
• The literal (e.g., True, False) matches the value when equal
• Second line: if the first argument is False, the result is False
• The _ matches anything but drops its value
4
Pattern Matching: Example
• The behavior of myAnd is the same as the logical and
ghci> myAnd True True
True
ghci> myAnd True False
False
ghci> myAnd False True
False
ghci> myAnd False False
False
5
Pattern Matching: Order
• The order of different patterns is very important
• Rule: the patterns will be checked from top to bottom. The first pattern
that matches the input applies
• Example lucky :: Int -> String
lucky 7 = "Lucky"
lucky _ = "Out of luck"
• Execution results ghci> lucky 7
"Lucky"
ghci> lucky 1
"Out of luck"
6
Pattern Matching: Tuples
• Pattern matching can also be used on tuples
• We might write the following code for pair addition without pattern
matching (fst and snd are functions from Prelude)
addPairs :: (Int, Int) -> (Int, Int) -> (Int, Int)
addPairs x y = (fst x + fst y, snd x + snd y)
• With pattern matching
addPairs' :: (Int, Int) -> (Int, Int) -> (Int, Int)
addPairs' (x1, x2) (y1, y2) = (x1 + y1, x2 + y2)
7
Pattern Matching: Lists
• We can also pattern match against lists
• A common pattern to deconstruct a list is by its head and tail
• Example myHead :: [a] -> a
myHead [] = error "Empty List"
myHead (x:_) = x
error is a function from Prelude that throws an exception with a message
• Execution results
ghci> myHead [1, 2, 3]
1
ghci> myHead []
*** Exception: Empty List
8
Pattern Matching: Lists
• This pattern is very common for recursing over a list
• Code template
func [] = …
func (x:xs) = … func xs …
• Example: compute the length of a list
myLength :: [a] -> Int
myLength [] = 0
myLength (_:xs) = 1 + myLength xs
9
Patterns of Lists
• [ ] matches an empty list
• [x] matches a singleton list (exactly one element)
• (x:xs) matches a list with at least one element
• The head is x, the tail is xs (could be empty)
• (x:y:xs) matches a list with at least two elements
• The head is x, second element is y, the rest of list is xs (could be empty)
• And many more, e.g., [x, y], (x:y:z:_), (_:_:_:_:_:_), etc
10
Patterns of Lists
• Suppose we have a pattern (x:y:xs)
List x y xs
[1,2,3,4,5] 1 2 [3,4,5]
[1,2] 1 2 []
"abc" 'a' 'b' "c"
[1] does not match
11
Pattern Matching: As-Patterns
• As-patterns can break up a value according to the pattern, while still
keeping a reference to the original value
firstLetter :: String -> String
firstLetter "" = "Empty String"
firstLetter all@(x:xs) = "The fisrt letter of " ++ all ++ " is " ++ [x]
• It also works for tuples
firstElem :: (Int, Int) -> String
firstElem x@(x1, x2) = "The first elem of " ++ show x ++ " is " ++ show x1
12
Non-Exhaustive Patterns
• If the input is not matched by any pattern, Haskell throws an exception
"non-exhaustive patterns"
• Example
badAdd :: [Int] -> Int
badAdd (x:y:_) = x + y
• It only adds the first two elements for lists with length >= 2
ghci> badAdd [1,2,3,4]
3
ghci> badAdd [1]
*** Exception: Non-exhaustive patterns in function badAdd
13
Non-Exhaustive Patterns
• "Non-exhaustive patterns" typically means that the programmer misses
some cases of the input in the implementation
• We should inspect the implementation and add the missing cases
• Sometimes it is convenient to use _ to match all values
badAddFixed :: [Int] -> Int
badAddFixed [] = 0
badAddFixed [x] = x
badAddFixed (x:y:_) = x + y
14
Conditionals: If-Then-Else
• Haskell has several different ways to write code involving conditions
• The If-Then-Else expression is a simple way
• Example
pos :: Int -> String
pos x = if x > 0
then "Pos"
else "Non-Pos"
15
Conditionals: Guarded Equations
• An alternative way to avoid scary nested if-then-else: guarded equations
mySignum :: (Num a, Ord a) => a -> Int
mySignum x
| x>0 = 1
| x<0 = -1
| otherwise = 0
• Analogous to the mathematical function
1 if x >0
{
signum(x) = −1 if x < 0
0 otherwise
16
Conditionals: Case Expressions
• Case expressions can be used to define results based on the possible
cases of a value
word :: Int -> String
word n = case n of
1 -> "one"
2 -> "two"
3 -> “three"
_ -> "something else"
• It is an expression; it can be used like any other Haskell expression
17
Conditionals: Case Expressions
• All cases of a case expression are patterns, just like function definitions
describeList :: [a] -> String
describeList ls = "The list is " ++ case ls of
[] -> "empty"
[_] -> "a singleton list"
_ -> "a longer list"
• Execution results
ghci> describeList [1,2,3,4,5]
"The list is a longer list"
ghci> describeList [1]
"The list is a singleton list"
ghci> describeList []
"The list is empty”
18
List Comprehensions
• Recall the notation from math for building sets
2
{x | x ∈ {1,…,5}, even x}
• Haskell has a very similar notation to build a list
• A list comprehension is a way in Haskell to describe, filter, transform, and
combine lists
19
List Comprehensions: Generators
• The generator creates source values in the comprehension
• A generator uses the drawn from operator <- with a list on the right
• Each generator value is used as an argument of the representative
expression
ghci> [ x^2 | x <- [1, 2, 3, 4, 5] ]
[1,4,9,16,25]
ghci> [ succ c | c <- "abcd" ]
"bcde"
succ is from Prelude; it means successor, the next one
20
List Comprehensions: Generators
• A list comprehension can have more than one generator, with successive
generators being separated by lemmas
• Every pair of values is produced
• Example
ghci> [ 10*x + y | x <- [1, 2, 3], y <- [4, 5] ]
[14, 15, 24, 25, 34, 35]
21
List Comprehensions: Guards
• List comprehensions can also use logical expressions called guards to
filter the values produced by generators
• A guard is a predicate (boolean expression)
• If the guard evaluates to True under a value, the value is retained
• If the guard evaluates to False, the value is discarded
ghci> [ x^2 | x <- [1, 2, 3, 4, 5] ]
[1,4,9,16,25]
ghci> [ x^2 | x <- [1, 2, 3, 4, 5], even x ]
[4,16]
even is from Prelude
22
List Comprehensions
• The .. operator can be used to build a list/sequence
Expression Result
[1..5] [1,2,3,4,5]
[3,6..20] [3,6,9,12,15,18]
[‘a’..’g’] “abcdefg”
• It helps to write a list comprehension with a sequence of numbers being
the generator
squares n = [ x^2 | x <- [1..n] ]
foo = [ x*2 | x <- [1..10], x * 2 >= 12]
bar = [ x | x <- [50..100], x `mod` 7 == 3 ]
23
Let and Where
• Writing readable code is very important
• Let and where constructs are helpful for improving code readability
• We should use let or where if the code is getting complicated
• Break up long expressions
• Give the sub-expressions meaningful names
24
Let Expressions
• The “let … in …” construct is an expression
• It can be used anywhere expressions are allowed
ghci> let x = 9 in x+1
10
ghci> 4 * (let x = 9 in x+1) + 2
42
• It can be used to simplify longer definitions
cylinder :: Double -> Double -> Double
cylinder r h =
let sideArea = 2 * pi * r * h
topArea = pi * r * r
in sideArea + 2 * topArea
25
Let Expressions
cylinder :: Double -> Double -> Double
cylinder r h =
let sideArea = 2 * pi * r * h
topArea = pi * r * r
in sideArea + 2 * topArea
• In the example of cylinder surface area, the let expression allows us to
• Split one long expression into several short ones
• Give the sub-expression meaningful names
• Note that all sub-expressions (sideArea, topArea) are aligned to the same
column; otherwise, it causes a parse error
26
Where Clauses
• The where clause is bound to a surrounding syntactic construct, like the
pattern matching line of a function definition
cylinder' :: Double -> Double -> Double
cylinder' r h = sideArea + 2 * topArea
where sideArea = 2 * pi * r * h
topArea = pi * r * r
• Similar to let-in expressions, where clauses allow multiple sub-
expressions, separated by line break or semicolon
• Note that all sub-expressions (sideArea, topArea) are aligned to the same
column; otherwise, it causes a parse error
27
Let vs. Where
• The let expressions allow us to bind variables everywhere
• The where clauses can only bind variables at the end of a function
ghci> 1 + (let x = 10 in 2 * x)
21
ghci> 1 + (2 * x where x = 10)
<interactive>:2:12: error: parse error on input ‘where’
28
Let vs. Where
• Variables in let are local; they do not span across guards
• Variables in where are visible to the entire function
baz :: Int -> String
baz x
| x > 0 = s
| otherwise = "not " ++ s
where s = "pos"
baz :: Int -> String
baz x
| x > 0 = let s = "pos" in s
| otherwise = "not " ++ s
29
Recursion
• Haskell does not have loops in the traditional sense
• It supports recursions that can be used instead of loops
• With recursions and conditionals, the language is Turing complete
• Example: factorial
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)
30
Recursion
• The definition of a recursive function has two cases
• Base case: simple case where the result is straightforward
• Recursive case: find a subproblem, call the same function to solve the
subproblem, use the sub-result to create the result for the bigger problem
• Example: argument n decreases to n-1 or n/2. Base case is 0 or 1.
• Example: argument (x:xs) becomes xs. Base case is [ ] or [x].
31
Example: maximum
• Write a function that returns the maximum element of a list
• What is the type of the function?
• Ord a => [a] -> a
• Code (using the max function for two elements from Prelude)
myMaximum :: Ord a => [a] -> a
myMaximum [] = error "Empty List"
myMaximum [x] = x
myMaximum (x:xs) = max x (myMaximum xs)
32
Example: Quick Sort
• Quick sort only needs four lines of code!
• What is the type of the quick sort function?
• Ord a => [a] -> [a]
• Code
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = smaller ++ [x] ++ larger
where smaller = quicksort [a | a<-xs, a<=x]
larger = quicksort [a | a<-xs, a>x]
33
Example: replicate
• replicate (from Prelude) takes an Int and a value, and returns a list that
has the specified number of repetitions of the value
• What is the type of replicate?
• Int -> a -> [a]
• Code
myReplicate :: Int -> a -> [a]
myReplicate n v
| n <= 0 = []
| otherwise = v : myReplicate (n - 1) v
34
Example: take
• take (from Prelude) takes an Int n and a list, and returns the first n
elements of the list
• What is the type of take?
• Int -> [a] -> [a]
• Code
myTake :: Int -> [a] -> [a]
myTake n _
| n <= 0 = []
myTake _ [] = []
myTake n (x:xs) = x : myTake (n-1) xs
35
Example: zip
• zip (from Prelude) takes two lists and zips them together. It truncates the
longer list to match the length of the shorter one.
• For example, zip [1, 2, 3] [7, 8] returns [(1, 7), (2, 8)]
• What is the type of zip?
• [a] -> [b] -> [(a, b)]
• Code myZip :: [a] -> [b] -> [(a, b)]
myZip _ [] = []
myZip [] _ = []
myZip (x:xs) (y:ys) = (x, y) : myZip xs ys
36
Recursion with Auxiliary Functions
• A function may need additional parameters to track some information but
those additional parameters should be invisible to the client
• We can define multiple functions
• One or more auxiliary functions with additional parameters
• A “main” function for the client with a clean “interface”
37
Example: findFirst
• findFirst takes a value V and a list as input, and returns the position of the
first occurrence of V in the list (0-indexed). If V does not exist in the list, it
returns -1
• The findFirst function should only have two parameters, but we need an
additional parameter to track the index
findFirst :: Eq a => a -> [a] -> Int
findFirst v xs = findFirstAux 0 v xs
findFirstAux :: Eq a => Int -> a -> [a] -> Int
findFirstAux _ _ [] = -1
findFirstAux i v (x:xs)
| v == x = i
| otherwise = findFirstAux (i + 1) v xs
38
Example: findFirst
• Problem: findFirstAux is also visible in the top-level scope
• We can hide auxiliary functions in the top-level scope using where
findFirst :: Eq a => a -> [a] -> Int
findFirst v xs = findFirstAux 0 v xs
where
findFirstAux :: Eq a => Int -> a -> [a] -> Int
findFirstAux _ _ [] = -1
findFirstAux i v (x:xs)
| v == x = i
| otherwise = findFirstAux (i + 1) v xs
39
Mutual Recursion
• Functions can be defined using mutual recursion, where two or more
functions are defined recursively in terms of each other
• Example: the even and odd functions (from Prelude)
myEven :: Int -> Bool
myEven 0 = True
myEven n = myOdd (n - 1)
myOdd :: Int -> Bool
myOdd 0 = False
myOdd n = myEven (n - 1)
40
Mutual Recursion
• Another example: two functions (evens and odds) that select the elements
from a list at all even and odd positions (0-indexed)
• What are the types of evens and odds?
• evens :: [a] -> [a] odds :: [a] -> [a]
evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs
odds :: [a] -> [a]
odds [] = []
odds (_:xs) = evens xs
41
Efficiency of Recursion
• One may complain that a recursive function is less efficient than the
iterative version because the former needs to maintain a large call stack
• Example: sumTo function that computes the sum of integers from 0 to N
sumTo :: Integer -> Integer
sumTo 0 = 0
sumTo n = n + sumTo (n - 1)
42
Efficiency of Recursion
• How is sumTo 3 calculated?
sumTo 3
= 3 + sumTo 2
= 3 + (2 + sumTo 1)
= 3 + (2 + (1 + sumTo 0)))
= 3 + (2 + (1 + 0)))
= 3 + (2 + 1)
= 3 + 3
= 6
*conceptually, without thunk (unevaluated expressions)
• The calculation starts from the base case, but the function needs to
decrease the parameter to reach the base case
43
Efficiency of Recursion
sumTo 3
= 3 + sumTo 2
= 3 + (2 + sumTo 1)
= 3 + (2 + (1 + sumTo 0)))
= 3 + (2 + (1 + 0)))
= 3 + (2 + 1)
= 3 + 3
= 6
• Many frames are saved on the stack, because the return value of a
recursive call is used by the caller to build the result
• What if we don’t need to use the return value to “build” the result?
44
Tail Recursion
• A function is tail recursive when a recursive call is the last thing executed
by the function
• Example: sumToTailRec that computes the sum of integers from 0 to N
sumToTailRec :: Integer -> Integer
sumToTailRec n = sumToTailRecAux n 0
sumToTailRecAux :: Integer -> Integer -> Integer
sumToTailRecAux n r
| n == 0 = r
| otherwise = sumToTailRecAux (n - 1) (n + r)
45
Tail Recursion
• How is sumToTailRec 3 calculated?
sumToTailRec 3
= sumToTailRecAux 3 0
= sumToTailRecAux 2 3
= sumToTailRecAux 1 5
= sumToTailRecAux 0 6
= 6
*conceptually, without thunk
• The return value of each recursive call is the same as the return value of
the next recursive call
• Don’t need to save all frames on the stack; reuse the current frame for
next recursive call!
46
Running Time
• Running time of sumTo/sumToTailRec 100,000,000
Function Compiler Command Running time
sumTo ghc ~15s
sumToTailRec ghc ~18s
sumTo ghc -O2 ~5s
sumToTailRec ghc -O2 ~1s
• Lazy evaluation and tail recursion optimization affect the running time
47
Tail Recursion: Example
• Compute the factorial
fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n - 1)
• Tail recursive version
factTailRec :: Integer -> Integer
factTailRec n = factTailRecAux n 1
where
factTailRecAux :: Integer -> Integer -> Integer
factTailRecAux 0 r = r
factTailRecAux n r = factTailRecAux (n - 1) (n * r)
48
Tail Recursion: Example
• Compute the length of a list
len :: [a] -> Int
len [] = 0
len (_:xs) = 1 + len xs
• Tail recursive version
lenTailRec :: [a] -> Int
lenTailRec xs = lenTailRecAux xs 0
where
lenTailRecAux :: [a] -> Int -> Int
lenTailRecAux [] l = l
lenTailRecAux (_:xs) l = lenTailRecAux xs (l + 1)
49
