perm filename SOLN2.S79[206,LSP] blob sn#451440 filedate 1979-06-13 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00010 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 \input mytex[1,rdg] % TEX file used to answer HomeWork Set 2, Spring 1979 C00006 00003 \HeadA⊂Answers to Problem Set $\#$2 - Due April 12, 1979⊃ C00011 00004 \QUESTION 4\ ([MT]p17 $\#4$). C00023 00005 \QUESTION 5\ ([MT]p9 $\#1)$. C00024 00006 \STATEMENT C00030 00007 \QUESTION 8. C00033 00008 \QUESTION 10. C00036 00009 \QUESTION 11\ (Optional). C00041 00010 \par\vfill\eject C00048 ENDMK C⊗; \input mytex[1,rdg] % TEX file used to answer HomeWork Set 2, Spring 1979 % This is the answer to the homework set # 2 % Handed out: Thursday 5-April; due Thursday 12-April \def\QUESTION #1.{\HeadB⊂Question $\#$#1⊃\eightpoint\hangindent 10pt\sl\xskip\!} \def\STATEMENT #1\etats{\par\yyskip {\hrule width 10pc} \eightpoint\hangindent 10pt\sl #1\par {\hrule width 10pc}} \def\ANSWER{\par\HeadC⊂Answer⊃\ninepoint\rm\!} \def\equatno(#1){{\sl Equation (#1)}} \def\ref #1[#2]{{\bf #1},{\sl #2}} \def\disptext #1{\par\yyskip\ctrline {#1}\par\yyskip\noindent\!} \def\funct #1[#2]{{\LISPE #1|}{\rm [}$\,$#2$\,${\rm ]}} \def\eq {$\null=\null$} % this does the right thing with spacing \def\assign {$\null\←\null$} % this does the right thing with spacing \def\LISPE #1|{{\sl #1}} % this is for LISP External Notation \def\LISPI #1|{{\bf #1}} % this is for LISP Internal Notation \def\a #1{\LISPI $\underline a$|$\,$#1} \def\d #1{\LISPI $\underline d$|$\,$#1} \def\at #1{\LISPI $\underline {\hbox {at}}$|$\,$#1} \def\n #1{\LISPI $\underline n$|$\,$#1} \def\cons ⊂#1.#2⊃{\LISPI #1\ .\ #2|} \def\append ⊂#1*#2⊃{\LISPI #1\ *\ #2|} \def\list <#1>{\LISPI <\ #1\ >|} \def\if #1{\LISPI $\underline {\hbox {if}}$| #1} \def\then #1{\LISPI $\underline {\hbox {then}}$| #1} \def\else #1{\LISPI $\underline {\hbox {else}}$| #1} \def\elseif #1{\LISPI $\underline {\hbox {elseif}}$| #1} \HeadA⊂Answers to Problem Set $\#$2 - Due April 12, 1979⊃ \QUESTION 1\ ([MT]p17 $\#1$). Consider the function \LISPE drop| defined by \disptext{\LISPE \funct drop[ u ] \assign \if \n u \then NIL \else \cons ⊂\list <\a u> . \funct drop[ \d u]⊃|.} Compute (by hand) \LISPE \funct drop[ {\LISPI (A B C)|} ]|. What does \LISPE drop| do to lists in general? Write \LISPE drop| in internal notation using \LISPI DEFUN|. \ANSWER \LISPE \funct drop[ {\LISPI (A B C)|} ]| will returns \LISPI ((A) (B) (C))|. In general, it will make each element, \LISPI x|, of a list into the list, \LISPI ( x )| -- i.e. a list whose single member is this \LISPI x|. (Of course, \LISPI x| need not be an atom, but may be a list itself.) In internal notation, we would write $$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr (DEFUN ⊗DROP⊗(U)⊗\cr ⊗(COND⊗((NULL U)⊗NIL)\cr ⊗⊗(T⊗(CONS (LIST (CAR U)) (DROP (CDR U))))))\cr }}$$ \QUESTION 2\ ([MT]p17 $\#2$). What does the function \disptext{\LISPE \funct r2[ u ] \assign \if \n u \then NIL \else \cons ⊂\funct reverse[\a u] . r2[\d u]⊃|} do to lists of lists? How about $$\vcenter{\halign{\lft{\LISPE #|}⊗\assign\lft{\LISPE #|}\cr \funct r3[ x ]⊗\if \at x \then x \else \funct reverse[{\funct r4[x]}]\cr \funct r4[ u ]⊗\if \n u \then NIL \else \cons ⊂\funct r3[\a u].\funct r4[\d u]⊃?\cr}}$$ \ANSWER \LISPE r2| reverses each element, \LISPI x|, of a list. These reverse elements are then returned, in order. E.G. \LISPE \funct r2[ {\LISPI ( (A B (X Y)) (C D E) (Q) ) |} ]| returns \LISPI ( ((X Y) B A) (E D C) (Q) ) |. \LISPE r3| uses \LISPE r4| to recursively reverse the order of each entry in a list, as well as the list itself. That is, all sub-lists, sub-sub-lists, etc. and will be reversed, not just those at the first level. (E.G. \LISPE \funct r3[ {\LISPI ( (A B (X Y)) (C D E) (Q) ) |} ]| returns \LISPI ( (Q) (E D C) ((Y X) B A) ) |.) \LISPE r4| reverses the order of all sublists within the overall list, but not the order of elements of this full list. (E.G. \LISPE \funct r4[ {\LISPI ( (A B (X Y)) (C D E) (Q) ) |} ]| returns \LISPI ( (A B (X Y)) (C D E) (Q) ) |.) It also has the problem that it doesn't give an error when its argument is not a (non-\LISPI NIL|) atom. \QUESTION 3\ ([MT]p17 $\#3)$. Compare \disptext{\LISPE \funct r3'[ x ] \assign \if \at x \then x \else \append ⊂\list <\funct r3'[\d x]>*\list <\funct r3'[\a x]>⊃|} with the function \LISPE r3| of the proceeding example. \ANSWER \LISPE r3'| correctly reverses S-expressions, whereas \LISPE r3| reverses LISTs. That is, \LISPE r3'| does NOT do the appropriate thing with the \LISPI NIL| which terminates each list, as \LISPE r3| does. (E.G. \LISPE \funct r3'[ {\LISPI ( A ) |} ]| returns \LISPI (NIL . A) |.) \QUESTION 4\ ([MT]p17 $\#4$). Consider \LISPE r5| defined by \disptext{\LISPE \funct r5[ u ] \assign \if \n u $∨$ \n {\d u} \then u \else \cons ⊂[\a \funct r5[\d u]].{\funct r5[\cons ⊂\a u. \funct r5[\d \funct r5[\d u]]⊃}]⊃|.} Compute \LISPE \funct r5[ {\LISPI (A B C D)|} ]|. What does \LISPE r5| do? Needless to say, this is not a good way of computing this function even though it involves no auxiliary functions. [This ingenious defination was discovered by S. Ness.] \ANSWER To no one's surprise, this function computes the reverse of its argument. Disbelievers should trace this function as follows: $$\vcenter{\halign{\lft{\LISPE #|}⊗\eq\lft{\LISPE #|}\cr \funct r5[ {\LISPI (A B C D)|} ]⊗ \cons ⊂[\a \funct r5[\d (A B C D)]]. {\funct r5[\cons ⊂\a (A B C D).\funct r5[\d \funct r5[\d (A B C D]]⊃]}⊃\cr ⊗\cons ⊂[\a \funct r5[ (B C D)]].{\funct r5[\cons ⊂A.\funct r5[\d r5[ (B C D)]]⊃]}⊃.\cr \funct r5[ {\LISPI (B C D)|} ]⊗ \cons ⊂[\a \funct r5[(C D)]].{\funct r5[\cons ⊂B.\funct r5[\d \funct r5[(C D)]]⊃]}⊃.\cr \funct r5[ {\LISPI (C D)|} ]⊗ \cons ⊂[\a \funct r5[(D)]].{\funct r5[\cons ⊂C.\funct r5[\d \funct r5[(D)]]⊃]}⊃.\cr \funct r5[ {\LISPI (C D)|} ]⊗ \cons ⊂[\a \funct r5[(D)]].{\funct r5[\cons ⊂C.\funct r5[\d \funct r5[(D)]]⊃]}⊃.\cr \funct r5[ {\LISPI (D)|} ]⊗ \LISPI (D)|.\cr}}$$ THEREFORE $$\vcenter{\halign{\lft{\LISPE #|}⊗\eq\lft{\LISPE #|}\cr \funct r5[ {\LISPI (C D)|} ]⊗ \cons ⊂[\a (D)].{\funct r5[\cons ⊂C.\funct r5[\d (D)]⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[\cons ⊂C.\funct r5[NIL]⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[\cons ⊂C.NIL⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[ (C) ]}⊃\cr ⊗\cons ⊂D.(C)⊃\cr ⊗\LISPI (D C)|.\cr}}$$ This used the fact that \funct r5[ {\LISPI NIL|} ] \eq \LISPI NIL|, and \funct r5[ {\LISPI (C)|} ], being of the same form as \funct r5[ {\LISPI (D)|} ], would equal just \LISPI (C)|. Backing up this recursion, we see $$\vcenter{\halign{\lft{\LISPE #|}⊗\eq\lft{\LISPE #|}\cr \funct r5[ {\LISPI (B C D)|} ]⊗ \cons ⊂[\a (D C)].{\funct r5[\cons ⊂B.\funct r5[\d (D C)]⊃]}⊃\cr ⊗\cons ⊂[ D ].{\funct r5[\cons ⊂B.\funct r5[ (C) ]⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[\cons ⊂B.(C)⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[ (B C) ]}⊃\cr ⊗\cons ⊂D.(C B)⊃\cr ⊗\LISPI (D C B)|.\cr}}$$ And finally, we get $$\vcenter{\halign{\lft{\LISPE #|}⊗\eq\lft{\LISPE #|}\cr \funct r5[ {\LISPI (A B C D)|} ] ⊗\cons ⊂[\a (D C B)].{\funct r5[\cons ⊂A.\funct r5[\d (D C B)]⊃]}⊃\cr ⊗\cons ⊂[ D ].{\funct r5[\cons ⊂A.\funct r5[ (C B) ]⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[\cons ⊂A.(B C)⊃]}⊃\cr ⊗\cons ⊂D.{\funct r5[ (A B C) ]}⊃\cr ⊗\cons ⊂D.(C B A)⊃\cr ⊗\LISPI (D C B A)|.\cr}}$$ One could use induction to (informally) prove that \LISPE r5 \eq reverse|, as follows\par \HeadC ⊂Base Step:⊃ \LISPE \n u $∨$ \n{\d u} $\→$ \funct r5[u] \eq u \eq \funct reverse[u]|\par \HeadC ⊂Induction:⊃\par $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct r5[u]⊗\eq \a [r5[\d u]] . r5[\a u . r5[ \d [r5 [\d u]]]\cr ⊗\eq \a [\funct reverse[\d u]] . \funct reverse[\a u . \funct reverse[ \d [\funct reverse [\d u]]]\cr ⊗\eq \list <\a [\funct reverse[\d u]]> * \funct reverse[\list <\a u> * \funct reverse[ \d [\funct reverse [\d u]]]\cr ⊗\eq \list <\a [\funct reverse[\d u]]> * [\funct reverse [\funct reverse[ \d [\funct reverse [\d u]]]]] * \funct reverse[\list <\a u>]\cr ⊗\eq \list <\a [\funct reverse[\d u]]> * [ \d [\funct reverse [\d u]] * \list <\a u> ]\cr ⊗\eq \quad{\rm ; as (1) reverse [reverse x] = x & (2) reverse of singleton < x > is x}\cr ⊗\eq [\list <\a [\funct reverse[\d u]]> * \d [\funct reverse [\d u]] ] * \list <\a u> \cr ⊗\quad{\rm ; by associativity of *}\cr ⊗\eq [\a [\funct reverse[\d u]] . \d [\funct reverse [\d u]] ] * \list <\a u> \cr ⊗\eq \funct reverse[\d u] * \list <\a u> \cr ⊗\eq \funct reverse[u]\cr }}$$ \QUESTION 5\ ([MT]p9 $\#1)$. What is the value of \list < \cons ⊂A . \a {(\cons ⊂B.C⊃)}⊃,\ \cons ⊂D.\d {(\cons ⊂B.C⊃)}⊃>. \ANSWER $$\vcenter{\halign{\lft{\LISPE #|}⊗\eq\lft{\LISPE #|}\cr \list < \cons ⊂A . \a {(\cons ⊂B.C⊃)}⊃,\ \cons ⊂D.\d {(\cons ⊂B.C⊃)}⊃> ⊗\list < \cons ⊂A . B⊃,\ \cons ⊂D.C⊃>\cr ⊗( (A . B) (D . C) )\cr}}$$ \STATEMENT What do the following functions (6-8) do? For each, provide a concise prose answer, a couple of example input/output pairs, and a brief explanation of why/how it works. Are there any restrictions on the arguments (e.g., ``the second argument must be a list of lists'')? \etats \QUESTION 6. $$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|} ⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr (DEFUN ⊗DP⊗(X)⊗⊗\cr ⊗(COND⊗((ATOM X)⊗$0$)⊗\cr ⊗⊗(T⊗(MAX⊗(ADD1 (DP (CAR U)))\cr ⊗⊗⊗⊗(DP (CDR U))))))\cr }}$$ \ANSWER \NOTE we define \LISPE \funct MAX[ x,y ] \assign \if x$>$y \then x \else y| and we define \LISPE ADD1| by \LISPI (DEFUN ADD1 (G) (PLUS $1$ G))|.\eton This function computes the DePth of its argument, viewing this S-expression as a list of lists. Take any atom in this S-expression, and consider the number of ``(''s, ``)''s, and ``.''s in front of it. Their difference (i.e. the number of ``('' minus the number of ``)'' and ``.''s) may be considered the depth of this atom. The maximal depth, over all atoms, is the depth of this S-expression; and is precisely what \LISPE DP| computes. Note: This is NOT the depth of the S-expression, when it is viewed as a binary tree. This defination of depth will depend on the number of members of this list. E.G. The S-expression tree corresponding to \LISPI (1 2 3)| would be of depth $3$, although its \LISPE DP| value is $1$. To get this other depth, write a more symmetric version of \LISPE DP| by adding $1$ to the maximum of the depths of both daughters. [I.E. Change the \LISPI T| clause to \LISPI (ADD1 (MAX (DP (CAR U)) (DP (CDR X))))|.] Examples of output: $$\vcenter{\halign{\lft{\LISPE #|}⊗$\null =#$\cr \funct DP[ (1 (2) ((3)) ) ]⊗3\cr \funct DP[ (1 (2) . ((3)) ) ]⊗2\cr}}$$ \HeadC ⊂Why it works⊃ The depth of a list is the maximal depth of any of its members. That is, it is the depth of a particular member, or the maximal depth of an subsequent entries, whichever is larger. The depth of an element within a list is the depth of that member by itself, plus one, as it is in a list. Knowing that the depth of an atom is $0$, we see why this definition will work. This can take any S-expression as input. \QUESTION 7. $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct ag[u,n,m] \assign \if \n u ⊗\then NIL⊗\cr ⊗\elseif m$\null >1$ ⊗\then \funct ag[\d u,n,m-1]\cr ⊗⊗\else \cons ⊂\a u.\funct ag[\d u,$\,$n,$\,$n]⊃\cr }}$$ \ANSWER This returns every $n↑{th}$ entry of a list, starting from the $m↑{th}$. \HeadC ⊂Why it works⊃ Basically, this function counts down, using its $3↑{rd}$ argument. When this count reaches $0$, the current first element, which is the m$↑{th}$ value of the original list, is \LISPI cons|ed to the result obtained when the remainderhis list is scanned. Here, this $3↑{rd}$ argument is refilled using the value held in the $2↑{nd}$ argument slot. Henceforth, every n$↑{th}$ value will be enterred into the list eventually returned. This ends when the remaining list is \LISPI NIL|. \LISPI u| must be a list, else an error can be expected when that final non-\LISPI NIL| atom is examined. Whenever the first \n u test fails, \LISPI m| will be compared with $1$. If it is not an integer, this $>$ comparison may be undefined. If ever the final \LISPE else| clause is taken, then \LISPI n|'s value will be used. Again, if the \LISPI u| slot here is not null, this \LISPI n| value, now filling \LISPI m|'s role, will be compared with $1$; and so it should have an integer value. \QUESTION 8. \disptext{\LISPE \funct f9[u,v] \assign \if \n u $∨$ \n v \then $0$ \else \a u $\times$ \a v $+$ \funct f9[\d u,\d v]|} \ANSWER This computes the dot product of the vectors \LISPI u| and \LISPI v|. \HeadC ⊂Why is works?⊃ The dot product of two $n$-dimensional vectors is the sum of the product of the first (respective) pair of values, plus the dot product of the pair of $n-1$-dimensional vectors which remain. This is precisely what \LISPE f9| computes. \LISPE u| and \LISPE v| must be lists, whose elements are all numeric. Their relative lengthes are inconsequential, as \LISPE f9| will stop whenever either list terminates. \QUESTION 9. $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct oc[x,u] \assign \if \n u ⊗\then $0$\cr ⊗\else \funct oc[x,\d u] $+$ [\if x\eq \a u \then $1$ \else $0$]\cr }}$$ What is \LISPE \funct oc[ {\LISPI B, (A B C Q B A R)|} ]|? \LISPE \funct oc[ {\LISPI 4, (1 2 (3 4) T)|} ]|? How does \LISPE oc| differ from \LISPE oc2|, defined as follows: $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct oc2[x,u] \assign \if x \eq u ⊗\then $1$⊗\cr ⊗\elseif \at u ⊗\then 0\cr ⊗⊗\else \funct oc2[x,\d u] $+$ \funct oc2[x,\a u]\cr }}$$ \ANSWER \LISPE oc| computes the number of time the first argument occurs in the second. So \LISPE \funct oc[ {\LISPI B, (A B C Q B A R)|} ]| returns $2$, however \LISPE \funct oc[ {\LISPI 4, (1 2 (3 4) T)|} ]| returns $0$, as 4 is not equal to \LISPI 1|, \LISPI 2|, \LISPI (3 4)|, nor \LISPI T|. \LISPE oc2|, however, finds all such occurrences, however deeply buried within the lists. For example, \LISPE \funct oc2[ {\LISPI 4, (1 2 (3 4) T)|} ]| would find the \LISPI 4|, within the \LISPI (3 4)|, and therefore return $1$. Also, \LISPE oc2| can accept any arbitrary S-expressions for \LISPE u|, while \LISPE oc| can only accept lists. \QUESTION 10. Write a function that tells how many corresponding pairs of elements of two lists are equal. Given \LISPI (A B C D E)| and \LISPI (Q B D E E)|, the function should return the value $2$, since second and fifth elements of each list match. Specify this function in external notation, internal notation, and mention any restrictions you have imposed upon the form of the arguments (e.g., what if one is not a list?) \ANSWER In external notation, this is $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct pr[u,v] \assign \if \n u $∨$ \n v ⊗\then $0$\cr ⊗\else \funct pr[\d u,\d v] $+$ [\if \a u \eq \a v \then $1$ \else $0$]\cr }}$$ The \eq we will use is ``\LISPI equal|'', so we may deal with lists whose elements are non-atoms appropriately. This function will be undefined if either of the arguments is, in fact, a (non-\LISPI NIL|) atom. Backing up through the recursion, this means if the shorter list is not a list, \LISPE pr| will eventually blow up. The internal form follows: $$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr (DEFUN ⊗PR(U V)⊗⊗\cr ⊗(COND⊗((OR (NULL U) (NULL V) )⊗0)\cr ⊗⊗((EQUAL (CAR U) (CAR V))⊗(ADD1 (PR (CDR U) (CDR V))))\cr ⊗⊗(T⊗(PR (CDR U) (CDR V)))))\cr }}$$ \QUESTION 11\ (Optional). Write a function that eliminates multiple occurrences of all elements from a list. The {\sl final} occurrence of each element remains. Thus, its value for the list \LISPI (R C A B D C D B A R B)| should be \LISPI (C D A R B)|. Hint: You can define an auxilary function of 2 arguments, which transfers elements of one list onto a second list, and checks to see if the element is there already before transferring it. Hint: you may want to call upon the REVERSE function one or more times. Hint: you may wish to use the EQUAL function instead of the EQ functin, since sometimes the elements may not all be atoms. \ANSWER There are several acceptable solutions, most of which essentially ignore the ``helpful'' hints. The single function \LISPE final| is perhaps the most elegant solution: $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct final[u]\eq \if \n u ⊗\then NIL⊗\cr ⊗\elseif \a u $\in$ \d u ⊗\then \funct final[\d u]\cr ⊗⊗\else \cons ⊂\a u.\funct final[\d u]⊃\cr }}$$ (This uses the membership predicate, ``$\in$,'' defined in [MT].) In internal notation, \LISPI FINAL| can be declared: $$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr (DEFUN⊗FINAL(U)⊗⊗\cr ⊗(COND⊗((NULL U)⊗NIL)\cr ⊗⊗((MEMBER (CAR U) (CDR U))⊗(FINAL (CDR U)))\cr ⊗⊗(T⊗(CONS (CAR U) (FINAL (CDR U))))))\cr }}$$ This function does take $O( n↑2 )$ time, when $n = \null$the number of elements in this list. It is fairly easy to compose other functions which require only $O( nm )$ time, e.g. for $m = \null$the number of distinct elements. $$\vcenter{\halign{\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}⊗\lft{\LISPE #|}\cr \funct FNL[u] ⊗\eq \funct First[{\funct reverse [u]},$\,$NIL]⊗⊗\cr \funct First[u,v] ⊗\eq \if \n u ⊗\then NIL\cr ⊗⊗\elseif u $\in$ v ⊗\then \funct FIRST[ \d u,v ]\cr ⊗⊗⊗\else \funct FIRST[ \d u,\ \cons ⊂\a u.v⊃ ]\cr }}$$ This could even be done in $O( n \log n )$ time, by first sorting the list, then checking adjacent pairs for equality, (and deleting the first element if this condition holds,) then ``unsorting'' back to the original order. \par\vfill\eject \end