Lecture 02

2023-04-05 | Week 1 | edited by Ruining Ding

(originally written 2022-09-28 by Matt Wang)

Ruining here! This continues from last lecture, and covers the first 36 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)
    • C-type main() functions are forbidden
  • every function must return a value
    • C-type functions of type void are forbidden
  • 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 (Ruining will call this determinism)
  • 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++;
}

There are a few consequences resulting from these basic tenets:

  • no random numbers can be generated or used
    • since that would violate determinism
  • no input is taken in a compiled Haskell programme
    • since that would violate determinism (input will determine result produced)
  • no output is produced (aside from the final product) in a compiled Haskell programme
    • since that would not longer be pure (we are altering program state)

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. This means that it is one of the best imbodiments of functional programming design goals with minimal features from other paradigms. 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))

-- is how you declare a comment in Haskell.

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 and its type inference rules!

ghci> :t googleplex
googleplex :: Integer

Operators

Haskell supports operators you’re used to: +, -, *, /, ^, etc.

But, there’s a few caveats!

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)!

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 by index:

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; there’s also a corresponding prod

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. (You could think of this behaving similarly to when you drag a cell on Excel/Google Sheets to repeat a pattern.)

-- 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?

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 Haskell list comprehension looks like on slide 34.

Comprehensions can also use multiple input lists and guards! (As seen on slide 35.)

Hi, Ruining here. If you happen to be familiar with set-builder notation from math classes, comprehensions are similar (see section on programming languages for a side-by-side comparison).

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")]

And that’s it from Ruining and Matt! Let Ruining know if you’ve got any q’s :)