[taos-glug] thumbs down to SICP Exercise 2.32; empty sets, append
- From: "Philip T. Ansteth" <pansteth@xxxxxxxxxxx>
- To: taos-glug@xxxxxxxxxxxxx
- Date: Tue, 26 Aug 2003 15:49:02 -0500
I figured out an answer that gives the same list of subsets of (1 2 3)
in the book. I trust that list reflects the standard definition of
"subset".
My answer is below if you want to look at it, plus some problems
that I ran into testing it on the empty set and different versions
of append.
But I don't have the requested "clear explanation" of why it works, and
I don't like that. I guess, lacking that clear explanation, it looks like
magic to me. Plus I ran into problems with the empty set and
append.
What would such a "clear explanation" consist of?
It seems to me that it could be nothing less than a argument that shows the
equivalence of the Scheme procedure to the formal definition of subset.
And the definition of a subset, where would that come from? I don't
think that it's an "intuitive" sort of thing, like the shortest distance
between two points being a straight line.
For example, what would be the subsets of the empty set? (See below.)
IMHO, there is something gimmicky about the author's example.
This Exercise 2.32 example uses a programming technique that came out
of the blue. It's just not the same as any of the conventional programming
techniques (such as cons'ing up and cdr'ing down) that have been developed
to this point in the book.
I therefore give a "thumbs down" to this this exercise. Personally, I would
be very nervous if I had came across this in somebody else's code, and
I won't, at this point, put it in any of mine--at least not until
I understand it.
Here's my "answer":
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (x) (cons (car s) x)) rest)))))
P.S. I haven't yet given up on this. For example, I find it slightly less
unintelligible if I write it like this:
(define (subsets2 s)
(if (null? s)
(list '())
(let ((rest (subsets2 (cdr s))))
(append (map (lambda (x) (cons (car s) x)) rest) rest))))
This seems to give the same answer as the first for (1 2 3).
But both might be wrong.
Things don't seem to work for the empty set:
(define empty_set '())
(subsets empty_set) --> () or (()) depending on which "append" you use
(subsets2 empty_set) --> (())
The one result used the version of append in the book (section
2.2.1, the other MzScheme's implementation (on Windows Me--I don't know about
Guile under Linux).
But I haven't the foggiest why reversing the order of an append would
give different results using the append in 2.2.1
Also, is it correct that the empty set is a subset of itself?
I know there's somebody out there who knows the answer to these things.
Other related posts:
