Higher Order Functions
CS 345
Lecture 6
In writing (for example) negate-all functionally,
what do we do differently from an imperative style?
We avoid the mutation of state…
Do we iterate with a for loop?
No, we use recursion
Do we use an array?
No, we use a list (recursive data structure)
Do we mutate values in our list?
No, we return a new list containing new values
How do we create a new list?
“cons” items, ultimately onto an empty list
Last session:
Higher Order Functions
The functional programming experience
Higher Order Functions, defined
Functions that take functions as arguments:
(define (apply f ls)
(if (empty? ls)
‘()
(cons (f (car ls)) (apply f (cdr ls)))))
Functions that return other functions:
(define (discount br %)
(lambda (price)
(if (>= price br)
(* % price)
price)))
Why offer higher order functions in a programming language?
1) Why take functions as arguments?
First, let’s think about what a for loop lets you do, imperatively:
int[] myArray = {10, 11, 12, 13, 14};
for (int i= 0; i < myArray.length; i++) { myArray[i] = myArray[i] * 2; } A for loop lets you apply some operation, repeatedly. 1) Why take functions as arguments? Now think about how to accomplish this task recursively, and with no state mutation, in Racket Here’s one way to do it, without higher order functions: (define (mult-by-two ls) (if (empty? ls) '() (cons (* 2 (car ls)) (mult-by-two (cdr ls))))) 1) Why take functions as arguments? Now, use Higher Order Functions. By taking another function as an argument, the previous code can be separated into two parts: the evaluation, and the recursive act of applying the evaluation (define (apply f ls) (if (empty? ls) '() (cons (f (car ls)) (apply f (cdr ls))))) (define (mult-2 x) (* x 2)) (define (mult-by-two ls) (apply mult-2 ls)) 1) Why take functions as arguments? And as we saw, apply is built-in to all functional languages. It’s actually called map. Using built-in higher order functions, functional-stye repetition is as easy as: (define (mult-2 x) (* x 2)) (define (mult-by-two ls) (map mult-2 ls)) 1) Why take functions as arguments? BIG PICTURE: Higher order functions let our code be more elegant and modular: we can re-use code and ultimately write less code. public static int[] multTwo(int[] myArray){ for (int i= 0; i < myArray.length; i++) { myArray[i] = myArray[i] * 2; } return myArray; } (define (mult-2 x) (* x 2)) (define (mult-by-two ls) (map mult-2 ls)) 2) Why return functions? In our previous example, the mult-2 function that we mapped over the list took only one argument: (define (mult-2 x) (* x 2)) (define (mult-by-two ls) (map mult-2 ls)) But what if we needed two arguments? For example, what if we wanted to specify the value to add to each list element? Try running this in DrRacket. What error do you get? tt 2) Why return functions? To fix the arity mismatch in Racket, we need to return a function that grabs the list item. 2) Why return functions? (define (add-stuff x) (lambda (y) (+ x y))) ---------------------------------------------------------------------------- > (map (add-stuff 5) (list 1 2 3 4))
(map (lambda (y) (+ 5 y)) (list 1 2 3 4)
Now map can send (car (list 1 2 3 4)) to a lambda function that, appropriately, only expects one item, the list item
(list 6 7 8 9)
2) Why return functions?
BIG PICTURE:
Returning functions lets us accommodate arity requirements, thus allowing our modular functions to fit together.
Participation Quiz (Google Doc)
Practice with Higher Order Functions
Participation Quiz Answers
New Today
More built-in higher order functions
We’ve already seen map. Let’s add…
foldr / foldl
filter
Built-in higher order functions: fold
A fold takes a function and “folds” it in between the elements of a list, returning one value:
> (foldr + 0 ‘(1 2 3))
1 2 3
+ 1 + 2 + 3
0 + 1 + 2 + 3
6
foldr
> (foldr – 0 ‘(1 2 3))
2
(- 1 (- 2 (- 3 0)))
(- 1 (
(- 1 (- 2 (
(- 1 (- 2 (- 3 0)))
We call this a “right” fold, because the evaluation order of this expression reads the input list from right to left.
Implementing fold right:
> (myfoldr – 0 ‘(1 2 3))
2
21
Fold left
foldl means a left-to-right fold in this sense:
(foldl – 0 (list 1 2 3 4 5)
(- 5 (- 4 (- 3 (- 2 (- 1 0)))))
= 3
The evaluation order, (- 1 0) first, (- 2 (- 1 0)) next, reads the list (list 1 2 3 4 5) from left to right.
(- 1 0)
(- 2 (- 1 0))
(- 3 (- 2 (- 1 0)))
(- 4 (- 3 (- 2 (- 1 0))))
(- 5 (- 4 (- 3 (- 2 (- 1 0)))))
Implementing fold left:
When to use foldr, when foldl?
foldr evals a list right-to-left, and foldl evals it left-to-right. The choice between them just depends on your problem.
Ex.: You could make a descending list into an ascending list just by using foldl:
foldl cons ‘() (list 3 2 1)
Constructing (“consing”) a list as you read the input list from left to right reverses the original order of the list:
(cons 3 ‘() )
(cons 2 (cons 3 ‘() ))
(cons 1 (cons 2 (cons 3 ‘() )))
Another important built-in higher order function:
Filter
> (filter even? (list 1 2 3 4 5))
‘(2 4)
Filter takes a predicate and a list and returns a list of only those items from the input list that satisfy the predicate.
Ordinary Filter Implementation?
Fun Challenge
You can use foldr to implement filter!
Why does this work?
> (my-filter even? (list 1 2))
(my-foldr (lambda (x base) …) ‘() (list 1 2))
( (lambda (x base) …) 1 (my-foldr (lambda (x base) …) ‘() (list 2)))
( (lambda (x base)…) 1 ( (lambda (x base) …) 2 (my-foldr (lambda (x base) …) ‘() ‘()))
( (lambda (x base)…) 1 ( (lambda (x base) …) 2 ‘()))
( (lambda (x base)…) 1 (cons 2 ‘()))
(cons 2 ‘())
/docProps/thumbnail.jpeg