<span class="Apple-style-span" style="font-style: italic;">Why should merge-neighbors call merge-all-neighbors?</span><br><br>That design decision was driven partly by reason, partly by necessity.  Since the first condition of &quot;merge-neighbors&quot; disposes of (lon) and (first lolon) by merging them, something needs to be done with (rest lolon).  The lists contained in (rest lolon) are un-merged, and so it seemed reasonable to send them back to &quot;merge-all-neighbors&quot; to do the job.  Also, since &quot;merge-all-neighbors&quot; is the only function which accepts a single (listof (listof numbers)) argument, it seemed necessary to do so. Bad reason, I admit, but I couldn&#39;t think of anything else. <br>

<br><span class="Apple-style-span" style="font-style: italic;">How many generative recursions do you think a program such as merge-sort should use? More than one is extremely rare.</span> <br><br>I have no idea.  I think the problem is that I don&#39;t really understand the basics of generative recursion.  I need to back up.  Even if the solution &quot;works,&quot; I&#39;m not really interested in it if it&#39;s not functioning as an instance of generative recursion.  <br>

<br><span class="Apple-style-span" style="font-style: italic;">&quot;The function merge-all-neighbors merges the items on the given list in a pair-wise fashion: the first and second, the third and the fourth, etc. The function merge uses merge-all-neighbors until there is only one list left on the list.&quot; </span><br>

<br>This is helpful, although I believe you could reasonably expect a student to intuit it from the book examples.  My initial problem was failing to distinguish &quot;merging&quot; from &quot;appending.&quot;  Once I got that straight, I understood the goal of the &quot;merge-all-neighbors.&quot;  I was hoping my (check-expect....) examples made that clear.  <br>

<br><div>Let me start with the design recipe for generative recursion from HtDP:<br><br>(define (generative-recursive-fun problem)<br>  (cond<br>    [(trivially-solvable? problem)<br>     (determine-solution problem)]<br>

    [else<br>     (combine-solutions<br>       ... problem ...<br>       (generative-recursive-fun (generate-problem-1 problem))<br>       <br>       (generative-recursive-fun (generate-problem-n problem)))]))<br></div><div>

<span class="Apple-style-span" style="font-style: italic; "> </span></div><div>Start the design with a trivially solvable problem, which in this case (I believe) is a (listof (listof numbers)) consisting of only a single (listof numbers)). </div>

<div><span class="Apple-style-span" style="font-style: italic;"><br></span><span class="Apple-style-span" style="font-weight: bold;">(define (merge-all-neighbors a-lolon)</span></div><div><span class="Apple-style-span" style="font-weight: bold;">    (cond</span></div>

<div><span class="Apple-style-span" style="font-weight: bold;">        [(empty? (rest a-lolon)) a-lolon]</span></div><div><span class="Apple-style-span" style="font-weight: bold;">        [else...</span></div><div>      (combine-solutions<br>

      ... problem ...<br>      (generative-recursive-fun (generate-problem-1 problem))<br>      <br>      (generative-recursive-fun (generate-problem-n problem)))]))</div><div><br></div><div>The next thing to do is to merge pairs, or the first and second lists in a-lolon.  The only way I can imagine doing that is by merging (first a-lolon) with (first (rest a-lolon)).</div>

<div><br></div><div>But that has to be wrong.  Suppose the value of a-lolon is (list (list 1) (list 2)).  If (first a-lolon) merges with (first (rest a-lolon)), then it forces the &quot;merge-all-neighbors&quot; to recur on (rest (rest a-lolon)).  That would return empty, which is not a trivially-solvable problem.  </div>

<div><br></div><div>The only way around that is for &quot;merge-all-neighbors&quot; to test for (empty? a-lolon).  The final result would look like this --</div><div><br></div><div>(define (merge-all-neighbors a-lolon)</div>

<div>  (cond</div><div>    [(empty? a-lolon) empty]</div><div>    [(empty? (rest a-lolon)) a-lolon]</div><div>    [else </div><div>     (cons (merge (first a-lolon) (first (rest a-lolon)))</div><div>           (merge-all-neighbors (rest (rest a-lolon))))]))</div>

<div><br></div><div>I considered this design possibility earlier because it seems to work, but I&#39;d be shocked if it was right.  It violates too many of conditions of the design recipe by 1) including a possible value for a-lolon that doesn&#39;t exist in it&#39;s data definition, and, 2) not using merge-all-neighbors to recur on (merge (first a-lolon) (first (rest a-lolon))).  </div>

<div><br></div><div>What is my problem?  Where is my blind spot?  I&#39;m not very encouraged by the fact I&#39;ve come up with two poorly designed solutions to what seems like a fairly straight-forward problem.  It makes me feel as though my design compass is broken.  </div>

<div><br></div><div>I&#39;m trying very hard to understand how basic algorithms are designed, but it&#39;s not coming to me.  All help and suggestions are greatly appreciated!</div><div><br></div><div>Thanks for your patience. </div>

<div><br></div><div>Dave Yrueta<br><br>On Sun, Mar 22, 2009 at 12:01 PM, Matthias Felleisen &lt;<a href="mailto:matthias@ccs.neu.edu">matthias@ccs.neu.edu</a>&gt; wrote:<br>&gt;<br>&gt; Why should merge-neighbors call merge-all-neighbors? <br>

&gt; How many generative recursions do you think a program such as merge-sort should use? More than one is extremely rare. <br>&gt; Having said that, I guess the description of the algorithm doesn&#39;t bring out the process as much as I hoped for. How would this work for you: <br>

&gt; &quot;The function merge-all-neighbors merges the items on the given list in a pair-wise fashion: the first and second, the third and the fourth, etc. The function merge uses merge-all-neighbors until there is only one list left on the list.&quot; <br>

&gt;<br>&gt; On Mar 22, 2009, at 2:19 PM, David Yrueta wrote:<br>&gt;<br>&gt; Thank you all for your responses. <br>&gt; Borrowing the &quot;merge&quot; function already developed and tested in Chapter 17, I came up with the version of &quot;merge-all-neighbors&quot; copied below.  <br>

&gt; It seems to work, although the second clause of &quot;merge-all-neighbors&quot; troubles me --<br>&gt;<br>&gt;  [else (merge-neighbors (first lolon) (rest lolon))]))<br>&gt;<br>&gt; -- because it doesn&#39;t recur on (rest lolon) with &quot;merge-all-neighbors.&quot;  It makes me think I&#39;m deviating from the design recipe.  On my first pass, when I thought I was strictly adhering to the structural recursion template, this is what I came up with --<br>

&gt; (define (merge-all-neighbors lolon)<br>&gt;   (cond<br>&gt;     [(empty? (rest lolon)) lolon]<br>&gt;     [else (merge-neighbors (first lolon) (merge-all-neighbors (rest lolon)))]))<br>&gt; When I did that, I was surprised to discover that &quot;merge-all-neighbors&quot; behaved almost identically to &quot;merge-sort,&quot; which &quot;merge-all-neighbors&quot; is supposed to act as an auxiliary function to:<br>

&gt; In this case, (merge-all-neighbors (list (list 5) (list 4) (list 3) (list 2)) returns (list (list 2 3 4 5)), which was not my intention, but seemed productive.  <br>&gt; Anyway, thoughts and comments are greatly appreciated.  Bottom line: is my version of &quot;merge-all-neighbors&quot; below correct, lucky, or wrong (meaning I&#39;ve missed test cases)?<br>

&gt; ;Data Definitions<br>&gt; ;A list-of-numbers (lon) is either<br>&gt; ;1 empty, or<br>&gt; ;2 (cons n lon) where n is a number<br>&gt; ;A list-of-list-of-numbers (lolon) is either<br>&gt; ;1. (cons lon empty), or<br>
&gt; ;2. (cons lon lolon) where lon is a list-of-numbers<br>
&gt; ;merge-all-neighbors : (listof (listof numbers)) -&gt; (listof (listof numbers))<br>&gt; ;consumes a lolon, returns a merged lolon; to merge two lists means to append them in ascending order<br>&gt; ;(check-expect (merge-all-neighbors (list empty)) (list empty))<br>

&gt; ;(check-expect (merge-all-neighbors (list (list 2 5))) (list (list 2 5)))<br>&gt; ;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9))) (list (list 2 3 5 9)))<br>&gt; ;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9) (list 4 8))) (list (list 2 3 5 9) (list 4 8)))<br>

&gt; ;(check-expect (merge-all-neighbors (list (list 2) (list 5) (list 9) (list 3))) (list (list 2 5) (list 3 9)))<br>&gt; (define (merge-all-neighbors lolon)<br>&gt;   (cond<br>&gt;     [(empty? (rest lolon)) lolon]<br>
&gt;     [else (merge-neighbors (first lolon) (rest lolon))]))<br>
&gt; ;merge-neighbors : (listof numbers) (listof (listof numbers)) -&gt; (listof (listof numbers))<br>&gt; ;consumes a lon and a lolon; returns a lolon with the lon merged with the first lon from the lolon<br>&gt; ;(check-expect (merge-neighbors (list 1 3) (list (list 2 4))) (list (list 1 2 3 4)))<br>

&gt; ;(check-expect (merge-neighbors (list 2 4) (list (list 1 3))) (list (list 1 2 3 4)))<br>&gt; ;(check-expect (merge-neighbors (list 1 3) (list (list 2 4)(list 5 7))) (list(list 1 2 3 4)(list 5 7)))<br>&gt; ;(check-expect (merge-neighbors (list 2 5) (list (list 1 3 4) (list 6 7))) (list (list 1 2 3 4 5) (list 6 7)))<br>

&gt; (define (merge-neighbors lon lolon)<br>&gt;   (cond<br>&gt;     [(empty? (rest lolon))<br>&gt;      (list (merge lon (first lolon)))]<br>&gt;     [else (cons (merge lon (first lolon))<br>&gt;                 (merge-all-neighbors (rest lolon)))]))<br>

&gt; ;merge : (listof numbers) (listof numbers) -&gt; (listof numbers)<br>&gt; ;consumes two lon sorted in ascending order, returns a single lon sorted in ascending order<br>&gt; ;(check-expect (merge empty (list 1 3)) (list 1 3))<br>

&gt; ;(check-expect (merge (list 1 3) empty) (list 1 3))<br>&gt; ;(check-expect (merge (list 1 3) (list 2 4 5)) (list 1 2 3 4 5))<br>&gt; ;(check-expect (merge (list 2 4 5) (list 1 3)) (list 1 2 3 4 5))<br>&gt; (define(merge alon1 alon2)<br>

&gt;   (cond<br>&gt;     [(and(empty? alon1)(empty? alon2))empty]<br>&gt;     [(empty? alon1)(cons(first alon2)(merge alon1 (rest alon2)))]<br>&gt;     [(empty? alon2)(cons (first alon1)(merge (rest alon1) alon2))]<br>&gt;     [else<br>

&gt;      (cond<br>&gt;        [(&lt;=(first alon1)(first alon2))(cons (first alon1)(merge(rest alon1) alon2))]<br>&gt;        [else(cons(first alon2)(merge alon1 (rest alon2)))])]))<br>&gt; Thanks!<br>&gt; Dave Yrueta<br>

&gt;<br>&gt;<br>&gt;<br>&gt;<br>&gt;<br>&gt;<br>&gt; On Sun, Mar 22, 2009 at 7:34 AM, Marco Morazan &lt;<a href="mailto:morazanm@gmail.com">morazanm@gmail.com</a>&gt; wrote:<br>&gt;&gt;<br>&gt;&gt; On Sat, Mar 21, 2009 at 7:50 PM, David Yrueta &lt;<a href="mailto:dyrueta@gmail.com">dyrueta@gmail.com</a>&gt; wrote:<br>

&gt;&gt; &gt; How can this accomplished --<br>&gt;&gt; &gt; (check-expect (merge-all-neighbors (list (list 9) (list 1))) (list (list 1<br>&gt;&gt; &gt; 9)))?<br>&gt;&gt; &gt;<br>&gt;&gt; &gt; -- without some sorting going on within &quot;merge-all-neighbors&quot;?<br>

&gt;&gt;<br>&gt;&gt; Your function, merge-all-neighbors, needs to process two pieces of<br>&gt;&gt; data of arbitrary size. You need to decide how both pieces of data<br>&gt;&gt; have to be processed. Do you only need to traverse one list at a time?<br>

&gt;&gt; Do you need to traverse both lists at the same time?<br>&gt;&gt;<br>&gt;&gt; There is also an assumption that you seem to not have picked up. In<br>&gt;&gt; addition to being (listof number), what other property should you<br>

&gt;&gt; assume each of the inputs has? Is (merge-all-neighbors (list 2 1)<br>&gt;&gt; (list 8 9)) a &quot;legal&quot; application of merge-all-neighbors to two lists<br>&gt;&gt; of numbers?<br>&gt;&gt;<br>&gt;&gt; After figuring out the above, I suggest you think about how<br>

&gt;&gt; (merge-all-neighbors (list 2 8 9) (list 1 3 7 10)) can yield (list1 2<br>&gt;&gt; 3 7 8 9 10). This should tell you how the inputs need to be processed.<br>&gt;&gt;<br>&gt;&gt;<br>&gt;&gt; --<br>&gt;&gt;<br>&gt;&gt; Cheers,<br>

&gt;&gt;<br>&gt;&gt; Marco<br>&gt;<br>&gt;<br><br></div>