<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "> <div><br></div><div>Why should merge-neighbors call merge-all-neighbors? </div><div><br></div><div>How many generative recursions do you think a program such as merge-sort should use? More than one is extremely rare. </div><div><br></div><div>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: </div><div><br></div><div>"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." </div><div><br></div><br><div><div>On Mar 22, 2009, at 2:19 PM, David Yrueta wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Thank you all for your responses. <div><br></div><div>Borrowing the "merge" function already developed and tested in Chapter 17, I came up with the version of "merge-all-neighbors" copied below. </div> <div><br></div><div><div>It seems to work, although the second clause of "merge-all-neighbors" troubles me --<br></div><div><br></div><div> [else (merge-neighbors (first lolon) (rest lolon))]))<br></div><div><br> </div><div>-- 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 --</div> <div><br></div><div><div>(define (merge-all-neighbors lolon)</div><div> (cond</div><div> [(empty? (rest lolon)) lolon]</div><div> [else (merge-neighbors (first lolon) (merge-all-neighbors (rest lolon)))]))</div><div> <br></div><div>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:</div> <div><br></div><div>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. </div><div><br></div><div>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)?</div> <div><br></div></div></div><div><div>;Data Definitions</div><div>;A list-of-numbers (lon) is either</div><div>;1 empty, or</div><div>;2 (cons n lon) where n is a number</div><div><br></div><div>;A list-of-list-of-numbers (lolon) is either</div> <div>;1. (cons lon empty), or</div><div>;2. (cons lon lolon) where lon is a list-of-numbers</div><div><br></div><div>;merge-all-neighbors : (listof (listof numbers)) -> (listof (listof numbers))</div><div>;consumes a lolon, returns a merged lolon; to merge two lists means to append them in ascending order</div> <div>;(check-expect (merge-all-neighbors (list empty)) (list empty))</div><div>;(check-expect (merge-all-neighbors (list (list 2 5))) (list (list 2 5)))</div><div>;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9))) (list (list 2 3 5 9)))</div> <div>;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9) (list 4 8))) (list (list 2 3 5 9) (list 4 8)))</div><div>;(check-expect (merge-all-neighbors (list (list 2) (list 5) (list 9) (list 3))) (list (list 2 5) (list 3 9)))</div> <div>(define (merge-all-neighbors lolon)</div><div> (cond</div><div> [(empty? (rest lolon)) lolon]</div><div> [else (merge-neighbors (first lolon) (rest lolon))]))</div><div><br></div><div>;merge-neighbors : (listof numbers) (listof (listof numbers)) -> (listof (listof numbers))</div> <div>;consumes a lon and a lolon; returns a lolon with the lon merged with the first lon from the lolon</div><div>;(check-expect (merge-neighbors (list 1 3) (list (list 2 4))) (list (list 1 2 3 4)))</div><div>;(check-expect (merge-neighbors (list 2 4) (list (list 1 3))) (list (list 1 2 3 4)))</div> <div>;(check-expect (merge-neighbors (list 1 3) (list (list 2 4)(list 5 7))) (list(list 1 2 3 4)(list 5 7)))</div><div>;(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)))</div> <div>(define (merge-neighbors lon lolon)</div><div> (cond</div><div> [(empty? (rest lolon))</div><div> (list (merge lon (first lolon)))]</div><div> [else (cons (merge lon (first lolon))</div><div> (merge-all-neighbors (rest lolon)))]))</div> <div><br></div><div><div><div>;merge : (listof numbers) (listof numbers) -> (listof numbers)</div><div>;consumes two lon sorted in ascending order, returns a single lon sorted in ascending order</div><div>;(check-expect (merge empty (list 1 3)) (list 1 3))</div> <div>;(check-expect (merge (list 1 3) empty) (list 1 3))</div><div>;(check-expect (merge (list 1 3) (list 2 4 5)) (list 1 2 3 4 5))</div><div>;(check-expect (merge (list 2 4 5) (list 1 3)) (list 1 2 3 4 5))</div><div>(define(merge alon1 alon2)</div> <div> (cond</div><div> [(and(empty? alon1)(empty? alon2))empty]</div><div> [(empty? alon1)(cons(first alon2)(merge alon1 (rest alon2)))]</div><div> [(empty? alon2)(cons (first alon1)(merge (rest alon1) alon2))]</div> <div> [else</div><div> (cond</div><div> [(<=(first alon1)(first alon2))(cons (first alon1)(merge(rest alon1) alon2))]</div><div> [else(cons(first alon2)(merge alon1 (rest alon2)))])]))</div><div><br> </div></div></div><div><div>Thanks!</div><div>Dave Yrueta</div><div><br></div><div><br></div></div><div><br></div><div><br></div></div><div><br></div><div><br><br><div class="gmail_quote">On Sun, Mar 22, 2009 at 7:34 AM, Marco Morazan <span dir="ltr"><<a href="mailto:morazanm@gmail.com">morazanm@gmail.com</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">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> </div>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> <font color="#888888"><br> Marco<br> </font></blockquote></div><br></div></blockquote></div><br></body></html>