Home > Archive > Scheme > July 2006 > The Little Schemer
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
The Little Schemer
|
|
|
| On page 152 the book talks about partial and total functions.
It introduces a function called 'align' that has the following
definition:
(define align
(lambda (pora)
(cond
((atom? pora) pora)
((a-pair? (first pora))
(align (shift pora)))
(else (build (first pora)
(align (second pora)))))))
It then asks to write a function that counts the number
of atoms in align's arguments.
So it introduces this:
(define length*
(lambda (pora)
(cond
((atom? pora) 1)
(else (+ (length* (first pora))
(length* (second pora)))))))
This of course just counts each atom of a given lat.
Which is different from the problem statement given.
I interpret the problem statement:
"write a function that counts the number
of atoms in align's arguments."
To mean, for every list passed to align in the function
'align', count the number of atoms then give the total.
Now at this point they have the following to say:
<begin quote>
Is there something else that changes about
the arguments to align and its recursive uses?
Yes, there is. The first component of a pair
becomes simpler, though the second component
becomes more complicated.
In what way is the first component simpler?
It is only a part of the original pair's first
component.
Doesn't this mean that length* is the wrong
function for determining the length of the
argument? Can you find a better function?
A better function should pay more attention
to the first component.
How much more attention should we pay to
the first component?
At least twice as much.
<end quote>
Then they introduce the right function:
(define weight*
(lambda (pora)
(cond
((atom? pora) 1)
(else
(+ (x (weight* (first pora)) 2)
(weight* (second pora)))))))
If I pass ((a b) c) to weight*, I get 7.
And that is fine if you consider (a b) to
be an atom. But I thought that is
specifically a list? In which case,
how is this correctly counting atoms
in align's arguments?
If I pass ((a b) c) to align, the valid arguments
would be:
((a b) c)
(a (b c))
(b c)
c
Which means the valid number of atoms
in align's argument would be 5.
Because (a b) and (b c) in the
two lists ((a b) c) and (a (b c))
respectively, are lists. Not atoms.
Now, I'm willing to give the author's the
benefit of the doubt because I am still
new to scheme. Where is the error in
my thinking?
--
aegis
| |
|
|
aegis wrote:
> On page 152 the book talks about partial and total functions.
> It introduces a function called 'align' that has the following
> definition:
>
> (define align
> (lambda (pora)
> (cond
> ((atom? pora) pora)
> ((a-pair? (first pora))
> (align (shift pora)))
> (else (build (first pora)
> (align (second pora)))))))
>
> It then asks to write a function that counts the number
> of atoms in align's arguments.
>
> So it introduces this:
>
> (define length*
> (lambda (pora)
> (cond
> ((atom? pora) 1)
> (else (+ (length* (first pora))
> (length* (second pora)))))))
>
> This of course just counts each atom of a given lat.
> Which is different from the problem statement given.
>
> I interpret the problem statement:
> "write a function that counts the number
> of atoms in align's arguments."
>
> To mean, for every list passed to align in the function
> 'align', count the number of atoms then give the total.
>
> Now at this point they have the following to say:
>
> <begin quote>
> Is there something else that changes about
> the arguments to align and its recursive uses?
>
> Yes, there is. The first component of a pair
> becomes simpler, though the second component
> becomes more complicated.
>
> In what way is the first component simpler?
>
> It is only a part of the original pair's first
> component.
>
> Doesn't this mean that length* is the wrong
> function for determining the length of the
> argument? Can you find a better function?
>
> A better function should pay more attention
> to the first component.
>
> How much more attention should we pay to
> the first component?
>
> At least twice as much.
> <end quote>
>
> Then they introduce the right function:
>
> (define weight*
> (lambda (pora)
> (cond
> ((atom? pora) 1)
> (else
> (+ (x (weight* (first pora)) 2)
> (weight* (second pora)))))))
>
> If I pass ((a b) c) to weight*, I get 7.
> And that is fine if you consider (a b) to
> be an atom. But I thought that is
> specifically a list? In which case,
> how is this correctly counting atoms
> in align's arguments?
>
> If I pass ((a b) c) to align, the valid arguments
> would be:
> ((a b) c)
> (a (b c))
> (b c)
> c
How are you getting (a (b c))?
The first invocation is with '((a b) c).
This invocation adds these two items:
2 * (weight '(a b))
(weight 'c)
The (weight '(a b)) invocation adds these two items:
2 * (weight 'a)
(weight 'b)
(weight 'a), (weight 'b), and (weight 'c) all return 1, because 'a, 'b,
and 'c are all atoms.
The total is 7 because of the recursive structure; 2 * (weight '(a b))
and 2 * (weight 'a) means that the total weight of the a is 4, and 2 *
(weight '(a b)) means the total weight of b is 2. So the total is 4 + 2
+ 1 = 7.
| |
| aegis 2006-07-16, 10:00 pm |
|
H. wrote:
> aegis wrote:
>
> How are you getting (a (b c))?
>
I wasn't referring to weight* there but instead the function
"align" and the different arguments passed to
align and how the number of atoms that align deals
with is 7. I was trying to understand how they derived
the weight* function in relation to how the align function
works.
--
aegis
| |
| Marlene Miller 2006-07-17, 4:00 am |
| > > aegis wrote:
[...]
[...][color=darkred]
[...][color=darkred]
> I wasn't referring to weight* there but instead the function
> "align" and the different arguments passed to
> align and how the number of atoms that align deals
> with is 7. I was trying to understand how they derived
> the weight* function in relation to how the align function
> works.
It looks to me like you want to count the atoms in the arguments to align
for /all the recursive calls/. I think that is the problem. I think your way
of reading of the problem is not what the authors mean.
Take just one argument, the first call. ((a b) c). Count the atoms: a, b, c:
3. ((1 + 1) + 1) = 3. Count the atoms again, but give the left one of a pair
twice as much weight. (2 * (2 * 1 + 1) + 1) = 7.
| |
|
|
Marlene Miller wrote:
> [...]
> [...]
> [...]
>
> It looks to me like you want to count the atoms in the arguments to align
> for /all the recursive calls/. I think that is the problem. I think your way
> of reading of the problem is not what the authors mean.
>
> Take just one argument, the first call. ((a b) c). Count the atoms: a, b, c:
> 3. ((1 + 1) + 1) = 3. Count the atoms again, but give the left one of a pair
> twice as much weight. (2 * (2 * 1 + 1) + 1) = 7.
I still don't follow though. Why do we give the left one
of a pair twice as much weight?
Beyond that, I also fail to see how the problem statement:
"Can you write a function that counts the number of atoms
in align's arguments"
means anything other than count the atoms in the arguments
to align for /all the recursive calls/. "align's arguments" expresses
more than one argument belonging to align. Further, why do the
authors insist on conflating atoms and lists?
If I pass ((a b) c) to align, then there is only one atom
/in/ that argument. It is "c". "(a b)" is not an atom. It is a list.
--
aegis
| |
|
|
> I still don't follow though. Why do we give the left one
> of a pair twice as much weight?
Just because that is how the author's described the pattern. They could
have described a pattern where the first elements are squared instead
of doubled, and then the resulting program would have implemented that.
As far as I can see, giving the left one twice as much weight is an
academic exercise with the goal of giving the reader more practice in
writing and understanding recursion.
> Beyond that, I also fail to see how the problem statement:
> "Can you write a function that counts the number of atoms
> in align's arguments"
> means anything other than count the atoms in the arguments
> to align for /all the recursive calls/. "align's arguments" expresses
> more than one argument belonging to align. Further, why do the
> authors insist on conflating atoms and lists?
> If I pass ((a b) c) to align, then there is only one atom
> /in/ that argument. It is "c". "(a b)" is not an atom. It is a list.
Well actually, if I have the list '((a b) c), there are *no* atoms.
There is only one list. But '((a b) c) is an argument to a recursive
procedure, and one of the next recursive calls with this procedure is
with 'c, which is an atom. And further recursive calls are with 'a and
'b. So, eventually all three atoms are processed.
| |
| Marlene Miller 2006-07-18, 4:01 am |
| "aegis" <aegis@mad.scientist.com> wrote
> I still don't follow though. Why do we give the left one
> of a pair twice as much weight?
We'd like to know (have some assurrance) that our recursive function stops
recurring. Some don't. We'd like to have a /proof/ that our recursive
function stops. In some recursive functions, the argument is an integer
which decreases by 1 with each recursive call. In some recursive functions,
the argument is a (finite) list whose length decreases by 1 with each
recursive call. In align it's obvious to you and me by looking at some
examples that the right-shifting will stop. We'd like to prove that. We'd
like to assign a positive integer to each argument that decreases with each
call. Simply /deep/ counting the number of atoms in the argument does not
work. ((a b) c) => 3 atoms. (a (b c)) => 3 atoms. The number of atoms does
not decrease. We observe intuitively that the pairs gravitate to the right,
accumulate on the right. If we assign a large number to a left-heavy
configuration of pairs and a small number to a right-heavy configuration of
pairs, the numbers will decrease with each call to align and we will know
that align stops. As we process the nested list of atoms, we count atoms
(not pairs), but we favor the left atom by counting it twice. If the left
member of a pair is also pair (a b), we don't count the pair. We remember
that we have to count each atom in the pair twice. We go into the pair (a
b), count "a" twice. 2*1 + 1 = 3. We come out and count the 3 (so-to-speak)
atoms in the pair twice. 2*3 + 1 = 7. [Well, any book I'd write clearly
wouldn't sell.]
> Beyond that, I also fail to see how the problem statement:
> "Can you write a function that counts the number of atoms
> in align's arguments"
> means anything other than count the atoms in the arguments
> to align for /all the recursive calls/. "align's arguments" expresses
> more than one argument belonging to align.
"Count the elements in the subsets of S = {a b c d}." Does that mean count
the elements in each subset or count the elements in all the subsets? I
don't know.
> Further, why do the
> authors insist on conflating atoms and lists?
> If I pass ((a b) c) to align, then there is only one atom
> /in/ that argument. It is "c". "(a b)" is not an atom. It is a list.
I'd say ((a b) c) has 3 atoms. Do you remember the chapter Oh My Gawd*: It's
Full of Stars? Deep (not shallow) counting . The way I think about it, they
are not counting the pair (a b). They are counting all the atoms in the
pair. All those atoms have to be counted twice. They go into the pair, count
a twice and b once. They come out and remember that they have to count all 3
(so-to-speak) atoms in the pair twice. That makes 6 atoms. They count c
once. That makes 7 atoms.
| |
| bestphphosting@gmail.com 2006-07-19, 8:04 am |
| Hi
I really need this book Little Schemer .
Is this book available as an ebook somewhere on web?
If so then plz send me the link.
Plz reply soon...
Bye
aegis wrote:
> On page 152 the book talks about partial and total functions.
> It introduces a function called 'align' that has the following
> definition:
>
> (define align
> (lambda (pora)
> (cond
> ((atom? pora) pora)
> ((a-pair? (first pora))
> (align (shift pora)))
> (else (build (first pora)
> (align (second pora)))))))
>
> It then asks to write a function that counts the number
> of atoms in align's arguments.
>
> So it introduces this:
>
> (define length*
> (lambda (pora)
> (cond
> ((atom? pora) 1)
> (else (+ (length* (first pora))
> (length* (second pora)))))))
>
> This of course just counts each atom of a given lat.
> Which is different from the problem statement given.
>
> I interpret the problem statement:
> "write a function that counts the number
> of atoms in align's arguments."
>
> To mean, for every list passed to align in the function
> 'align', count the number of atoms then give the total.
>
> Now at this point they have the following to say:
>
> <begin quote>
> Is there something else that changes about
> the arguments to align and its recursive uses?
>
> Yes, there is. The first component of a pair
> becomes simpler, though the second component
> becomes more complicated.
>
> In what way is the first component simpler?
>
> It is only a part of the original pair's first
> component.
>
> Doesn't this mean that length* is the wrong
> function for determining the length of the
> argument? Can you find a better function?
>
> A better function should pay more attention
> to the first component.
>
> How much more attention should we pay to
> the first component?
>
> At least twice as much.
> <end quote>
>
> Then they introduce the right function:
>
> (define weight*
> (lambda (pora)
> (cond
> ((atom? pora) 1)
> (else
> (+ (x (weight* (first pora)) 2)
> (weight* (second pora)))))))
>
> If I pass ((a b) c) to weight*, I get 7.
> And that is fine if you consider (a b) to
> be an atom. But I thought that is
> specifically a list? In which case,
> how is this correctly counting atoms
> in align's arguments?
>
> If I pass ((a b) c) to align, the valid arguments
> would be:
> ((a b) c)
> (a (b c))
> (b c)
> c
>
> Which means the valid number of atoms
> in align's argument would be 5.
> Because (a b) and (b c) in the
> two lists ((a b) c) and (a (b c))
> respectively, are lists. Not atoms.
>
> Now, I'm willing to give the author's the
> benefit of the doubt because I am still
> new to scheme. Where is the error in
> my thinking?
>
> --
> aegis
| |
| Pascal Bourguignon 2006-07-19, 8:04 am |
| bestphphosting@gmail.com writes:
> I really need this book Little Schemer .
> Is this book available as an ebook somewhere on web?
> If so then plz send me the link.
> Plz reply soon...
No, but it's worth its price, so you can get a paper version anyway ;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
You're always typing.
Well, let's see you ignore my
sitting on your hands.
|
|
|
|
|