Lecture 02
2022-09-28 | Week 1 | by Matt Wang
Matt here! This continues from last lecture, and covers the first 57 slides of the Intro to FP deck. As always, please give me feedback on the notes!
Table of Contents
What is Functional Programming?
Functional programming is defined by several key tenets:
- every function must take an argument (or more than one)
- every function must return a value
- functions are pure: they should have no side effects
- side effects include changing global variables, input/output, print statements, etc.
- the most important tenet!
- calling a function
f(x)
with the same argumentx
should always return the same outputy
- variables are immutable: after declaration, they cannot be modified
- ex:
f(x){ x = x + 1; return x }
is not allowed!
- ex:
- functions are first-class - just like other values, they can be stored as variables, passed as arguments, etc.
More rigorously:, a pure function has two core properties:
- It doesn’t depend on any data other than its inputs to compute a result
- It doesn’t modify any data beyond initializing local variables required to compute its output
Sometimes, this is called a referentially transparent function.
This function is pure: it only depends on p
, and the only variable it initializes is never re-assigned (i.e., it’s just to help us with naming).
int f(int p) {
int q = 5 * p * p;
return q;
}
This function is not pure: not only does it depend on a global variable z
(not an input to the function), but it also modifies it during the computation!
int z;
int f(int p) {
return p * z++;
}
In class, we briefly mentioned that language features like closures may seem like they violate function purity. In actuality, they still do - stay tuned for more!
Functional versus Imperative
Let’s compare and contrast!
Imperative programs:
- are sequences of statements, loops, and function calls - they operate sequentially
- require changes in variable state
- as a result, multi-threading can be tricky, since there’s shared mutable state and thus race conditions
- the order of execution matters!
Functional programs have different paradigms:
- at the core, functional programs are only composition of functions - no loops, statements, etc.
- no changes in variable state are allowed
- multi-threading is trivial: there is no shared mutable state (since mutability is not allowed)!
- and, interestingly, the order of execution is not important
What does that last point mean? Under the hood, it’s all about side effects.
In an imperative language, calling functions in different orders can have side effects. Consider this example:
int global = 0;
int func1(int arg) {
return arg + global++;
}
int func2(int arg) {
return arg * global;
}
int func(int arg) {
int y = func1(arg);
int z = func2(arg);
if (z == 7)
return 0;
else return y;
}
In func
, even though the declarations of y
and z
seem to not depend on each other - calling them in different orders matters!
- if we were to run
int y = func1(arg)
first, thenglobal
gets incremented to1
, which changesz
’s behaviour! - if we were to run
int z = func(arg)
first, thenglobal
stays at0
, andz
returns0
!
Functional programming disallows code like what we just saw; so, we really could evaluate y
and z
in any order!
Intro to Haskell
Haskell is one of the first (and earliest) pure functional languages. While it has many restrictions - like requiring generally pure functions - it really lets us learn functional programming!
Our First Program
After installing Haskell, we can run the interactive interpreter with ghci
:
$ ghci
(you can exit this with Ctrl+D
)
In a separate window, let’s make a file - hypot.hs
(note the file extension)
-- hypot.hs
hypot a b = sqrt((a^2) + (b^2))
We didn’t discuss this in lecture, but --
is how you declare a comment in Haskell. Matt will add comments for all files we use!
We can now load this in ghci
:
$ ghci
GHCi, version 9.2.4: https://www.haskell.org/ghc/ :? for help
ghci> :load hypot
[1 of 1] Compiling Main ( hypot.hs, interpreted )
Ok, one module loaded.
ghci> hypot 3 4
5.0
Let’s say we update our file:
-- hypot.hs
square x = x * x
hypot a b = sqrt (square a + square b)
We can reload this file with :r
:
ghci> :r
[1 of 1] Compiling Main ( hypot.hs, interpreted )
Ok, one module loaded.
ghci> hypot 7 8
10.63014581273465
We can also define functions in the interpreter itself:
ghci> quadratic x y = 2 * x^2 + y
ghci> quadratic 3 1
19
We’ll talk more about functions later in this lecture!
The Golden Rule of Haskell Indentation
Code which is part of an expression should be indented further in than the beginning of that expression.
You must align the spacing for all items in a group.
If you don’t follow this rule, you’ll get some errors!
Examples:
mult x y =
x * y
let
x = 5
y = 6
-- note: this is rather uncommon
let x = 5
y = 6
where
x = a
y = b
where x = a
y = b
case x of
42 -> foo
-1 -> bar
if foo
then bar
else boo
Data Types in Haskell
The Type System
Haskell is a statically typed language. That means that the type of all variables and all functions can be figured out at compile time
(this is different from Python - a dynamically typed language - where types can only be determined as the program actually runs)
Haskell also has type inference: the compiler can figure out the types of most expressions without you annotating them! Neat!
(this started in functional programming, and has made its way into mainstream languages like C++’s auto
keyword)
Primitive Types
The built-in data types are:
Int
: 64-bit signed integersInteger
: arbitrary-precision signed integers- aside: how does this work?
- in languages like Python, we can treat numbers as arrays of
Int
s of a “Base2^64
” system - matt says, the Wikipedia article isn’t bad!
Bool
: booleans (True
orFalse
)Char
: characters (like in other languages)Float
: 32-bit (single-precision) floating pointDouble
: 64-bit (double-precision) floating point
Let’s see a live code example of some primitive types:
-- example.hs
-- Defining an Int
nerds = 150 :: Int
-- Defining an Integer
googleplex = 10^100 :: Integer
-- Defining a Float
rootbeer = 3.14159 :: Float
-- Defining a Bool
carey_has_hair = False :: Bool
When we enter just the name of a variable, ghci
will print its value for us:
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> googleplex
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
:t
tells us the type of the expression passed to it. This is really, really useful: it’s a helpful tool to learn more about the language!
ghci> :t googleplex
googleplex :: Integer
Operators
Haskell supports operators you’re used to: +
, -
, *
, /
, ^
, etc.
But, there’s a few gotchas!
This works well:
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> 42 + nerds * 10
1542
In Haskell, the /
division operator does not work on Integers! (why might that be - there’s a good functional reason!)
ghci> nerds / 10
<interactive>:3:7: error:
• No instance for (Fractional Int) arising from a use of ‘/’
• In the expression: nerds / 10
In an equation for ‘it’: it = nerds / 10
You must use `div`
instead.
ghci> nerds `div` 10
15
However, /
works on floats just fine:
ghci> rootbeer / 10
0.314159
To make numbers negative, you need to add a parentheses: this makes -
a unary operator:
ghci> nerds + (-1)
149
There is prefix notation for infix operators:
ghci> (+) rootbeer 1.0
4.14159
Boolean operators generally work like how you’d expect!
ghci> nerds > 100 && not carey_has_hair
True
Composite Types
We’ll dive into three composite types:
- a
Tuple
is a fixed-size collection of values; each value can be any type. - a
List
is a sequence of values; each value must be the same type. - a
String
is a list of characters!
Let’s see some examples in action.
Tuples
Tuples are great for associating values together, or having a function “return multiple values”.
--- examples.hs
-- A Tuple for a student's score
grade = ("Sergey", 97)
-- A job posting: title, wage, hrs/wk
job = ("Chef", 35.5, 40)
-- A tuple with tuples, lists & ints
whoa = ((1,"two"),['a','b','c'], 17)
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> grade
("Sergey",97)
ghci> fst grade
"Sergey"
ghci> snd grade
97
fst
and snd
are only defined for tuples with two elements! They do not work for tuples with 3 or more elements - you’d use pattern matching instead (coming next lecture)!
We didn’t have time to touch on this in lecture, but Matt wants to add - what is the type of the Tuple? Let’s ask ghci:
ghci> :t grade
grade :: (String, Integer)
Interesting! Note that the type of the tuple encodes:
- the number of elements in the tuple
- the types of each element in the tuple
This means, for example, that you can’t have a list of any two tuples - they must all be tuples of the same size and types!
Lists
Lists are the building block of functional programming. Note that they are not arrays: they have O(N)
access and no pre-defined size.
--- examples.hs
-- A List of primes
primes :: [Int]
primes = [1,2,3,5,7,11,13]
-- A List of jobs
jobs = ["SWE","Chef","Writer"]
-- A List of Lists
lol = [[1,2,3],[4,5],[6,7,8,9]]
-- A list of tuples
lot = [("foo",1),("bar",2),("boo",3)]
-- An empty list
mt = []
The most commonly used list functions are head
and tail
; head
returns the first item of the list, and tail
returns a list of the rest of the items!
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> head primes
1
ghci> tail primes
[2,3,5,7,11,13]
Here are some other handly simple list functions.
Is a list empty?
ghci> null []
True
Get the list’s length:
ghci> length primes
7
take
and drop
are convenient ways to access slices of a list.
ghci> take 3 primes
[1,2,3]
ghci> drop 4 primes
[7,11,13]
!!
gives you random access:
ghci> jobs !! 2
"Writer"
elem
tells you if an item is in a list:
ghci> elem "Chef" jobs
True
sum
adds up the entire list
ghci> sum primes
42
or
performs boolean or
over the list; there’s also a corresponding and
ghci> or [True, False, False]
True
ghci> and [True, False, False]
False
zip
creates tuples out of two lists. This is the same as python’s zip
!
ghci> zip [10,20,30] jobs
[(10,"SWE"),(20,"Chef"),(30,"Writer")]
Like the name may imply, Haskell lists are implemented as singly-linked lists. List operations are implemented recursively! This has performance impacts, since there is no linear random access!
Strings
You’ve seen Strings before!
-- examples.hs
-- Defining a String w/explicit type
truth :: String
truth = "USC sucks"
-- Defining a string w/o a type
lies = "USC kids are smart"
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> truth
"USC sucks"
We can perform concatenation with ++
:
ghci> "I think " ++ truth
"I think USC sucks"
Like many languages, under-the-hood, String ~= [Char]
(Strings are really just a character list)! This means we can use head
, tail
, and check for equality:
ghci> :t truth
truth :: String
ghci> head truth
'U'
ghci> tail truth
"SC sucks"
ghci> "hey" == ['h','e','y']
True
List Processing
Lists may seem boring, but they form the foundation of functional programming (other than, well, functions). In particular, functional list manipulation has made its way into almost every mainstream programming language!
Creating Lists: Concatenate and Cons
We can make a list using the :
“cons” operator to add an item to the front, or the ++
concatenation operator to join two lists.
-- examples.hs
-- A List of primes
primes = [1,2,3,5,7,11,13]
-- A bigger List of primes
more_primes = primes ++ [17,19]
-- A List of jobs
jobs = ["SWE","Chef","Writer"]
-- A bigger list of jobs
more_jobs = "Prof" : jobs
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> more_primes
[1,2,3,5,7,11,13,17,19]
ghci> more_jobs
["Prof","SWE","Chef","Writer"]
We can also create lists from scratch - but don’t forget the trailing : []
!
ghci> 1 : []
[1]
ghci> 1 : 3 : []
[1,3]
ghci> (10,20) : (30,40) : []
[(10,20),(30,40)]
Creating Lists: Ranges
Ranges are a neat feature in Haskell that let us easily create lists.
-- example.hs
-- All #s between 1 and 10, inclusive
one_to_ten = [1..10]
-- Odd #s between 1 and 10
oddities = [1,3..10]
-- An infinite list from 42 onward!
whole_lotta_numbers = [42..]
-- An infinite cycle of 1,3,5,1,3,5,…
tricycle = cycle [1,3,5]
ghci> :load examples
[1 of 1] Compiling Main ( examples.hs, interpreted )
Ok, one module loaded.
ghci> one_to_ten
[1,2,3,4,5,6,7,8,9,10]
ghci> oddities
[1,3,5,7,9]
ghci> take 5 whole_lotta_numbers
[42,43,44,45,46]
ghci> take 10 tricycle
[1,3,5,1,3,5,1,3,5,1]
Woah … what’s going on with infinite lists? That can’t possibly work, right?
Matt says: I’ve added a bit more to this section than what we covered in lecture, since we didn’t have a chance to answer all the questions!
Well … it does! In particular, this goes back to Haskell being lazily-evaluated. Haskell won’t generate list items from a range until they’re needed: so, if you never ask for list element #1000 out of the infinite list, Haskell won’t care! In other words, none of the list is initialized when it’s initially declared.
You may then ask some questions:
- can you take the
tail
of an infinite list?- yes, you can! for example,
tail [42..]
is the same as[43..]
. You can usetail [42..]
just like[42..]
.
- yes, you can! for example,
- “but Matt”, you say,
tail [42..] == [43..]
hangs, andtail [42..]
just keeps on printing numbers. What’s up with that?- well, when
ghci
returns a value, it calls a “print function” on it; the print function for lists keeps on printing until the list is empty. - so, when you type in
tail [42..]
, Haskell will keep printing until the list is empty, which is … never. Hence, wall of text! - on the contrary,
tail [42..] == [43..]
hangs because of the implementation of the==
operator, which compares heads until the list is empty. - since this never happens, the program doesn’t terminate!
- well, when
- what is the
length
of an infinite list?- try it :)
Be careful when trying it! In particular, Haskell (and all programming languages) cannot always tell if your program goes into an infinite loop. Have your Ctrl+C
ready!
List Comprehensions
The Idea
List comprehensions are a compact yet extraordinarily powerful syntax to create lists.
Semiformally, here’s a definition:
A list comprehension is a F.P. construct that lets you easily create a new list based on one or more existing lists. With a list comprehension, you specify the following inputs:
- One or more input lists that you want to draw from (these are called “generators”)
- A set of filters on the input lists (these are called “guards”)
- A transformation applied to the inputs before items are added to the output list.
Carey’s created this animation that maps some Python-like pseudocode into what a Haskel list comprehension looks like:
Matt’s going to add an animation here soon :)
Comprehensions can also use multiple input lists and guards!
Matt’s going to add an animation here soon :)
Simple Examples
Let’s walk through the simple examples:
-- comp.hs
-- Generate squares of 2 thru 7
squares = [x^2 | x <- [2..7]]
-- Generate products of two lists
prods = [x*y | x <- [3,7], y <- [2,4,6]]
-- Generate combinations of strings
nouns = ["party","exam","studying"]
adjs = ["lit","brutal","chill"]
combos = [adj ++ " " ++ noun |
adj <- adjs, noun <- nouns]
-- Generate combinations of tuples
menu = [(oz,flavor) |
oz <- [4,6],
flavor <- ["Choc","Earwax","Booger"]]
ghci> :load comp.hs
[1 of 1] Compiling Main ( comp.hs, interpreted )
Ok, one module loaded.
ghci> squares
[4,9,16,25,36,49]
ghci> prods
[6,12,18,14,28,42]
ghci> combos
["lit party","lit exam","lit studying","brutal party","brutal exam","brutal studying","chill party","chill exam","chill studying"]
ghci> menu
[(4,"Choc"),(4,"Earwax"),(4,"Booger"),(6,"Choc"),(6,"Earwax"),(6,"Booger")]
Advanced Examples
Here are two comprehensions that will come back to us very soon:
-- comp.hs
-- What is pass_fail?
mt_scores = [78,52,87,32,70,71]
pass_fail = [ if s > 70 then "Pass"
else "Fail" |
s <- mt_scores]
-- What is count?
count = sum [if s > 70 then 1 else 0 |
s <- mt_scores]
If you’ve seen map and reduce before, these should look familiar 🤔
ghci> :load comp
[1 of 1] Compiling Main ( comp.hs, interpreted )
Ok, one module loaded.
ghci> pass_fail
["Pass","Fail","Pass","Fail","Fail","Pass"]
ghci> count
3
And some more ones that illustrate just how compact comprehensions are:
-- Generate first 5 #s divisible by 29
-- between 1000 and infinity
div_by_29 = take 5 [x | x <- [1000..],
(mod x 29) == 0]
-- Extract all non-uppercase chars
lies = "nerds EAT rockS!"
truth = [ c | c <- lies,
not (elem c ['A'..'Z'])]
-- Generate right triangles
right_triangle_tuples = [ (a,b,c) |
a <- [1..10], b <- [a..10], c <- [b..10],
a^2+b^2==c^2 ]
The last tuple has three input lists, each of which depend on the previous one! This is called a dependent generator. In this case, it helps us avoid duplicates; in general, it allows us to create lists on the fly!
ghci> :load comp
[1 of 1] Compiling Main ( comp.hs, interpreted )
Ok, one module loaded.
ghci> div_by_29
[1015,1044,1073,1102,1131]
ghci> truth
"nerds rock!"
ghci> right_triangle_tuples
[(3,4,5),(6,8,10)]
Someone in class asked if you can nest list comprehensions. Since they just return a list, the answer is yes!! Just give it a shot!
Influencer Alert!!
In Matt’s opinion, this is one of the best parts of the class.
Comprehensions have been adopted by several notable programming languages, like Python, C# and R (used in statistical analysis). Here are two examples.
In Python, where you’re most likely to have seen them:
nums = range(1,11) # range ... interesting 🤔🤔🤔
# produces [4, 8, 12, 16, 20]
twox_evens = [2*x for x in nums
if x % 2 == 0]
And in C#, where they just dropped all the punctuation!
IEnumerable<int> nums =
Enumerable.Range(0, 10);
// produces [4, 8, 12, 16, 20]
var twox_evens = from x in nums
where x % 2 == 0 select 2*x;
Functions
Our First Haskell Function
Haskell functions have three core components:
- (optional): type information about the function’s parameters and return value
- the name and parameter names
- an expression that defines the function’s behaviour
This is how we may define an insulting function in an imperative language:
String insult(String name, String smell) {
String s = name + " smells like " +
smell + " and doesn't floss.";
return s;
}
Here’s how we’d define the same language in Haskell
insult :: String -> String -> String
insult name smell =
name ++ " smells like " ++ smell ++ " and doesn't floss."
Some things to note:
- there’s no explicit
return
statement since the right-hand side of a function is what it returns! - by convention, spaces and indentation is used to define code blocks; no braces necessary (think Python)
String -> String -> String
may seem strange - it seems like there’s no difference between parameters and return types. We’ll talk about this later when we discuss currying.
Multiline Declarations
In class, Carey said that ghci does not allow multi-line functions. This is true if you just hit the enter key. However, you can use :{
and :}
to “capture” multiple lines. Here’s an example:
ghci> :{
ghci| insult name smell =
ghci| name ++
ghci| " smells like " ++
ghci| smell ++
ghci| " and doesn't floss."
ghci| :}
ghci> insult "carey" "cheese"
"carey smells like cheese and doesn't floss."
You still need to use spaces and indentation, so watch out for that!
Optional Type Declaration
Type declaration is optional because of Haskell’s type inference! How does it work?
insult :: String -> String -> String
insult name smell =
name ++ " smells like " ++ smell ++ " and doesn't floss."
- we can only concatenate lists, so we know
name
andsmell
are some type of list " smells like "
and" and doesn't floss."
are lists of characters (recall thatString = [Char]
!)- since we can only concatenate lists of the same type,
name
andsmell
areString
s!! - and, the concatenation of
String
s isString
, so it returns aString
So … why would we even use type declarations? Unlike who we’re insulting, it’s good hygiene (and, best practice)!
- type declarations can provide better compiler warnings and errors
- type declarations make your code easier to read
- arguably the most important trait in software
- the person reading it may be you six months later!
So, we recommend that you annotate your functions - or at least, the user-facing/top-level ones!
Main Functions and (avoiding) Monads
This is intentionally hand-wavy. We won’t be covering monads or impure FP much in this class.
What we haven’t talked about yet is the main function - in other words, how can we have Haskell run a function when we open a file?
(and, while we’re at it, how can we get user input - which is a side effect)
To do it, we’ll create a function called main
, and annotate it with the IO()
“type” (really - a system and monad). We then add this strange do
block, and write what seems like imperative code:
-- insult.hs
insult :: String -> String -> String
insult name smell =
name ++ " smells like " ++ smell ++ " and doesn't floss."
main::IO()
main = do
putStr "What is your name? "
name <- getLine
putStrLn (insult name "unwashed dog")
We can then call our main
function and get some input.
ghci> :load insult
[1 of 1] Compiling Main ( insult.hs, interpreted )
Ok, one module loaded.
ghci> main
What is your name? Carey
Carey smells like unwashed dog and doesn't floss.
Is this handwavy? Yes! IO (and impure FP) is not a focus for this class, so we won’t spend too much on it. If you’re interested, we suggest:
More Examples!
Let’s see some other examples!
A simpe comparison function:
isBigger :: Double -> Double
isBigger a b = a > b
A function on a list:
average :: [Double] -> Double
average list =
(sum list) / fromIntegral (length list)
In class, Carey mentioned that fromIntegral
is used to cast the value of length
to be divisible, and said it maps from Integral -> Double
. This is mostly true, though it’s actually more powerful than that - to see why, try :t fromIntegral
!
This last example showcases the power of Haskell’s type system:
get_last_item :: [any_type] -> any_type
get_last_item lst =
head (reverse lst)
This function works for a list of any type! So, Haskell doesn’t care what type it is. The any_type
is a type variable, which we can think of as a generic or template type. We’ll refine this notion in a later lecture.
What’s cool is that we didn’t have to do anything special - it just works out of the box! And, we didn’t even need to tell Haskell that it’s generic: the type system figured it out by itself!
Calling Functions
In class, we went over a brain teaser. With:
f :: Int -> Int
f x = x^2
g :: Int -> Int
g x = 3*x
What do the following two lines do?
y = f g 2
z = f 5 * 10
Well, it turns out:
y = f g 2
is a syntax error!- this is because Haskell evaluates functions from left to right
- so,
f g 2
is the same as((f g) 2)
, which doesn’t make sense - sincef
doesn’t operate on functions
f 5 * 10 = 250
- this is because in Haskell, functions have higher precedence than operators, so they’re always evaluated first
-- We want to compute f(g(x))
compute_f_of_g x = f (g x)
-- We want to compute f ( x * 10)
compute_f_of_x_times_ten x = f (x * 10)
And that’s it from Matt! Let him know if you’ve got any q’s :)