Skip to main content Link Search Menu Expand Document (external link)

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 argument x should always return the same output y
  • variables are immutable: after declaration, they cannot be modified
    • ex: f(x){ x = x + 1; return x } is not allowed!
  • 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:

  1. It doesn’t depend on any data other than its inputs to compute a result
  2. 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, then global gets incremented to 1, which changes z’s behaviour!
  • if we were to run int z = func(arg) first, then global stays at 0, and z returns 0!

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 integers
  • Integer: arbitrary-precision signed integers
    • aside: how does this work?
    • in languages like Python, we can treat numbers as arrays of Ints of a “Base 2^64” system
    • matt says, the Wikipedia article isn’t bad!
  • Bool: booleans (True or False)
  • Char: characters (like in other languages)
  • Float: 32-bit (single-precision) floating point
  • Double: 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 use tail [42..] just like [42..].
  • “but Matt”, you say, tail [42..] == [43..] hangs, and tail [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!
  • 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:

  1. One or more input lists that you want to draw from (these are called “generators”)
  2. A set of filters on the input lists (these are called “guards”)
  3. 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:

  1. (optional): type information about the function’s parameters and return value
  2. the name and parameter names
  3. 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 and smell are some type of list
  • " smells like " and " and doesn't floss." are lists of characters (recall that String = [Char]!)
  • since we can only concatenate lists of the same type, name and smell are Strings!!
  • and, the concatenation of Strings is String, so it returns a String

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:

  • taking CS 231
  • read the Learn You a Haskell chapters on IO and Monads

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 - since f 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 :)