[plt-scheme] HTDP 14.3.4 lists within lists.

From: Dave (supercoupon2 at gmail.com)
Date: Tue Mar 31 05:37:24 EDT 2009

Hi,

I seem to be having some problems with this, but am unsure if just my
function is wrong or if my whole headspace about list notation is a
bit off. Here's what I've got so far...

;QUESTION
;Exercise 14.3.4.   People do not like deep Web trees because they
require too many page switches to reach useful information. For that
reason a Web page designer may also want to measure the depth of a
page. A page containing only symbols has depth 0. A page with an
immediately embedded page has the depth of the embedded page plus 1.
If a page has several immediately embedded Web pages, its depth is the
maximum of the depths of embedded Web pages plus 1. Develop depth,
which consumes a Web page and computes its depth.


;DATA DEFINITION

;A Web-page (short: WP) is either
;   1.
;      empty;
;   2.
;      (cons s wp)
;      where s is a symbol and wp is a Web page; or
;   3.
;      (cons ewp wp)
;      where both ewp and wp are Web pages.

;CONTRACT

;depth : WP -> number
;to evaluate the depth of a webpage (max # of internal nesting)

;EXAMPLES

;(depth (list 'q))
; 0
;(depth (list 'q 'w 'r))
; 0
;(depth (list 'q (list 's) 'w 'r))
; 1
;(depth (list 'q (list 's) 'w (list 't) 'r))
; 1
;(depth (list 'q (list 's 'v) 'w (list (list 'p) 't) 'r))
;2


;TEMPLATE

;(define (fun-for-wp a-wp)
;  (cond
;    [(empty? a-wp) ...]
;    [(symbol? (first a-wp)) ... (first a-wp) ... (fun-for-wp (rest a-
wp)) ...]
;    [else ... (fun-for-wp (first a-wp)) ... (fun-for-wp (rest a-
wp)) ...]))


;MALFUNCTION

(define (depth a-wp)
  (cond
    [(empty? a-wp) 0]
    [(symbol? (first a-wp)) (depth (rest a-wp))]
    [else (cond
            ((>= (+ 1 (depth (first a-wp))) (+ 1 (depth (rest a-wp))))
(+ 1 (depth (first a-wp))))
                (else (+ 1 (depth (rest a-wp)))))]))


;TESTS

;(depth (list 'q))
 0
;(depth (list 'q 'w 'r))
 0
;(depth (list 'q (list 's) 'w 'r))
1
;(depth (list 'q (list 's) 'w (list 't) 'r))
2
;(depth (list 'q (list 's 'v) 'w (list (list 'p) 't) 'r))
3

What I've written seems to count all embedded web pages rather than
just the deepest. To me the final cond says If depth of First is
greater, add one to that, otherwise add one to Rest. instead I seem to
be adding the number of any nested lists together.
I've seen that others who have stumbled on this one have used Max
instead of the way I compared the two branches, but I'm not sure
that's where I'm wrong.
It seems like I haven't instructed it to choose one and not the
other.  Anyway, I'll go have a think about this, any assistance would
be much appreciated.




Posted on the users mailing list.