<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 "merge-neighbors" 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 "merge-all-neighbors" to do the job. Also, since "merge-all-neighbors" 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'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't really understand the basics of generative recursion. I need to back up. Even if the solution "works," I'm not really interested in it if it's not functioning as an instance of generative recursion. <br>
<br><span class="Apple-style-span" style="font-style: italic;">"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." </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 "merging" from "appending." Once I got that straight, I understood the goal of the "merge-all-neighbors." 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 "merge-all-neighbors" 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 "merge-all-neighbors" 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'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't exist in it'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'm not very encouraged by the fact I'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'm trying very hard to understand how basic algorithms are designed, but it'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 <<a href="mailto:matthias@ccs.neu.edu">matthias@ccs.neu.edu</a>> wrote:<br>><br>> Why should merge-neighbors call merge-all-neighbors? <br>
> How many generative recursions do you think a program such as merge-sort should use? More than one is extremely rare. <br>> Having said that, I guess the description of the algorithm doesn't bring out the process as much as I hoped for. How would this work for you: <br>
> "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." <br>
><br>> On Mar 22, 2009, at 2:19 PM, David Yrueta wrote:<br>><br>> Thank you all for your responses. <br>> Borrowing the "merge" function already developed and tested in Chapter 17, I came up with the version of "merge-all-neighbors" copied below. <br>
> It seems to work, although the second clause of "merge-all-neighbors" troubles me --<br>><br>> [else (merge-neighbors (first lolon) (rest lolon))]))<br>><br>> -- because it doesn't recur on (rest lolon) with "merge-all-neighbors." It makes me think I'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>
> (define (merge-all-neighbors lolon)<br>> (cond<br>> [(empty? (rest lolon)) lolon]<br>> [else (merge-neighbors (first lolon) (merge-all-neighbors (rest lolon)))]))<br>> When I did that, I was surprised to discover that "merge-all-neighbors" behaved almost identically to "merge-sort," which "merge-all-neighbors" is supposed to act as an auxiliary function to:<br>
> 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>> Anyway, thoughts and comments are greatly appreciated. Bottom line: is my version of "merge-all-neighbors" below correct, lucky, or wrong (meaning I've missed test cases)?<br>
> ;Data Definitions<br>> ;A list-of-numbers (lon) is either<br>> ;1 empty, or<br>> ;2 (cons n lon) where n is a number<br>> ;A list-of-list-of-numbers (lolon) is either<br>> ;1. (cons lon empty), or<br>
> ;2. (cons lon lolon) where lon is a list-of-numbers<br>
> ;merge-all-neighbors : (listof (listof numbers)) -> (listof (listof numbers))<br>> ;consumes a lolon, returns a merged lolon; to merge two lists means to append them in ascending order<br>> ;(check-expect (merge-all-neighbors (list empty)) (list empty))<br>
> ;(check-expect (merge-all-neighbors (list (list 2 5))) (list (list 2 5)))<br>> ;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9))) (list (list 2 3 5 9)))<br>> ;(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>
> ;(check-expect (merge-all-neighbors (list (list 2) (list 5) (list 9) (list 3))) (list (list 2 5) (list 3 9)))<br>> (define (merge-all-neighbors lolon)<br>> (cond<br>> [(empty? (rest lolon)) lolon]<br>
> [else (merge-neighbors (first lolon) (rest lolon))]))<br>
> ;merge-neighbors : (listof numbers) (listof (listof numbers)) -> (listof (listof numbers))<br>> ;consumes a lon and a lolon; returns a lolon with the lon merged with the first lon from the lolon<br>> ;(check-expect (merge-neighbors (list 1 3) (list (list 2 4))) (list (list 1 2 3 4)))<br>
> ;(check-expect (merge-neighbors (list 2 4) (list (list 1 3))) (list (list 1 2 3 4)))<br>> ;(check-expect (merge-neighbors (list 1 3) (list (list 2 4)(list 5 7))) (list(list 1 2 3 4)(list 5 7)))<br>> ;(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>
> (define (merge-neighbors lon lolon)<br>> (cond<br>> [(empty? (rest lolon))<br>> (list (merge lon (first lolon)))]<br>> [else (cons (merge lon (first lolon))<br>> (merge-all-neighbors (rest lolon)))]))<br>
> ;merge : (listof numbers) (listof numbers) -> (listof numbers)<br>> ;consumes two lon sorted in ascending order, returns a single lon sorted in ascending order<br>> ;(check-expect (merge empty (list 1 3)) (list 1 3))<br>
> ;(check-expect (merge (list 1 3) empty) (list 1 3))<br>> ;(check-expect (merge (list 1 3) (list 2 4 5)) (list 1 2 3 4 5))<br>> ;(check-expect (merge (list 2 4 5) (list 1 3)) (list 1 2 3 4 5))<br>> (define(merge alon1 alon2)<br>
> (cond<br>> [(and(empty? alon1)(empty? alon2))empty]<br>> [(empty? alon1)(cons(first alon2)(merge alon1 (rest alon2)))]<br>> [(empty? alon2)(cons (first alon1)(merge (rest alon1) alon2))]<br>> [else<br>
> (cond<br>> [(<=(first alon1)(first alon2))(cons (first alon1)(merge(rest alon1) alon2))]<br>> [else(cons(first alon2)(merge alon1 (rest alon2)))])]))<br>> Thanks!<br>> Dave Yrueta<br>
><br>><br>><br>><br>><br>><br>> On Sun, Mar 22, 2009 at 7:34 AM, Marco Morazan <<a href="mailto:morazanm@gmail.com">morazanm@gmail.com</a>> wrote:<br>>><br>>> On Sat, Mar 21, 2009 at 7:50 PM, David Yrueta <<a href="mailto:dyrueta@gmail.com">dyrueta@gmail.com</a>> wrote:<br>
>> > How can this accomplished --<br>>> > (check-expect (merge-all-neighbors (list (list 9) (list 1))) (list (list 1<br>>> > 9)))?<br>>> ><br>>> > -- without some sorting going on within "merge-all-neighbors"?<br>
>><br>>> Your function, merge-all-neighbors, needs to process two pieces of<br>>> data of arbitrary size. You need to decide how both pieces of data<br>>> have to be processed. Do you only need to traverse one list at a time?<br>
>> Do you need to traverse both lists at the same time?<br>>><br>>> There is also an assumption that you seem to not have picked up. In<br>>> addition to being (listof number), what other property should you<br>
>> assume each of the inputs has? Is (merge-all-neighbors (list 2 1)<br>>> (list 8 9)) a "legal" application of merge-all-neighbors to two lists<br>>> of numbers?<br>>><br>>> After figuring out the above, I suggest you think about how<br>
>> (merge-all-neighbors (list 2 8 9) (list 1 3 7 10)) can yield (list1 2<br>>> 3 7 8 9 10). This should tell you how the inputs need to be processed.<br>>><br>>><br>>> --<br>>><br>>> Cheers,<br>
>><br>>> Marco<br>><br>><br><br></div>