[SOLVED] CS Java data structure python flex PowerPoint Presentation

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

Todays 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).

Lets 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, lets write disc-prices.

This approach is ok:

> (sum (disc-prices 100 0.85 (list 90 100 100 100)))

But its 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 lets write discount
Why wont 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 wouldnt 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:

Wasnt apply handy?Gosh, shouldnt 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 wasnt sum handy?Shouldnt 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, youll 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