Date: Thu, 28 Mar 2024 14:47:42 -0500 (CDT) Message-ID: <1679448127.1021.1711655262184@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1020_199671162.1711655262183" ------=_Part_1020_199671162.1711655262183 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Use the Intermediate Student with lambda
language level. Yo=
u can choose to use lambda
, as appropriate, in any of the assi=
gned problems. [For 2011: You may not use local
to de=
fine functions; all program functions (including helpers) must be defined a=
t the top level.]
Book Problems:
(define= (my-max lon) (cond [(empty? lon) (error 'my-max "applied to no arguments")] [(empty? (rest lon)) (first lon)] [else (local [(define head (first lon)) (define max-tail (my-max (rest lon)))] (if (>=3D head max-tail) head max-tail))]))
(define= (my-max1 lon1) (cond [(empty? lon1) (error 'my-max "applied to no arguments")] [(empty? (rest lon1)) (first lon1)] [else (local [(define head2 (first lon1)) (define max-tail2 (my-max1 (rest lon1)))] (if (>=3D head2 max-tail2) head2 max-tail2))]))
make-sort
.make-sort
produces functions. Test these results by applyi=
ng them to a few different arguments.greg
is (4, -4/3, 4/5, -4/7, ...=
).(lambda= (f g x) (f x (lambda (x) (g (g x)))))
(lambda= (f1 g1 x1) (f1 x1 (lambda (x2) (g1 (g1 x2)))))
; compo= se : ? ; Purpose: (compose f g) returns the result of composing functions f and g:= x |-> f(g(x)) (define (compose f g) (lambda (x) (f (g x))))
mergesort
function as described in=
exercise 26.1.2, except decompose the problem "top-down" rather than "bott=
om-up". You will need to define a function split: (list-of number) -&=
gt; 2-element-structure-of-lists-of-number)
that partitions its inpu=
t into two lists of approximately (+/- 1) the same length in O(n) time wher=
e n is the length of the input list. (split l)
returns a =
2-element structure containing two lists of numbers. See below for hints in=
defining a 2-element structure. After splitting the list in half, Hints for writing the "split" function:
A 2-element structure can be defined (you MUST do this somewhere!) in on= e of two ways:
a) Define your own structure. The CS term for a pair of= elements is "dyad", so for instance, one could define a structure as<= /p>
(define= -struct dyad (first second))
Review your notes on how "define-struct" automatically creates cons= tructor and accessor functions. You will still need to, i= n words, define what types the "first" and "second" elements are supposed t= o be (note: there are several ways to do this).
b) Use Scheme's built-in functions. First, you mu=
st explicitly define that you are going to use a list of exactly two elements, i.e. (list a b=
)
. Scheme already provides functions to access the=
first and second elements of such a list, called, oddly enough, "first" an=
d "second":
(first = (list a b)) =3D=3D> a (second (list a b)) =3D=3D> b
Again, you will still need to define exactly what types the first and se= cond elements are supposed to be. DO NOT USE <= code>(first (rest lon)) as this an encapsulation vi= olation of an indefinite-length list!
Think simple!
Follow these important rules whenever you write function on a list using <=
em>structural recursion (note that the generative recursion that merge=
sort uses follows slightly different rules):
(first aList)
and the recursive result, (local
definition to keep you from repeating the recu=
rsive call.