Functional Programming

Functional Programming

Functional programming is one type of declarative programming.

In functional programs, it still feels like you're giving explicit instructions, but the language/​compiler has more freedom in interpreting details.

Functional Programming

Start by thinking of imperative programming, but…

• There is no state (global variables, etc.).
• No variables at all can be stored.
• No variables means no loops (because we need variables as for loop counters or while conditions).

Functional Programming

How can we get anything done without variables? The emphasis is on evaluating calculations, not executing steps.

We still get function arguments. e.g. x is a function argument, not a variable in these:

def half_of(x):
    return x/2

double half_of(double x) {
  return x/2;
}

half_of x = x/2

Functional Programming

Recursion can take the place of loops.

What we express is calculation we need the result of instead of follow these steps. That is what gives the compiler more freedom.

Having no variables means (should mean?) easier debugging: results of a function are determined entirely by its arguments.

Haskell

Haskell is a functional programming language.

It's very functional: purely functional. It doesn't allow you to sneak imperative tricks in.

Haskell

Some other functional languages allow some imperative things to happen (Lisp, Scheme, OCaml, Erlang). They are arguably more practical, but [I claim] not as good at helping you learn functional style programming.

So, we're using Haskell.

Haskell

We will use GHC (the Glasgow Haskell Compiler) as our compiler. It's the standard toolchain for Haskell.

Haskell

Also, it includes the GHCi interactive environment where you can test expressions/​code, as well as interact with programs/​modules.

Prelude> 2-4
-2
Prelude> 2*3 /= 6
False
Prelude> reverse [2,3,4,5]
[5,4,3,2]

Haskell

To load code from a .hs file, use :l:

Prelude> :l mycode.hs
[1 of 1] Compiling Main            ( mycode.hs, interpreted )
Ok, modules loaded: Main.
*Main>

To reload changes to the .hs file, use :r:

*Main> :r
Ok, modules loaded: Main.

Haskell Basics

Basic data types (incomplete):

• numbers: 4, 6.3, (-4)
• strings: "abc", "6.3"
• lists: [1, 2, 3, 4], ["abc", "def"]
• boolean: True, False

Haskell Basics

Numeric expressions work like you probably expect:

Haskell Basics

… and boolean expressions:

Haskell Basics

One basic list operation: concatenate:

Haskell Basics

Another: cons (short for construct):

Note: The (:) operator has a list element on the left, and a list on the right. The element is prepended to the start of the list. The operator is right-associative, so the last two examples are equivalent.

Haskell Basics

Characters are indicated with single quotes and strings with double quotes (like C):

Haskell Basics

Strings are just shorthand for lists of characters (like C):

Haskell Basics

Haskell lists are conceptually singly-linked lists: imagine a head with pointer to the rest of the list. *

Not only does 1:2:[] == [1,2] but you could think of the syntax [1,2] as just a shorthand for 1:2:[].

Haskell Functions

Functions are (obviously) important in functional languages. They are the primary unit of code (as opposed to classes, statements, etc).

Calling functions in Haskell looks different than you might expect: no parens around arguments; just spaces separate arguments. It may take some getting used to.

Haskell Functions

Haskell Functions

Haskell knows what is a function and how many arguments it takes: it expects the right number of arguments to follow (except when it doesn't: more later).

So, if f is a two-argument function, this is sensible:

f 1 2

… and these are incomplete and have and extra argument, respectively (but more later):

f 1
f 1 2 3

Haskell Functions

Defining functions (at least for simple expressions) is easy (filename functions1.hs):

half_of x = x/2
isBig a = a > 100
listify x y = [x, y]

And then you can use them:

Prelude> :l functions1.hs
[1 of 1] Compiling Main        ( functions1.hs, interpreted )
Ok, modules loaded: Main.
*Main> half_of 5
2.5
*Main> isBig 123
True
*Main> listify 'a' 'b'
"ab"

Pattern Matching

A simple expression doesn't let us get much logic into a function.

The most Haskell-ish way to express a condition is pattern matching where we can express if the arguments look like this, the result is….

Pattern Matching

For example, a function for a logical and:

myAnd False _ = False
myAnd True a = a

Things happening there:

• The first definition is used if the first argument is False.
• The _ matches any value (but ignores it).
• The second is used if the first argument is True
• The named argument matches anything captures its value.

Pattern Matching

The behaviour is a logical and operation:

*Main> :r
Ok, modules loaded: Main.
*Main> myAnd True True
True
*Main> myAnd True False
False
*Main> myAnd False True
False
*Main> myAnd False False
False

Pattern Matching

Rule: the first definition that matches applies.

isZero 0 = True
isZero _ = False

*Main> isZero 0
True
*Main> isZero 1
False

Pattern Matching

Recursion works and we can match a cons pattern (first and rest of a list). We could define something like:

myLength [] = 0
myLength (_:xs) = 1 + myLength xs

*Main> myLength [1, 2, 3]
3
*Main> myLength "Hello World"
11

Pattern Matching

The cons pattern is very common for recursing over a list.

processList [] = …                        -- base case
processList (x:xs) = … processList xs …   -- recursive case

Pattern Matching

Another example: are two lists equal?

listEqual [] [] = True
listEqual (x:xs) (y:ys) = x == y && listEqual xs ys

*Main> listEqual [1,2,3] [1,2,3]
True
*Main> listEqual [1,2,3] [1,2,4]
False

Problem?

Pattern Matching

The patterns in the function definition miss the case of non-equal length lists.

*Main> listEqual [1,2,3] [1,2,3,4]
*** Exception: functions1.hs:(16,1)-(17,51): Non-exhaustive patterns in function listEqual

We can add these cases to cover those inputs:

listEqual [] (_:_) = False
listEqual (_:_) [] = False

(or listEqual _ _ = False and use the first-match-only behaviour.)

Pattern Matching

We can match whatever patterns are necessary to solve our problem.

e.g. Does a list have even length? We can do that by matching two elements from the start of a list and recursing.

hasEvenLength [] = True     -- base case: length 0 is even
hasEvenLength [_] = False   -- base case: length 1 is odd
hasEvenLength (_:_:rest) = hasEvenLength rest

Pattern Matching

Rules for pattern matching:

• plain identifier (argument name, like x): matches anything and captures the value.
• _: matches anything but we don't need the value.
• literal value (like 1, [], etc): matches if equal.

Pattern Matching

Matching lists:

• []: matches an empty list.
• [a]: matches a one-element list.
• (a:tail): matches a list with at least one element. First is a, rest of list is tail (and could be an empty list).
• (a:b:tail): matches a list with at least two elements. First is a, second is b, remainder of list is tail (could be empty).

Pattern Matching

For example, if we have the pattern:

(a:b:c)

… then these lists match as follows:

Conditionals

Pattern matching produces nice-looking code, but it can't do everything. There are a few ways to write more flexible conditional code.

There is an if/else expression, but I'm banning it: it's not Haskell-ish, and often used by students to avoid learning the functional style.

Conditionals

Much nicer: guarded expressions

mySignum x
  | x>0         = 1
  | x<0         = -1
  | otherwise   = 0

Analgous to the mathematical function:

Conditionals

There is also a case expression to give multiple alternatives in a convenient way:

word n = case n of
  1 -> "one"
  2 -> "two"
  3 -> "three"
  _ -> "???"

Conditionals

The case is an expression: it can be used just like any other Haskell expression:

wordWithX n = (case n of
  1 -> "one"
  2 -> "two"
  3 -> "three"
  _ -> "???") ++ "X"

Conditionals

All of the values for the cases are patterns, just like function definitions:

describeList lst = "The list is " ++ case lst of
  _:_:_:_:_  -> "fairly long"     --  >= 4 elements
  _:_        -> "short"           --  >= 1 element
  []         -> "empty"

*Main> describeList []
"The list is empty"
*Main> describeList [3,4]
"The list is short"
*Main> describeList "hello"
"The list is fairly long"

Repetition

Since there are no variables, we can't write loops like we're used to in other languages.

Repetition

Loops (as we think of them) need a variable (i here) that determines when the loop ends: no variable = no way to end the loop.

for ( int i=0; i<10; i++ ) {
    cout << i << '\n';
}

int i = 100;
while ( i>1 ) {
    cout << i << '\n';
    i /= 2;
}

Repetition

We have recursion, and know (I hope) that recursion can be used instead of any loops.

myLength [] = 0
myLength (_:xs) = 1 + myLength xs

Recursion is going to be the biggest way we repeat logic: time to get comfortable with it.

Repetition

With recursions and conditions as we have them, the language is Turing complete. Everything else is just convenience.

We will also have implicit loops [my term]: an expression that implies repeated application of a function…

List Comprehensions

Recall the set builder notation from math:

It's a very efficient notation to describe a set. Haskell has a very similar notation to build a list…

List Comprehensions

A list comprehension are a syntax in Haskell to describe a list, similar to the set builder notation.

[Python borrowed list comprehensions: you may have seen them there. Or LINQ in .NET is like list comprehensions and SQL had a baby.]

List Comprehensions

First part: generators, like \(x\in\mathbb{N}\) in the set notation. The generator creates the source values.

Use the <- operator with an existing list on the right. e.g.

x <- [1,2,3,4]

List Comprehensions

The generator can be used with any expression to build a list. Each generator value is used as an argument to the expression.

Prelude> [ x^2+1 | x <- [1, 2, 3, 4, 5, 6, 7] ]
[2,5,10,17,26,37,50]
Prelude> [ succ c | c <- "hello" ]
"ifmmp"

List Comprehensions

You can use more than one generator in a comprehension: every pair of values is produced.

Prelude> [ 10*x + y | x <- [3,4,5], y <- [6,7,8,9]]
[36,37,38,39,46,47,48,49,56,57,58,59]

List Comprehensions

A second piece we can add: guards, like \(x \text{ is even}\) in the set notation.

A guard is a boolean expression that decides if a value should be included in the result or not.

Prelude> [ x^2+1 | x <- [1, 2, 3, 4, 5, 6, 7] ]
[2,5,10,17,26,37,50]
Prelude> [ x^2+1 | x <- [1, 2, 3, 4, 5, 6, 7], even x ]
[5,17,37]

List Comprehensions

List comprehensions are often used with the .. shorthand for arithmetic sequences.

List Comprehensions

The .. can be used anywhere you need a list, not just in a comprehension. But it makes it easy to write a list comprehension that builds a list of arbitrary size:

firstSquares n = [ i*i | i <- [1..n] ]
firstEvenSquares n = [ i*i | i <- [1..n], even i]
firstEvenSquares' n = [ i*i | i <- [2,4..n]]

*Main> firstSquares 10
[1,4,9,16,25,36,49,64,81,100]
*Main> firstEvenSquares 10
[4,16,36,64,100]
*Main> firstEvenSquares' 10
[4,16,36,64,100]

List Comprehensions

The notation we have lets us be very expressive in Haskell.

qs [] = []
qs (x:xs) = smaller ++ [x] ++ larger
  where smaller = qs [a | a<-xs, a<=x]
        larger = qs [a | a<-xs, a>x]

… a Quicksort in four lines.

Let and Where

It's easy to create unreadable code in Haskell: any function that does anything interesting probably requires a long expression. Just because it works doesn't mean it's good code.

The let and where clauses let you alias values so you can use them by-name or multiple times.

Let and Where

e.g. in the definition of the Quicksort, the where let me (1) turn what could have been one long, ugly expression into three short ones; (2) give the sub-expressions names so they are easier to understand.

qs [] = []
qs (x:xs) = smaller ++ [x] ++ larger
  where smaller = qs [a | a<-xs, a<=x]
        larger = qs [a | a<-xs, a>x]

Let and Where

The let name=… in … structure creates an expression and can be used anywhere you can use any other expression.

Prelude> let x=4 in x*2
8
Prelude> (let x=4 in x*2) ^ 3
512

Let and Where

But it's more useful to simplify things in longer definitions:

qs' [] = []
qs' (x:xs) =
  let smaller = qs' [a | a<-xs, a<=x]
      larger = qs' [a | a<-xs, a>x]
  in smaller ++ [x] ++ larger

Let and Where

The where must be part of a function definition (or similar block):

somePowers x = [x, sq x, sq (sq x)]
  where sq n = n*n

In either case, multiple sub-expressions can be defined, separated by linebreak (or semicolon).

Let and Where

The choice between let and where is often one of style: does it make more sense to define the sub-expressions before or after the main expression? It will depend on the context. Do the more readable thing.

qs (x:xs) = smaller ++ [x] ++ larger
  where smaller = qs [a | a<-xs, a<=x]
        larger = qs [a | a<-xs, a>x]

qs' (x:xs) =
  let smaller = qs' [a | a<-xs, a<=x]
      larger = qs' [a | a<-xs, a>x]
  in smaller ++ [x] ++ larger

Let and Where

You should use let or where if your code is getting complicated. Break up big expressions; give the sub-parts meaningful names.

[If I see a single expression more than one moderate-length line, I'm going to refuse to help you. The TAs should take off marks for coding style too.]

Recursion

The idea of recursion shouldn't be new. But maybe a little review wouldn't hurt…

Function definitions will have two cases (which may be sub-divided further).

Base case: small case(s) where the result is obvious/​easy.

Recursion

Recursive case: you find a smaller subproblem (i.e. closer to the base case), another version of the same problem that will help you find the real solution.

Make a recursive call to solve the subproblem.

Use that sub-result to create the real result.

Recursion

e.g. Argument n becomes n-1 or n/2. Base case is 0 or 1.

e.g. Argument (x:xs) becomes xs. Base case is [], or occasionally [x].

Recursion

An example: calculate powers (\(x^y\) for \(x, y\) integers, \(y\ge 0\)).

myPower _ 0 = 1
myPower x y = x * myPower x (y-1)

This uses the facts \(x^0=1\) and \(x^y = x\cdot x^{y-1}\).

Recursion

Like with any other iteration, we have the opportunity to be more or less efficient.

myPower' x y
  | y==0      = 1
  | even y    = half*half
  | odd y     = x*half*half
  where half = myPower' x (div y 2)

This uses the facts \(x^0=1\) and \(x^y = {(x^{y/2})}^2\) (and fixes integer division rounding).

Recursion

Running times?

myPower _ 0 = 1
myPower x y = x * myPower x (y-1)

myPower' x y
  | y==0      = 1
  | even y    = half*half
  | odd y     = x*half*half
  where half = myPower' x (div y 2)

myPower is \(O(y)\) and myPower' is \(O(\log y)\).

Recursion

More recursion: Hutton chapter 6 (especially §6.6) and Learn you a Haskell chapter 5.

Isn't Recursion Slow?

Many people think that recursion is slow(er than loops). With some languages/​tools, it is.

It is also limited by the implementation in some languages: can only recurse to a certain modest depth. (e.g. Python's sys.getrecursionlimit seems to give 3000 by default.)

But limitations in some tools don't imply any conceptual problem.

Isn't Recursion Slow?

Counter argument #1: Don't worry about it.

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Don Knuth or maybe Tony Hoare

If a recursive implementation is more readable or expressive, then it's better than fast code, except maybe in the most-called few percent. So write the readable recursive version and move on.

Isn't Recursion Slow?

Counter argument #2: Clever algorithms beat clever code. Write a good algorithm in the most readable way.

e.g. compare how long these take:

*Main> myPower 1 5000000
1
*Main> myPower' 1 5000000
1

No amount of clever coding is going to save myPower.

Isn't Recursion Slow?

Counter argument #3: maybe the problem isn't the code, it's the compiler.

The thing that usually slows recursion (compared to loops) is building the call stack. Let's explore that…

Isn't Recursion Slow?

The call stack keeps track of where to return to when the (recursive) function calls exit. If you recurse 1000 levels deep, the call stack needs 1000 entries built/destroyed.

Isn't Recursion Slow?

All of the expressions must be stored in-progress (on the call stack, as stack frames) so the recursion can be unwound once recursive calls start returning actual values. That's expensive if the recursion is deep.

Tail Recursion

Theory: recursion is slower than loops because we have to maintain the call stack. Therefore, if we could get rid of the call stack, it would be faster. Right?

Tail Recursion

Consider this (slightly stupid) function that adds two (positive) integers:

stupidAdder x 0 = x
stupidAdder x y = stupidAdder (x+1) (y-1)

*Main> stupidAdder 16 3
19
*Main> stupidAdder (-5) 100
95

Again, based on some math we know:

Tail Recursion

When we call stupidAdder 16 3, this happens:

The final answer is there in the base case. Why bother keeping the call stack?

Tail Recursion

We didn't need the call stack in that example because the result is the recursive call by itself, not some expression including the recursive result and other stuff.

e.g. not this:

stupidAdder' x y = 1 + stupidAdder' x (y-1)

Tail Recursion

If we can write recursive functions like this, the compiler could decide it's okay to throw away the call stack. If it does, our code should be faster.

These are called tail recursive functions: the very last thing that happens in the function (the tail) is a function call.

In general, we can talk about a tail call: any function that ends by returning another function call by itself.

Tail Recursion

Haskell will eliminate tail calls if compiler optimization is turned on. This can only be done if the code is compiled outside GHCi.

$ ulimit -v 4194304   # limit to 4GB memory
$ ghc -O2 tailrec.hs  # non-tail recursive stupidAdder
$ time ./tailrec
tailrec: out of memory
real	0m5.298s
user	0m4.565s
sys	0m0.733s
$ ghc -O2 tailrec.hs  # tail recursive stupidAdder
$ time ./tailrec
500000001
real	0m0.443s
user	0m0.438s
sys	0m0.005s

Creating Tail Recursion

Creating a tail recursive function generally requires passing a partial result as an argument: instead of the call stack keeping track of what you're calculating, you have to do it yourself.

The argument to hold the partial result is the accumulator. In stupidAdder, the first argument was implicitly doing this.

Creating Tail Recursion

Let's look back at myPower:

myPower _ 0 = 1
myPower x y = x * myPower x (y-1)

We'll introduce an accumulator argument a, and make the rule that this returns \(a\cdot x^y\):

myPowerTailRec a x y

Creating Tail Recursion

The base case: \(a\cdot x^0 = a\)

myPowerTailRec a _ 0 = a

The recursive case: \(a\cdot x^y = (a\cdot x) \cdot x^{y-1}\)

myPowerTailRec a x y = myPowerTailRec (x*a) x (y-1)

Basically: the call stack used to remember x *. Now we do the work in the accumulator.

Creating Tail Recursion

Running time to find \(1^{400000000}\) with these functions compiled with ghc -O2:

• 8.0 s with myPower;
• 0.3 s with myPowerTailRec.

… but 0.005 s with the logarithmic running time myPower'.

Creating Tail Recursion

The same trick with a factorial function:

factorial 0 = 1
factorial n = n * factorial (n-1)

Use the rule \(a \cdot n! = (n\cdot a) \cdot (n-1)!\) and this becomes:

factorial' n = factorialTailRec 1 n
    where
    factorialTailRec a 0 = a
    factorialTailRec a n = factorialTailRec (n*a) (n-1)

The where lets us hide implementation junk from the caller.

Creating Tail Recursion

Is tail recursion worth the effort? Not usually: it's a premature optimization.

Never if the compiler doesn't do tail-call optimization. (e.g. the usual compilers for Python and Java don't.)

But if you have a function that takes a long time because of overhead of maintaining the call stack, then maybe. (But consider how weirdly artificial I had to be to create myPower where it was noticable.)

Aside: C and Tail Recursion

Modern C compilers can optimize tail calls, and construct the accumulator (in simple cases, at least).

Have a look at an example. Compare the assembly code generated by gcc -O0 and gcc -O2.

This can speed up recursive implementations, and avoid limits on recursion depth.

Aside: C and Tail Recursion

Implications of the assembly the compilers generate…

• Calling myPower(1, 1000000) will probably cause a stack overflow with -O0, but succeed with -O2.
• A recursive case more complicated than x * might get transformed to the tail call and non-recusive implementation. Maybe not.
• The compiler isn't actually implementing the logic you wrote: it's producing output with the same results as the logic you wrote.