Sign in to follow this  

Chapter 2

This topic is 3819 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Quote:
Original post by Rebooted
Lists longer than two elements are created by nesting another cons cell as the second paired value.

I'm not sure I agree on this one. A list of 2 elements is made by using 2 cons cells, not one (I'm assuming "longer than" means >, not >=).

(list? (cons 1 2))
> #f

I'm maybe just being picky at terminology, but I'd rather be pedantic than having people confused over this.

Share this post


Link to post
Share on other sites
Quote:
Original post by Muhammad Haggag
Which brings me to this:
>(list 1 2 3 () 4 5)
(1 2 3 () 4 5)

If a nil element can be found mid-list, how does it differentiate between the end-of-list marker and the one in the middle? I thought null? worked by examining the car and comparing it against (), but that's obviously not the case?

null? does not work on the car, as only cons cells have cars and null? works on any object (numbers, strings, ...).

(define (null? x)
(eq? x ()))

Your (1 2 3 () 4 5) example isn't a problem: the fourth element () is placed in the car of the fourth cons cell. The structure of the list looks like this:

[1, #] -> [2, #] -> [3, #] -> [(), #] -> [4, #] -> [5, #] -> ()
with # being a pointer whose destination is specified by the following ->.

You just need to differentiate between a cons cell containing () in its car, and just plain (). In order to be an end-of-list marker, the () must appear in the cdr of a cons cell, not the car. Everything in a car position is an element of the list.

Since this is important, one last example:

(define (show x)
(cond ((pair? x)
(display "CONS( car:")
(display (car x))
(display ", cdr:")
(display (cdr x))
(display " )"))
(else
(display x)))
(newline))

(define (list? x)
(show x)
(or (null? x)
(and (pair? x)
(list? (cdr x)))))

> (list? '(1 2 3 () 4 5))
CONS( car:1, cdr:(2 3 () 4 5) )
CONS( car:2, cdr:(3 () 4 5) )
CONS( car:3, cdr:(() 4 5) )
CONS( car:(), cdr:(4 5) )
CONS( car:4, cdr:(5) )
CONS( car:5, cdr:() )
()
#t

Share this post


Link to post
Share on other sites
Quote:
Original post by SamLowry
Quote:
Original post by Rebooted
Lists longer than two elements are created by nesting another cons cell as the second paired value.

I'm not sure I agree on this one. A list of 2 elements is made by using 2 cons cells, not one (I'm assuming "longer than" means >, not >=).

Right. The second paired element should always be another list: () if the list is finished, or a cons cell.

It's worth pointing this example out too:


> (list? (cons 1 (cons 2 ())))
#t
> (list? (cons 1 (cons 2 3)))
#f

Share this post


Link to post
Share on other sites
For some reason, I'm not happy with my solutions to 2.27 and 2.28. They work well, but I have a nagging feeling that they're inelegant, or that there's an alternative way:

Quote:
Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

>(define x (list (list 1 2) (list 3 4)))
>x
((1 2) (3 4))

>(reverse x)
((3 4) (1 2))

>(deep-reverse x)
((4 3) (2 1))


My solution:
(define (deep-reverse items)
(define (iter in out)
(if (null? in)
out
(let ((head (car in)) (tail (cdr in)))
(if (list? head)
(iter tail (cons (deep-reverse head) out))
(iter tail (cons head out))))))
(iter items ()))


Quote:
Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

>(define x (list (list 1 2) (list 3 4)))

>(fringe x)
(1 2 3 4)

>(fringe (list x x))
(1 2 3 4 1 2 3 4)


My solution:
(define (fringe tree)
(if (null? tree)
()
(if (not (list? tree))
(list tree)
(append (fringe (car tree)) (fringe (cdr tree))))))


What do you think?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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'?

Share this post


Link to post
Share on other sites
Quote:
Original post by Muhammad Haggag
Is there another popular name for 'accumulate'?

fold and reduce are typical names for that function.

Share this post


Link to post
Share on other sites
Quote:
Original post by Muhammad Haggag
Exercise 2.35 is about writing a count-leaves procedure as an accumulation operation. I wrote a recursive solution as follows:
*** Source Snippet Removed ***
Is it possible to get away with a simpler solution? (Not that this one is complex--it isn't. Just wondering)

Kinda hard to answer. In theory, there could be a accumulate function specialized for trees and you could use that. But this logic would lead to absurdities, as you could simply say there's an even more specialized pre-existent function doing exactly the same as what count-leaves is supposed to do, and just call that. That would definitely lead to the simplest code.

So, using accumulate as it's defined in SICP, your code is probably the simplest solution, simplest meaning compact without being cryptic. Maybe you could make it a bit clearer by separating levels of abstraction (by using helper functions), but that's definitely nitpicking. Plus, this separating could lead to very abstract functions which would make things more complicated against.

Time to settle on a single answer for once: "hmmmm... I'm not sure".

Share this post


Link to post
Share on other sites

This topic is 3819 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this