🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to SICP Workshop

Chapter 2

Muhammad Haggag · 2007-07-01T13:14:05

Chapter 2 discussions go here. EDIT: Removed time period from title. [Edited by - Muhammad Haggag on April 8, 2007 1:45:33 AM]

SICP Workshop Workshops

Started by Muhammad Haggag January 01, 2007 07:33 AM

40 comments, last by SamLowry 17 years ago

SamLowry

1,865

May 08, 2007 04:44 PM

deep-reverse

I'd say your solution is efficient but inelegant. It looks like you have inlined several abstraction levels into one. I would use an intermediate function, map.

(define (deep-reverse x)  (if (list? x)      (reverse (map deep-reverse x))      x))

My solution isn't very efficient, and it works on non-lists also, which may not be what we want, but it can be fixed easily.

map and reduce (also known as fold) come in handy often when working with lists. I should make some exercises about these functions.

fringe
Same remarks as above.

(define (fringe x)  (if (list? x)      (apply append (map fringe x))      (list x)))

Elegance is in the eye of the beholder I'd say :)

[Edited by - SamLowry on May 8, 2007 5:44:09 PM]

Muhammad Haggag

1,358

Author

May 08, 2007 10:21 PM

Quote: Original post by SamLowry
deep-reverse

I'd say your solution is efficient but inelegant. It looks like you have inlined several abstraction levels into one. I would use an intermediate function, map.

[snip

Thanks, that's exactly what I was looking for. Your comment on inlined abstraction levels nailed it--that's what I've been unhappy about, but unable to pinpoint.

Ezbez

1,164

May 09, 2007 02:18 PM

Sam Lowry, I'd like some exercises on map. I don't quite get what it does; it just seems to work. [grin]

[Edit: fixed "Lowery". Sorry Sam]

[Edited by - Ezbez on May 9, 2007 5:18:04 PM]

Rebooted

612

May 09, 2007 02:53 PM

I agree with Sam that it is important to learn how to use the common higher-order functions effectively, particularly map and fold (and unfold). These 3 functions have a strong theoretical basis and so between them they are known to cover a wide class of problems. They also communicate intent more effectively than hand-written recursion, and have nice properties like guaranteed termination.

Quote: Original post by Ezbez
Sam Lowery, I'd like some exercises on map. I don't quite get what it does; it just seems to work. [grin]

map takes a function and a list as arguments, and gives another list.

It applies the function to each element of the list, and puts the result of each application into the new list.

For example:

(define (inc n)  (+ n 1))(define (id x) x); this gives the list (2 3 4)(map inc (list 1 2 3)); this gives the original list unaltered(map id (list 1 2 3))

Fold explanation coming. A good starting example might be to write factorial using fold. You will probably have to enter (require (lib "list.ss")) in MzScheme language mode to load in the defintions of foldr and foldl.

[Edited by - Rebooted on May 9, 2007 3:53:44 PM]

Ezbez

1,164

May 09, 2007 05:04 PM

Hm. Map is still causing me conceptual problems. For example, why does mapping Rebooted's inc function (eg: (map inc my-list))) works while Sam's functions both need to do list? tests.

Edit:

Oh! I see now! (map inc my-list) only works because I used a list not a tree! I believe I now understand map: it applies the function to all of the elements of the list it's passed - I thought it applied them to the leaves of the tree if it was given a tree. I'd still like an exercise or two to help solidify the concept, if you're still up on that offer, Sam (or anyone!). And I'm looking forward to the fold information.

SamLowry

1,865

May 09, 2007 05:38 PM

I've created a separate thread for the map and fold stuff.
Allen daarheen.

Rebooted

612

May 10, 2007 03:52 AM

Quote: Original post by Ezbez
Oh! I see now! (map inc my-list) only works because I used a list not a tree! I believe I now understand map: it applies the function to all of the elements of the list it's passed - I thought it applied them to the leaves of the tree if it was given a tree.

The function commonly called map works on lists. There is a corresponding map-tree function for trees too - see the new thread SamLowry has started. Every inductive datatype has its own map and fold functions.

Muhammad Haggag

1,358

Author

June 24, 2007 09:46 AM

These are my solutions to 2.29. Again, I feel they're not elegant enough. Specifically, branch-structure and mobile-balanced? look really kludgy.

(define (make-mobile left right)  (list left right))(define (make-branch length structure)  (list length structure))(define (left-branch mobile)  (car mobile))(define (right-branch mobile)  (cadr mobile))(define (branch-length branch)  (car branch))(define (branch-structure branch)  (let ((tail (cdr branch)))    (if (= (length tail) 1)        (car tail)        tail)))  (define (branch-weight branch)  (if (list? (branch-structure branch))      (total-weight (branch-structure branch))      (branch-structure branch)))(define (total-weight mobile)  (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile))))(define (mobile-balanced? mobile)  (let ((lb (left-branch mobile))        (rb (right-branch mobile)))    (and (= (branch-torque lb) (branch-torque rb))        (if (list? (branch-structure lb))            (mobile-balanced? (branch-structure lb))            #t)        (if (list? (branch-structure rb))            (mobile-balanced? (branch-structure rb))            #t))))                   (define (branch-torque branch)  (* (branch-length branch) (branch-weight branch)))(define A  (make-mobile   (make-branch 5 10)   (make-branch 5                (make-mobile (make-branch 2 5) (make-branch 2 5)))))(mobile-balanced? A)

The solution for 2.29-d (replacing lists with cons cells, i.e. list with cons and list? with pair?):

(define (make-mobile left right)  (cons left right))(define (make-branch length structure)  (cons length structure))(define (left-branch mobile)  (car mobile))(define (right-branch mobile)  (cdr mobile))(define (branch-length branch)  (car branch))(define (branch-structure branch) (cdr branch))  (define (branch-weight branch)  (if (pair? (branch-structure branch))      (total-weight (branch-structure branch))      (branch-structure branch)))(define (total-weight mobile)  (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile))))(define (mobile-balanced? mobile)  (let ((lb (left-branch mobile))        (rb (right-branch mobile)))    (and (= (branch-torque lb) (branch-torque rb))        (if (pair? (branch-structure lb))            (mobile-balanced? (branch-structure lb))            #t)        (if (pair? (branch-structure rb))            (mobile-balanced? (branch-structure rb))            #t))))                   (define (branch-torque branch)  (* (branch-length branch) (branch-weight branch)))(define A  (make-mobile   (make-branch 5 10)   (make-branch 5                (make-mobile (make-branch 2 5) (make-branch 2 5)))))(mobile-balanced? A)

SamLowry

1,865

June 24, 2007 02:15 PM

Quote: Original post by Muhammad Haggag
These are my solutions to 2.29. Again, I feel they're not elegant enough. Specifically, branch-structure and mobile-balanced? look really kludgy.

*** Source Snippet Removed ***

The solution for 2.29-d (replacing lists with cons cells, i.e. list with cons and list? with pair?):
*** Source Snippet Removed ***

Detail: a function

(define (left-branch mobile)  (car mobile))

can also be defined as

(define left-branch car)

If find your definition of branch-structure suspect: if the constructor looks like (list x1 x2), the accessors should be no more complex than car and cadr. Also, as all branches you create are lists of length 2, the check does not do anything, as the cdr of a 2-item list will always have length 1.

I don't like branch-weight too much, it breaks the layers of abstraction. The lowest abstraction layer consists of the constructors and accessors, and higher level functions built upon this lowest layer should never know about the internals. In your case, you know that you have to use list? in order to know if a structure is a number or another mobile.
I would add predicate functions in the lowest layer to avoid this: number-structure? and mobile-structure?. Notice what these predicates actually do: given a structure (important precondition), they will be able to identify if it is either a number or a mobile. I don't really like this, as I could give it a branch and it'd return #t without complaining. You can avoid this by adding type tags, e.g. the constructor becomes (list 'mobile left-branch right-branch), but that would be deviating from the exercise.

Same criticism applies on mobile-balanced?.
Also, you can make it a bit more elegant also by noticing that (if cond a #t) is the same as (or (not cond) a), which in your case would result in

(or (number? (branch-structure lb))    (mobile-balanced? (branch-structure lb)))

or more abstract

(or (number-structure? (branch-structure lb))    (mobile-balanced? (branch-structure lb)))

Part d of the exercise: changing the representation ought only to have repercussion on the lowest level (constructors, accessors, predicates). This is not the case in your code as branch-weight and mobile-balanced? had to be modified.

Try to stratify your code as much as you can, in any language. It really helps a lot.

[Edited by - SamLowry on June 24, 2007 2:15:30 PM]

Muhammad Haggag

1,358

Author

July 01, 2007 12:19 PM

Exercise 2.35 is about writing a count-leaves procedure as an accumulation operation. I wrote a recursive solution as follows:

(define (count-leaves tree)  (accumulate + 0 (map                   (lambda (t)                     (cond ((null? t) 0)                           ((not (pair? t)) 1)                           (else (count-leaves t))))                   tree)))

Is it possible to get away with a simpler solution? (Not that this one is complex--it isn't. Just wondering)

Also, I'm somewhat surprised that I didn't find a standard 'accumulate' or 'filter' in R5RS Scheme. I tried searching MzScheme, and I found 'filter' variants, but no 'accumulate'. Is there another popular name for 'accumulate'?

🎉 Celebrating 25 Years of GameDev.net! 🎉

Chapter 2

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

🎉 Celebrating 25 Years of GameDev.net! 🎉

Chapter 2

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines