Topics in Advanced Computing Lesson 3: Recursion / Higher order functions

1. Questions
   1. Reminders
   2. Reading
2. Finish up
3. Recursion
   1. Examples
   2. Quicksort
   3. zip / zipWith
4. Higher-order Functions
   1. Currying
   2. Partial Application
   3. Maps / filters
   4. Lambdas
   5. folds
   6. foldr
   7. foldl1 / foldr1
   8. scanl/scanr
   9. Application
   10. Composition

Questions

GH Classroom questions? Questions from last time?

Reminders

• Presentation 1 starts next week.
  • Overview of your topic. 15ish minutes?
  • Motivate it: why is this is an interesting area of research?
  • See rubric on BrightSpace
  • Volunteers?
• Problem Set 1 due next Tuesday.

Reading

• Chapter 5: Recursion
• Chapter 6: Higher-order functions

Finish up

Notes from last week that we didn’t get to:

• Type classes
• Functions
  • Pattern matching
  • As patterns
  • Guards
  • Where clause
  • Let clause
• Problem Set 1

Note: We probably won’t get through the rest of these notes in one class.

Recursion

• Defining a function in terms of itself.
• Need a base case.
• Recursively, if we can define f on smaller inputs, use it to figure out what to do on larger ones.

Examples

• maxList :: (Ord a) => [a] -> a (Hint: use the max function which takes in two parameters)
• replicate’ :: (Num i, Ord i) => i -> a -> [a]
• take’ :: (Num i, Ord i) => i -> [a] -> [a]

How do we define these recursively?

Quicksort

The quicksort algorithm is a classical $O(n \log n)$ sorting algorithm. The idea is as follows:

• Pick some element as the pivot.
• Put everything smaller than the pivot on the “left” side.
• Put everything bigger than the pivot on the “right” side.
• This puts the pivot in the correct place.
• Recursively quicksort the left and right sides.

How do we implement this in Haskell? Hint: use the head as the pivot.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = 

Hints:

• Use a let..in binding to define the left and right lists.
• Recursively quicksort those lists
• Put everything back together.

zip / zipWith

zip: take two lists and return a list of pairs.

zip [0, 1, 2] [1..]

Returns [(0,1), (1,2), (2,3)] (cuts off the infinite list!). Exercise: How would we define this using recursion / pattern matching? (Hint: base cases?)

zipWith: combination of zip and map. Take a function, two lists, and returns a list where we apply the function to both list elements.

zipWith (+) [0..10] [1..]

Returns [1,3,5,7,9,11,13,15,17,19,21].

Exercise: Can we define zipWith using zip? Can we define zipWith without using zip (recursion / pattern matching)?

Higher-order Functions

• Pass functions as arguments (fundamental to functional programming).
• Technically: multi-arg functions do this!

addNums :: Num a => a -> a -> a
addNums x y = x + y

This is called currying (named after Haskell Curry): translating a function of multiple arguments to a sequence of one-argument functions.

addNums is a function which takes in a parameter of typeclass Num, and returns another function. That returned function is one which takes in a parameter of typeclass Num and returns a value of typeclass Num.

Upshot: partial application:

addFour = addNums 4

• What? Try :t addFour, what do you get?
• Try addFour 7, what do you get?
• addNums 4: takes in parameter 4, returns a function which takes in parameter y, and returns 4 + y.

Currying

• Function application
• Multiple args = currying

Partial Application

• Examples: divByTen, etc
• zipWith’

Maps / filters

Map:

• take a function and a list and apply that function to each element of the list.
• Fundamental construct in functional programming.
• Most loops can be changed to use map instead.
• How to define it?
• Examples?

Filter: Take a predicate (a function which returns a Bool) and a list, and return the sublist of those items which the predicate evaluates to try

Example: filter (>0) [3, -1, 4, 7, -2, 0, 8] returns [3, 4, 7, 8].

Definition?

Other examples?

• Quicksort again
• Primes / twin primes
• Collatz sequences

Lambdas

• Anonymous function (if we only need to use a function once, don’t need to give it a name)
• Derived “lambda calculus”
• Use backslash \.
• Often useful with constructs like map / filter / fold

folds

Repeatedly apply a function to more and more of a list. Takes in a function, a starting value, and a list, and returns a single value.

Definition:

foldl :: (a -> b -> a)  -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

Ex: foldl (\acc x -> acc + x) 0 [1..5] is the sum function! (adds up the numbers in the list [1..5]). How?

• First: foldl f (f 0 1) [2..5], where f is the lambda.
• The lambda adds 0 and 1, so it’s now foldl f 1 [2..5]
• Next: foldl f (f 1 2) [3..5]
• foldl f 3 [3..5]
• foldl f (f 3 3) [4..5]
• foldl f 6 [4..5]
• foldl f (f 6 4) [5]
• foldl f 10 [5]
• foldl f (f 10 5) []
• foldl f 15 [] (finally we’re at the base case!)
• 15

In the prelude, in fact, sum is defined as sum = foldl (+) 0.

foldr

foldl is technically a “left-fold”. There is also a “right-fold”, foldr.

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

This is an implementation of the map function. This one takes the function f and the list, and, starting on the right, applies f to each element on the list and prepends it to the rest of the list. You could do this with foldl and ++, but : is much more efficient than ++ (why?).

(This is not how map is actually implemented! Can you think of a recursive, pattern-matching way to implement it instead?)

Lazy-evaluation:

quitZero x acc = if x == 0 then 0 else x+acc
foldr quitZero 0 [3,2,1,0,100,undefined]

What happens here? What about for foldr quitZero 0 [3,2,1,100,undefined]? Lazy evaluation!

foldl1 / foldr1

scanl/scanr

foldl / foldr but returns a list of all partially accumulated values.

Application

The ‘$’ operator is the “function application” operator. Why would we use it? It changes precedence.

f a b c binds as (((f a) b) c), ie apply f to a, then take that result and apply it to b, then apply that result to c.

f $ a b c means apply a to b, apply that result to c, and then use that result as the argument to f.

Example:

length (takeWhile (<1000) (scanl1 (+) (map sqrt[1..])))
length $ takeWhile (<1000) $ scanl1 (+) $ map sqrt[1..]

Those do the same thing, second is a bit more readable.

Composition

Using the standard prelude functions negate and abs, let’s take a list of numbers and make all of the values negative.

map \x -> negate(abs x) [5, -3, 7, -2]

Cleaner if we use the . operator for composition:

map (negate . abs) [5, -3, 7, -2]

“Compose the negate and abs functions, pass that to map”.