{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman{\*\falt Thorndale};}{\f2\fmodern\fcharset0\fprq1{\*\panose 02070309020205020404}Courier New;}
{\f29\fswiss\fcharset128\fprq2{\*\panose 020b0604020202020204}Arial Unicode MS;}{\f30\fswiss\fcharset128\fprq2 @Arial Unicode MS;}{\f31\froman\fcharset238\fprq2 Times New Roman CE{\*\falt Thorndale};}
{\f32\froman\fcharset204\fprq2 Times New Roman Cyr{\*\falt Thorndale};}{\f34\froman\fcharset161\fprq2 Times New Roman Greek{\*\falt Thorndale};}{\f35\froman\fcharset162\fprq2 Times New Roman Tur{\*\falt Thorndale};}
{\f36\froman\fcharset177\fprq2 Times New Roman (Hebrew){\*\falt Thorndale};}{\f37\froman\fcharset178\fprq2 Times New Roman (Arabic){\*\falt Thorndale};}{\f38\froman\fcharset186\fprq2 Times New Roman Baltic{\*\falt Thorndale};}
{\f47\fmodern\fcharset238\fprq1 Courier New CE;}{\f48\fmodern\fcharset204\fprq1 Courier New Cyr;}{\f50\fmodern\fcharset161\fprq1 Courier New Greek;}{\f51\fmodern\fcharset162\fprq1 Courier New Tur;}{\f52\fmodern\fcharset177\fprq1 Courier New (Hebrew);}
{\f53\fmodern\fcharset178\fprq1 Courier New (Arabic);}{\f54\fmodern\fcharset186\fprq1 Courier New Baltic;}{\f265\fswiss\fcharset0\fprq2 Arial Unicode MS Western;}{\f263\fswiss\fcharset238\fprq2 Arial Unicode MS CE;}
{\f264\fswiss\fcharset204\fprq2 Arial Unicode MS Cyr;}{\f266\fswiss\fcharset161\fprq2 Arial Unicode MS Greek;}{\f267\fswiss\fcharset162\fprq2 Arial Unicode MS Tur;}{\f268\fswiss\fcharset177\fprq2 Arial Unicode MS (Hebrew);}
{\f269\fswiss\fcharset178\fprq2 Arial Unicode MS (Arabic);}{\f270\fswiss\fcharset186\fprq2 Arial Unicode MS Baltic;}{\f273\fswiss\fcharset0\fprq2 @Arial Unicode MS Western;}{\f271\fswiss\fcharset238\fprq2 @Arial Unicode MS CE;}
{\f272\fswiss\fcharset204\fprq2 @Arial Unicode MS Cyr;}{\f274\fswiss\fcharset161\fprq2 @Arial Unicode MS Greek;}{\f275\fswiss\fcharset162\fprq2 @Arial Unicode MS Tur;}{\f276\fswiss\fcharset177\fprq2 @Arial Unicode MS (Hebrew);}
{\f277\fswiss\fcharset178\fprq2 @Arial Unicode MS (Arabic);}{\f278\fswiss\fcharset186\fprq2 @Arial Unicode MS Baltic;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;
\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}
{\stylesheet{\ql \li0\ri0\widctlpar\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 \fs24\lang1033\langfe1033\cgrid\langnp1033\langfenp1033 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{
\s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 \fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 \snext15 Default;}{\s16\ql \li0\ri0\nowidctlpar\tqc\tx4320\tqr\tx8640\aspalpha\faauto\rin0\lin0\itap0 
\fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 \sbasedon15 \snext16 header;}{\*\cs17 \additive \fs24\cf1\lang0\langfe255\langfenp255 Numbering Symbols;}}{\info{\author Sharon Tuttle}{\operator CNRS}{\creatim\yr2002\mo10\dy11\hr14\min30}
{\revtim\yr2002\mo11\dy15\hr23\min21}{\printim\yr2002\mo10\dy29\hr9\min52}{\version2}{\edmins2}{\nofpages2}{\nofwords772}{\nofchars4403}{\*\company CNRS-HSU}{\nofcharsws5407}{\vern8269}}\margt2114 
\deftab1250\widowctrl\ftnbj\aenddoc\noxlattoyen\expshrtn\noultrlspc\dntblnsbdb\nospaceforul\hyphcaps0\horzdoc\dghspace120\dgvspace120\dghorigin1701\dgvorigin1984\dghshow0\dgvshow3\jcompress\viewkind1\viewscale90\nolnhtadjtbl \fet0\sectd 
\sbknone\linex0\headery1440\sectdefaultcl {\header \pard\plain \s16\ql \li0\ri0\nowidctlpar\tqc\tx4320\tqr\tx8640\aspalpha\faauto\rin0\lin0\itap0 \fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 {\fs16 CS 131 - Homework #10\tab \tab p. }
{\field{\*\fldinst {\fs16 \\page}}{\fldrslt {\fs16\lang1024\langfe1024\noproof 2}}}{
\par }{\fs16 Fall 2002
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \s15\qc \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 
\fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 {\b\fs20 CS 131 - Intro to Computer Science I - Fall 2002
\par Homework #10
\par DUE: Friday, November 22th, by }{\b\fs20\ul 5:00 pm}{\b\fs20 
\par }{\b\fs20\ul 
\par }\pard \s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 {\fs20 As always, you will turn in certain function definitions and expressions that you have typed into the DrScheme definitions window and saved into one or more file names ending in }{
\b\fs20 .scm}{\fs20  .
\par 
\par The same homework and style guidelines apply as before, }{\b\fs20 except}{\fs20  as modified below.
\par }{\b\fs20 
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {\fs20 (we'll talk about the following in class next Tuesday (11-19), also --- but, in the meantime:
\par 
\par HtDP, p. 296: In}{\b\fs20  PARAMETRIC DATA DEFINITIONS,}{\fs20  we ..."agree that they do not specify everything about a class of data. Instead we use}{\b\fs20  variables }{\fs20 to say that any form of Scheme data can be used in a certain place."
\par }{\b\fs20 
\par }{\fs20 Once you give the parametric data definition, you may use it with any type as you like (just like once you define a function, you may call it with any argument you wish...)
\par 
\par Consider:
\par 
\par }{\fs20\loch\af2 \hich\af0\dbch\af0\loch\f2 ;;-\hich\af0\dbch\af0\loch\f2 -------------------------------------------------------
\par \hich\af0\dbch\af0\loch\f2 ;; a (listof ITEM) is either
\par \hich\af0\dbch\af0\loch\f2 ;;    1. the empty list, empty, or
\par \hich\af0\dbch\af0\loch\f2 ;;    2. (cons elem a-list) where
\par \hich\af0\dbch\af0\loch\f2 ;;       (a) elem is an ITEM and
\par \hich\af0\dbch\af0\loch\f2 ;;       (b) a-list is a (listof ITEM)
\par \hich\af0\dbch\af0\loch\f2 ;;----------------------------\hich\af0\dbch\af0\loch\f2 ----------------------------
\par }{\b\fs20\loch\af2 
\par }{\fs20 Using this one parametric data definition, now in a contract we can use (listof number) to represent a list of numbers, (listof symbol) to be a list of symbols, (listof (listof number)) to be a list where each element is a lis
t of numbers, etc. One parametric data definition is all you need for all of those uses.
\par 
\par What if a function can take any list? The text suggests using (listof X) for this (although, frankly,I'll still accept "list" when ANY list will do, also).
\par 
\par So, for example, if I just put the above data definition, then some example contracts are:
\par 
\par }{\fs20\loch\af2 \hich\af0\dbch\af0\loch\f2 ;; CONTRACT: length : (listof X) --> number
\par 
\par \hich\af0\dbch\af0\loch\f2 ;; (assuming that, say, a mail structure has already been defined)
\par \hich\af0\dbch\af0\loch\f2 ;; CONTRACT: grab-names : (listof mail) -> (listof s\hich\af0\dbch\af0\loch\f2 ymbol)
\par 
\par }{\fs20 ...(the latter could be used for a function that created a list of names (each expressed as a symbol) pulled from all of the mail structures in a list of mail structures)...
\par 
\par Now, in class on 11-12, we gave the following contract for filter1:
\par }{\fs20\loch\af2 
\par }{\fs16\loch\af2 \hich\af0\dbch\af0\loch\f2 ;; C\hich\af0\dbch\af0\loch\f2 ONTRACT: filter1: (number number -> boolean) list-of-numbers number -> list-of-numbers
\par 
\par }{\fs20 Using the parametric data definition for lists given above, this could now be rewritten as:
\par }{\fs16\loch\af2 
\par \hich\af0\dbch\af0\loch\f2 ;; CONTRACT: filter1: (number number -> boolean) (listof number) number -> \hich\af0\dbch\af0\loch\f2 (listof number)
\par }{\fs20\loch\af2 
\par }{\fs20 But, it turns out that our filter1 is actually much more versatile even than this --- as explained in the text, filter1's contract can be even more accurately expressed as:
\par }{\fs20\loch\af2 
\par \hich\af0\dbch\af0\loch\f2 ;; CONTRACT: filter1 : (X Y -> boolean) (listof X) Y  -> (listof \hich\af0\dbch\af0\loch\f2 X)
\par }{\fs20 
\par 1.\tab 
To demonstrate that the final contract for filter1 really does hold, copy the parametric data definition for (listof ITEM) from above, and then copy filter1 from the posted in-class examples (but include the above improved contract instead of that given).

\par 
\par \tab Now, include a data definition for a sale-item, made up of a sale item's name and its price. 
\par 
\par \tab Write a function }{\b\fs20 price-greater }{\fs20 that takes a sale-item instance and a number, and returns true if that sale-item's price is strictly greater than the number given. (that is, 
\par 
\par }\pard \s15\ql \fi-435\li855\ri0\nowidctlpar\aspalpha\faauto\rin0\lin855\itap0 {\fs20 \tab (price-greater (make-sale-item 'tonka-truck 15.99) 15) would be true,
\par     \tab (price-greater (make-sale-item 'legos 19.99) 19.99) would be false
\par 
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {\fs20 \tab Now, use filter1 and price-greater to write a function}{\b\fs20  all-greater }{\fs20 
that takes a list of sale-items and a price, and returns a list of sale-items all of whose price exceeds the given price. (Consider carefully: how should all-greater's contract be written?)
\par }{\b\fs20 
\par 2.\tab }{\fs20 Consider Exercise #19.1.5 from p. 292 of HtDP. Abstract the f
unctions min and max given into a single function, and do use local to improve the abstracted result as they suggest. (You only have to turn in the final version of the function, along with its usual design recipe pieces --- don't forget the appropriate d
ata definition(s), which should be parametric when appropriate.) Test it using at least the three lists given (the ones numbered 1., 2., and 3.) You do not have to introduce the local auxiliary function mentioned at the end, however (unless you want to).

\par 
\par \tab (You do}{\b\fs20  not }{\fs20 
have to answer this in your homework assignment, but: if you can, run both the version without the local and the one with the local on the long list in reverse order from 20 to 1. Count how long it takes for each of the two results --- can you 
see a difference in how long each takes? Why do you think using local makes a difference here? We'll try to discuss this in class after this assignment has been turned in.)
\par 
\par 3.\tab Do Exercise #19.1.6 from p. 292 of HtDP. Be sure to include at least the two tests mentioned (and in writing the contract for the new version, make use of one of the data definitions from a previous problem on this homework...)
\par 
\par 4.\tab Do Exercise #21.2.1, part 3, p. 314 (the function}{\b\fs20  evens}{\fs20 , using Scheme's built-in build-list function). Hint: use}{\b\fs20  local }{\fs20 to define an appropriate function to pass to }{\b\fs20 build-list}{\fs20 ..}{\b\fs20 
\par 
\par }{\fs20 5.\tab Do Exercise #21.2.2, part 1, p. 314 (the function }{\b\fs20 convert-euro}{\fs20 , using Scheme's built-in }{\b\fs20 map}{\fs20  function). Here, I want to point out that any constant definitions certainly should be
 included within the final function with the help of }{\b\fs20 local}{\fs20 ...and here, too, you should use }{\b\fs20 local}{\fs20  to define an appropriate function to pass to }{\b\fs20 map}{\fs20 .}{\b\fs20 
\par 
\par \tab 
\par }\pard \s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 {\b 
\par }}