PowerPoint Presentation
CS 345
Lecture 5
Last Session
Lists as “recursive data structures”
all lists are composed of the “head of the list” (car ls) and the “rest of the list” (cdr ls)
(list 1 2 3)
(car ls) = 1
(cdr ls) = (list 2 3)
Recursion over lists
evaluate (car ls) and recurse on (cdr ls)
Functional “negate-all”
(define (negate-all ls)
(if (empty? ls)
‘()
(cons (- (car ls)) (negate-all (cdr ls)))))
> (negate-all (list 1 2 3))
> ‘(-1 -2 -3)
(cons -1 (negate-all (list 2 3)))
(cons -1 (cons -2 (negate-all (list 3))))
(cons -1 (cons -2 (cons -3 (negate-all empty))))
(cons -1 (cons -2 (cons -3 ‘())))
Today’s New Topic:
HIGHER ORDER FUNCTIONS
Imagine you own a store, and you want to sell all your merchandise that is priced at or above some amount (say, $100) at a discount (say, at 85% of its usual price).
Let’s write a function that returns your revenue, if you sold all your merchandise.
Inventory = $90, $100, $100, $100
$90, $85, $85, $85 $345
Participation Quiz: Write an imperative version
using Java or Python or pseudocode
public class Revenue {
static int[] priceList = {54, 360, 67, 32, 410, 33, 79, 109, 144};
static double revenue(double breakpoint, double discount){
… Your code goes here….
Test your code with the breakpoint of 100 and discount of 15% off
How do we get started writing the functional version?
My suggestion: Try to phrase the solution as a quantity, in a sentence, as if you were helping a grade-schooler with their word problem from math class.
“The revenue from selling everything is the sum of the prices of all items, where the price for some items is discounted.”
We mentioned sum the other day:
(define (sum ls)
(if (empty? ls)
0
(+ (car ls) (sum (cdr ls)))))
(+ 90 (+ 85 (+ 85 (+ 85 0))))
Now, let’s write disc-prices.
This approach is ok:
> (sum (disc-prices 100 0.85 (list 90 100 100 100)))
But it’s not great, because functional programming can be so much more modular than this.
Making the code more modular
(define (apply f ls)
(if (empty? ls)
‘()
(cons (f (car ls)) (apply f (cdr ls)))))
More modular: now I can use this function to apply any other function, such as a discount function but also others, to any list
Apply is a “higher order function,” because it accepts a function as a parameter
Now let’s write discount
Why won’t this work?
“Arity mismatch”: the apply function expects the function f itself to accept only one parameter.
That discount function could work, if we re-wrote apply like this:
(define (apply f x y ls)
(if (empty? ls)
‘()
(cons (f x y (car ls)) (apply f x y (cdr ls)))))
But why wouldn’t we want do that?
To be as modular as possible, apply should enforce only what is guaranteed from as generic a perspective as possible, namely that the function f will take one parameter: a single list item.
The functions that serve a very specific scenario should be the ones to conform to the general functions, not the other way around.
Functional languages like Racket make it possible to write, say, discount in a cool way that makes it as flexible as needed…
Keep apply as it was, and write discount like this!
This function is “higher order” in the second sense of the term: it returns a function!
Our final program:
Wasn’t apply handy? Gosh, shouldn’t it be built-in?
It is! apply is my implementation of map.
>(map add-one (list 1 2 3 4))
‘(2 3 4 5)
And wasn’t sum handy? Shouldn’t it be built-in, too?
It is! sum is my implementation of (foldr + 0 ls).
> (foldr + 0 (list 1 2 3))
> 6
In this class, you’ll be asked to feel comfortable with these built-in higher order functions:
map
foldr/foldl
filter
Look how gorgeously tiny our program can be using built-in HOFs:
/docProps/thumbnail.jpeg