Write slope@,
which takes in a function f : real --> real,
a number x,
and a positive number e
(the "tolerance", usually small ... whatever "small" means).
It returns an approximation to the slope of f at
the point x,
according to the math formula:
slope@(f,x,e) = (f(x+e) - f(x-e)) / 2e
Thus, the slope of a horizontal line (constant function) is 0 everywhere, and of a line at 45 degrees (identity function) is 1 everywhere, and a curve which is horizontal "for a moment" has a slope of 0 just at that point (e.g. the top of the St. Louis arch).)
Aside:
Really, we're precisely computing f's average slope,
between x-e and x+e (provided f is continuous).
The hope is,
the function's slope at a particular point is close to its
average nearby slope (where "nearby" means "within e").
A good bet for most functions, but
the wigglier f is, the worse our guess is (for a fixed e);
a few functions wiggle wildly
(like
To think about:
How might you decide whether a function is very wiggly,
so that your function might automatically decide
to try a smaller e?
This problem does not require any knowledge of calculus --
only the math mentioned here.
If you have had calculus:
What is the diference between this approach of finding
the derivative, vs the approach taken by programs like Mathematica?
(Which of these corresponds to what you spent months learning, in calculus?)
Also, why does the above formula compute precisely
the average slope of f between two points (if f continuous)?
The average of a function between a and b,
is the integral from a to b divided (normalized) by (b-a);
Note that the integral of f' from a to b is f(b)-f(a) --
that's the fundamental theorem of calculus!:
We can determine the average value of f' over an entire interval,
only by knowing f at the endpoints.)
Now let's make a curried version of this:
Write the function slope,
which takes in a function f : real --> reale,
and returns a function real --> real
Can you see
how to do this with
local (but not lambda);
and
how to do this with
lambda (but not local)?
You may instead call this derivative or d/dx if
you like.
map:
What is the (approximate) derivative of
sqrt
at the inputs
(list 1 2 3 100 200 300 1000 2000 3000)
?
Use map.
(You'll need to create a function which already has
a own tolerance e included its own closure (scope),
since map wants functions of just one argument,
not two!)
Optional:
A function h: natnum --> real can be viewed as a histogram --
e.g. (h 3) returns how high the graph is along the interval [3,4).
Write a function which takes in h, a, b
and returns the total area under the histogram
in [a,b).
It's a one-liner, if you
use map, along with these handy helpers:
;; nums-between: natnum, natnum --> list-of-natnum
;; Return a (descending) list of the natnums in [a,b).
;; That is, including a but not including b.
;;
(define (nums-between a b)
(cond [(<= b a) empty]
[(> b a) (cons (sub1 b) (nums-between a (sub1 b)))]))
;
; Sneaky -- we're deviating from the natnum template,
; using b <= a as our base case instead of b=0!
; Really we're following the data def'n of b being of type
; "natnums >= a", except we handle <a and =a together.
(equal? (nums-between 4 4) empty)
(equal? (nums-between 4 5) (list 4))
(equal? (nums-between 4 7) (list 6 5 4))
(equal? (nums-between 4 2) empty)
;; sum: list-of-number --> number
;; Return the sum of the numbers in nums.
;;
(define (sum nums) (foldr + 0 nums))
;
; Remember, foldr wants:
; - for the cons case,
; how to combine first with the result of recursion on rest. (Here, +.)
; - for the empty case,
; the result (here, 0).
; - the list to be processed.
Extra-Challenge (optional):
Generalize this function to
compute the (approximate) area
under h:real --> real on [a,b),
by
dividing it up into
skinny rectangles.
What other inputs are needed?
(You can subdivide into trapezoids
or some other shape if you like;
we'll see a more interesting
adaptive method
later, for computing approximate area under a curve.)
Consider the idea of iterating a function: for instance, if I repeatedly double 3, I get 6, then 12, then 24, etc. That is, I take the output of a function, and again apply the function to that.
Iterating square twice, starting with 5,
yields (square (square 5)) = 625.
If I had a function
remove-max: list --> list(list 7 18 2 9 3)
(remove-max (remove-max (remove-max (list 7 18 2 9 3)))) = (list 2 3)In general, iterating some function
f 3 times
starting with i means
(f (f (f i)))
Write the function iterate,
which takes a function, a natNum,
and an initial input to the function,
and iterates the function that many times.
(e.g. we saw (iterate remove-max 3 (list 7 18 2 9 3)).
(Hint: what template will you base your code on?
Natnums!)
Challenge (optional):
Write two different versions of iterate,
one which is tail-recursive and one which isn't
(and indicate which is which, of course).
Using iterate,
write remove-first-n,
which takes a number n and list,
and returns the list with the first n items
removed.
(Of course, an error would result if the list
had fewer than n items.)
Challenge:
(for advanced calculus students):
Write a function which takes in a function f
and a number n,
and returns the
nth term of f's
Taylor series (or, Fourier Series) expanded around 0.
(Hint: iterate derivative!)
Write a function which takes in k
and x, and returns the sum of the
first k Taylor-terms-around-0, evaluated at x.
Write a function which just takes in k,
and returns a function awaiting a particular x!
You can of course provide a value x0 to expand
around, rather than 0.
We've seen in lecture a data-definition for Disk-Entries, that were mutually recursive (since directories contained a list-of-disk-entries). Often
map can be used in place of the
a second function to process the entire list:
;; A Disk-Entry is
;; -- (make-File string num)
;; -- (make-Folder symbol list-of-Disk-Entries)
;; A File is structure with a name and a size.
(define-struct File (name size))
;; A Folder has a name, and a list of other entries:
(define-struct Folder (name entries))
;; list-of-Disk-Entries is
;; -- empty
;; -- (cons Disk-Entry list-of-Disk-Entries)
;; sum: list-of-number --> number
;; Return the sum of the numbers in nums.
;;
(define (sum nums) (foldr + 0 nums))
;;;;;;;;;;;;;; Now, a function handling disk-entries. ;;;;;;;;;;
;; de-size: Disk-entry --> number
;; Return total number of disk-entries contained within a given one.
;;
(define (de-size a-de)
(cond [(File? a-de) 1] ; A single file contains just itself.
[(Folder? a-de) (+ 1 ; For the directory itself, plus..
(sum (map de-size (Folder-entries a-de))))]))
By recursively mapping de-size onto the list of
Disk-entrys,
we happily get back a list containing the size of
each sub-Disk-entry,
not needing to write a separate helper for that
list-of-disk-entry.
dot-product,
which takes in two lists of n numbers
(
a1
a2
...
an)
and
(b1
b2
...
bn)
and returns
a1*
b1
+
a2*
b2
+
an*
bn
(for any n >= 0).
(What are some trivial test cases?)
Hint: the built-in
map actually can
take
in a binary function and two lists of arguments.