;; The first three lines of this file were inserted by DrScheme. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-intermediate-reader.ss" "lang")((modname 15.3.1) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp"))))) ;A web-page (wp) is a structure: ;(make-wp header doc) where ;header is a symbol and doc is ;a web-document. ; ;A web-document (doc) is either ;1. empty, ;2. (cons sym doc) where sym is a symbol and ;doc is a web-document, or ;3. (cons wp doc) where wp is a webpage and ;doc is a web-document. (define-struct wp (header doc)) ; ;Template ;fun-for-wp : wp -> ??? ;(define (fun-for-wp a-wp) ; ... (wp-header a-wp) ... ; ... (fun-for-doc (wp-doc a-wp)) ...) ; ;fun-for-doc : doc -> ??? ;(define (fun-for-doc a-doc) ; (cond ; [(empty? a-doc) ...] ; [(symbol? (first a-doc)) ; ... (first a-doc) ... ; ... (fun-for-doc (rest a-doc)) ...] ; [(wp? (first a-doc)) ; ... (fun-for-wp (first a-doc)) ... ; ... (fun-for-doc (rest a-doc)) ...])) ; ;size : wp -> number ;Given a-wp, determine the number of ;symbols it contains. (define (size a-wp) (+ 1 (size-doc (wp-doc a-wp)))) ; ;size-doc : doc -> number ;Given a-doc, determine the size ;of the doc, which is the number ;of symbols it contains. ; (define (size-doc a-doc) (cond [(empty? a-doc) 0] [(symbol? (first a-doc)) (+ 1 (size-doc (rest a-doc)))] [(wp? (first a-doc)) (+ (size (first a-doc)) (size-doc (rest a-doc)))])) ;Tests ; (define DOC7 (cons 'ImADoc empty)) (define DOC6 (cons 'ImADocToo empty)) (define WP3 (make-wp 'ImAPage empty)) (define DOC5 (cons WP3 DOC6)) (define WP2 (make-wp 'AmIAPageToo? DOC5)) (define DOC4 (cons 'MaybeADoc DOC7)) (define DOC3 (cons WP2 DOC4)) (define DOC2 (cons 'ADoctor? DOC3)) (define DOC1 (cons 'OrADocument? DOC2)) (define WP1 (make-wp 'NoAWebPage DOC1)) ; ;(size WP1) ;8 ;wp-to-file : wp -> list-of-symbols ;Given a-wp, produces a list-of-symbols containing ;all the symbols in the headers of all web pages ;and all the symbols within the body of a-wp, ;excluding the bodies of immediately embedded ;webpages. ; ;Examples: (define WP-6 (make-wp 'ThisIsARepeat empty)) (define DOC-8 (cons WP-6 empty)) (define DOC-7 (cons 'ThisIsARepeat empty)) (define WP-5 (make-wp 'RepetionSuccess DOC-8)) (define DOC-6 (cons WP-5 DOC-7)) (define WP-4 (make-wp 'ThisIsARepeat DOC-6)) (define DOC-5.5 (cons WP-4 empty)) (define DOC-5 (cons 'NotIncluded DOC-5.5)) (define DOC-4 (cons 'ThisIsAnExample empty)) (define WP-3 (make-wp 'MyHeader empty)) (define DOC-2 (cons WP-3 DOC-4)) (define WP-2 (make-wp 'ThisIsAHeader DOC-5)) (define DOC-1 (cons WP-2 DOC-2)) (define WP-1 (make-wp 'TheHighestWP DOC-1)) ;(wp-to-file WP-1) ;'(TheHighestWP ThisIsAHeader MyHeader ThisIsAnExample)) ;Notice that 'NotIncluded does not show up because ;it is the body of an embedded web-page. ; ;wp-to-file : wp -> list-of-symbols (define (wp-to-file a-wp) (append (list (wp-header a-wp)) (wp-to-file-for-doc (wp-doc a-wp)))) ; ;wp-to-file-for-doc : doc -> list-of-symbols ;Given a-doc, produces a list-of-symbols containing all the ;symbols found within the body of the document as well ;as the headers of embedded web pages. It does not ;return the symbols of the bodies of the embedded ;web pages, however. (define (wp-to-file-for-doc a-doc) (cond [(empty? a-doc) empty] [(symbol? (first a-doc)) (append (list (first a-doc)) (wp-to-file-for-doc (rest a-doc)))] [(wp? (first a-doc)) (append (list (wp-header (first a-doc))) (wp-to-file-for-doc (rest a-doc)))])) ;occurs : symbol wp -> boolean ;Given a-symbol and a-wp, determine if ;a-symbol appears anywhere in the webpage, ;including in embedded webpages. (define (occurs a-symbol a-wp) (cond [(symbol=? a-symbol (wp-header a-wp)) true] [else (occurs-doc a-symbol (wp-doc a-wp))])) ;occurs-doc : symbol doc -> boolean ;Given a-symbol and a-doc, determine if ;a-symbol is anywhere within a-doc, including ;in embedded web pages. (define (occurs-doc a-symbol a-doc) (cond [(empty? a-doc) false] [(symbol? (first a-doc)) (cond [(symbol=? a-symbol (first a-doc)) true] [else (occurs-doc a-symbol (rest a-doc))])] [(wp? (first a-doc)) (or (occurs a-symbol (first a-doc)) (occurs-doc a-symbol (rest a-doc)))])) ;Test ;(wp-to-file WP-1) ;find-for-wp : wp symbol -> list-of-symbols/false ;Given a-wp and a-symbol, returns a list-of-symbols containing ;all the headers encountered on the way to find the symbol. ;Returns empty if the symbol does not occur. ;find-for-wp : wp symbol -> list-of-symbols/false (define (find-for-wp a-wp a-symbol) (cond [(occurs a-symbol a-wp) (append (list (wp-header a-wp)) (find-for-doc (wp-doc a-wp) a-symbol))] [else empty])) ;find-for-doc : doc -> list-of-symbols/false ;Given a-doc and a-symbol, returns a list-of-symbols containing ;all the headers encountered on the way to find a symbol. ;Returns empty if the symbol does not occur. (define (find-for-doc a-doc a-symbol) (cond [(empty? a-doc) empty] [(symbol? (first a-doc)) (find-for-doc (rest a-doc) a-symbol)] [(wp? (first a-doc)) (append (find-for-wp (first a-doc) a-symbol) (find-for-doc (rest a-doc) a-symbol))])) ;find : wp symbol -> list-of-symbols/false ;Given a-wp and a-symbol, return the headers ;of the web-pages that are accessed on the way ;to locating a-symbol. Returns false ;if a-symbol never occurs. (define (find a-wp a-symbol) (cond [(empty? (find-for-wp a-wp a-symbol)) false] [else (find-for-wp a-wp a-symbol)]))