[plt-scheme] HtDP 26.1.2

Thank you all for your responses.
Borrowing the "merge" function already developed and tested in Chapter 17, I
came up with the version of "merge-all-neighbors" copied below.

It seems to work, although the second clause of "merge-all-neighbors"
troubles me --

 [else (merge-neighbors (first lolon) (rest lolon))]))

-- 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 --

(define (merge-all-neighbors lolon)
  (cond
    [(empty? (rest lolon)) lolon]
    [else (merge-neighbors (first lolon) (merge-all-neighbors
(rest lolon)))]))

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:

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.

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)?

;Data Definitions
;A list-of-numbers (lon) is either
;1 empty, or
;2 (cons n lon) where n is a number

;A list-of-list-of-numbers (lolon) is either
;1. (cons lon empty), or
;2. (cons lon lolon) where lon is a list-of-numbers

;merge-all-neighbors : (listof (listof numbers)) -> (listof (listof
numbers))
;consumes a lolon, returns a merged lolon; to merge two lists means to
append them in ascending order
;(check-expect (merge-all-neighbors (list empty)) (list empty))
;(check-expect (merge-all-neighbors (list (list 2 5))) (list (list 2 5)))
;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9))) (list
(list 2 3 5 9)))
;(check-expect (merge-all-neighbors (list (list 2 5) (list 3 9) (list 4 8)))
(list (list 2 3 5 9) (list 4 8)))
;(check-expect (merge-all-neighbors (list (list 2) (list 5) (list 9) (list
3))) (list (list 2 5) (list 3 9)))
(define (merge-all-neighbors lolon)
  (cond
    [(empty? (rest lolon)) lolon]
    [else (merge-neighbors (first lolon) (rest lolon))]))

;merge-neighbors : (listof numbers) (listof (listof numbers)) -> (listof
(listof numbers))
;consumes a lon and a lolon; returns a lolon with the lon merged with the
first lon from the lolon
;(check-expect (merge-neighbors (list 1 3) (list (list 2 4))) (list (list 1
2 3 4)))
;(check-expect (merge-neighbors (list 2 4) (list (list 1 3))) (list (list 1
2 3 4)))
;(check-expect (merge-neighbors (list 1 3) (list (list 2 4)(list 5 7)))
(list(list 1 2 3 4)(list 5 7)))
;(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)))
(define (merge-neighbors lon lolon)
  (cond
    [(empty? (rest lolon))
     (list (merge lon (first lolon)))]
    [else (cons (merge lon (first lolon))
                (merge-all-neighbors (rest lolon)))]))

;merge : (listof numbers) (listof numbers) -> (listof numbers)
;consumes two lon sorted in ascending order, returns a single lon sorted in
ascending order
;(check-expect (merge empty (list 1 3)) (list 1 3))
;(check-expect (merge (list 1 3) empty) (list 1 3))
;(check-expect (merge (list 1 3) (list 2 4 5)) (list 1 2 3 4 5))
;(check-expect (merge (list 2 4 5) (list 1 3)) (list 1 2 3 4 5))
(define(merge alon1 alon2)
  (cond
    [(and(empty? alon1)(empty? alon2))empty]
    [(empty? alon1)(cons(first alon2)(merge alon1 (rest alon2)))]
    [(empty? alon2)(cons (first alon1)(merge (rest alon1) alon2))]
    [else
     (cond
       [(<=(first alon1)(first alon2))(cons (first alon1)(merge(rest alon1)
alon2))]
       [else(cons(first alon2)(merge alon1 (rest alon2)))])]))

Thanks!
Dave Yrueta







On Sun, Mar 22, 2009 at 7:34 AM, Marco Morazan <morazanm at gmail.com> wrote:

> On Sat, Mar 21, 2009 at 7:50 PM, David Yrueta <dyrueta at gmail.com> wrote:
> > How can this accomplished --
> > (check-expect (merge-all-neighbors (list (list 9) (list 1))) (list (list
> 1
> > 9)))?
> >
> > -- without some sorting going on within "merge-all-neighbors"?
>
> Your function, merge-all-neighbors, needs to process two pieces of
> data of arbitrary size. You need to decide how both pieces of data
> have to be processed. Do you only need to traverse one list at a time?
> Do you need to traverse both lists at the same time?
>
> There is also an assumption that you seem to not have picked up. In
> addition to being (listof number), what other property should you
> assume each of the inputs has? Is (merge-all-neighbors (list 2 1)
> (list 8 9)) a "legal" application of merge-all-neighbors to two lists
> of numbers?
>
> After figuring out the above, I suggest you think about how
> (merge-all-neighbors (list 2 8 9) (list 1 3 7 10)) can yield (list1 2
> 3 7 8 9 10). This should tell you how the inputs need to be processed.
>
>
> --
>
> Cheers,
>
> Marco
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090322/b51617cf/attachment.html>