SICP chapter 3 ex. 3.19

This is the exercise that asks to check a list for a loop using
constant space (and it requires a "very clever idea"). Do I understand
it correctly that the clever idea requires us to assume that an
integer always fits in constant (rather than logarithmic) space? If
so, we can

(define (max-depth tree)
(if (not (pair? tree))
0
(add1 (max (max-depth (car tree))(max-depth (cdr tree))))))

and do bounded iteration for (tree-cycle? tree) with an integer depth-
bound D where you use a number N as an index representing a tree-path;

suppose D=5, and N=9 = binary 01001, L(D,N)== (cdr(car(cdr(cdr(car
L))))), assuming 0 for cdr and 1 for car

Is this about right?

adn

"adnakh@gmail.com" <adnakh@gmail.com> writes:
>This is the exercise that asks to check a list for a loop using
>constant space (and it requires a "very clever idea"). Do I understand
>it correctly that the clever idea requires us to assume that an
>integer always fits in constant (rather than logarithmic) space?

Well, yes, you can assume that an integer /that represents a count of
something in memory/ is bounded in size, since memory itself is bounded
in size (typically to 2^32 bytes).  But...

> If so, we can
>
>(define (max-depth tree)
>  (if (not (pair? tree))
>    0
>    (add1 (max (max-depth (car tree))(max-depth (cdr tree))))))
>
>and do bounded iteration for (tree-cycle? tree) with an integer depth-
>bound D where you use a number N as an index representing a tree-path;
>
>   suppose D=5, and N=9 = binary 01001, L(D,N)== (cdr(car(cdr(cdr(car
>L))))), assuming 0 for cdr and 1 for car
>
>Is this about right?

Well, first of all, your max-depth won't work if there's a cycle!

But in any case, the clever idea they're looking for is much cleverer than
that.  It's not just a question of encoding list structures more compactly.
And it's way less code than what I think you'd need for your idea.

adnakh@gmail.com wrote:

> This is the exercise that asks to check a list for a loop using
> constant space (and it requires a "very clever idea"). Do I understand
> it correctly that the clever idea requires us to assume that an
> integer always fits in constant (rather than logarithmic) space? If
> so, we can
>
> (define (max-depth tree)
>   (if (not (pair? tree))
>     0
>     (add1 (max (max-depth (car tree))(max-depth (cdr tree))))))
>
> and do bounded iteration for (tree-cycle? tree) with an integer depth-
> bound D where you use a number N as an index representing a tree-path;
>
>    suppose D=5, and N=9 = binary 01001, L(D,N)== (cdr(car(cdr(cdr(car
> L))))), assuming 0 for cdr and 1 for car
>
> Is this about right?

Eh.  What you're doing is storing the path you took to get to the current
node.  I don't think that's what you want to do.

Your assignment is to "check a list for a loop."  Your code above
will cheerfully keep going around the list (adding an identical sequence
of 1's and 0's each time around) forever without detecting a loop.

If you want to detect a loop, you need to have a way to detect that
some node you look at as you go down the list, is a node you've
looked at before. It doesn't have to happen the first time you see
a node you've looked at before, but you've got to be able to guarantee
that if there's a loop (instead of a NIL at the end of the list) then
sooner or later as you go around the loop, you'll find at least one
node you've seen before, when you're able to *tell* that it's one
you've seen before.

There is an easy solution, but it does require a clever idea.

Bear

On Mar 31, 11:53 pm, "adn...@gmail.com" <adn...@gmail.com> wrote:
> This is the exercise that asks to check a list for a loop using
> constant space (and it requires a "very clever idea"). Do I understand
> it correctly that the clever idea requires us to assume that an
> integer always fits in constant (rather than logarithmic) space? If
> so, we can
>
> (define (max-depth tree)
>   (if (not (pair? tree))
>     0
>     (add1 (max (max-depth (car tree))(max-depth (cdr tree))))))
>
> and do bounded iteration for (tree-cycle? tree) with an integer depth-
> bound D where you use a number N as an index representing a tree-path;
>
>    suppose D=5, and N=9 = binary 01001, L(D,N)== (cdr(car(cdr(cdr(car
> L))))), assuming 0 for cdr and 1 for car
>
> Is this about right?
>
> adn

AFAIK if they say constant space, it requires a proper tail recursive
method. Your max-depth is not tail recursive.

adnakh@gmail.com wrote:
> This is the exercise that asks to check a list for a loop using
> constant space (and it requires a "very clever idea").

Does it say "check a list for a loop" or "check a tree for a loop"?
For lists, it is doable in constant space.  For trees, it requires
space proportional to the space of the tree (i.e., the number of
pairs in the tree).

Aziz,,