[plt-scheme] Help requested for HtDP Exercise 16.3.4 Challenge Part 2

All clues, comments and suggestions welcome!

Link to problem:
http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-21.html#node_sec_16.3

Data Definitions
A path is either
1.	empty, or
2.	(cons s p) where s is a symbol and p is a path

A list-of-files is either
1.	empty, or
2.	(cons f lof) where f is a file structure and lof is a list-of-files

A list-of-directories is either
1.	empty, or
2.	(cons d lod) where d is a directory structure and lod is a list-of-
directories

A directory is a structure
	(make-dir n ds fs)
where n is a symbol (representing the name of the directory), ds is a
list-of-directories, and fs is a list-of-files.

A file is a structure
	(make-file n s x)
where n is a symbol (representing the name of the file) s is a number
and x is some Scheme value.

Link to illustration of a exercise directory tree:
http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-21.html#node_sec_16.1

A Scheme representation of the exercise directory tree:
(define-struct file (name size content))
(define-struct dir(name dirs files))

(define docs(make-dir 'docs empty (list (make-file 'read! 19 empty))))
(define code(make-dir 'code empty (list (make-file ‘hang  8 empty)
(make-file 'draw 2 empty))))
(define text(make-dir 'text empty (list (make-file 'part1 99 empty)
(make-file 'part2 52 empty)(make-file 'part3 17 empty))))
(define libs(make-dir 'libs (list code docs)empty))
(define ts(make-dir 'ts (list text libs)(list (make-file 'read! 10
empty))))

Exercise 16.3.4 has three parts: the basic exercise, and the first and
second parts of the ‘challenge.’  I’m stuck on the second part of the
challenge.  Each solution seems to build on the last, so I’m including
what I came up with for the basic exercise and part 1 of the challenge
for context.

16.3.4 – Solution to basic exercise:
;;find?: directory-structure symbol > boolean
;;accepts a directory and a file-name, returns true if file-name
appears in directory or any sub-directories, false if it ;;does not
;;(find? ts 'hang) > true
(define(find? d f)
  (or(search-files (dir-files d) f);; search all files in directory
for file matching file-name
     (search-dirs (dir-dirs d) f)));; search all sub-directories for
file matching file-name

;;search-files:list-of-file-structures symbol > boolean
;;accepts a list-of-files and a file-name, returns true if file-name
matches any file names contained in the ;;list-of-files, false if it
does not
;;(search-files (list(make-file 'hang 8 empty)) 'hang) > true
(define(search-files lof f)
  (cond
    [(empty? lof)false];; if list-of-files is empty, return false
    [else(or(check-file-name (first lof) f);;else check first file
name for match or
            (search-files (rest lof)f))]));;recur on rest of list

;;check-file-name:file-structure symbol > boolean
;;accepts a file and a file-name, returns true if name of file and
file-name match, false if they do not.
;;(check-file-name (make-file 'hang 8 empty) 'hang) > true
(define(check-file-name fl f)
  (cond
    [(symbol=? (file-name fl)f)true];;if name of file matches file-
name, return true
    [else false]));;otherwise, return false

;;search-dirs:list-of-directory-structures symbol > boolean
;;accepts a list-of-directories and a file-name, returns true if file-
name matches any files found in the ;;subdirectories, otherwise false
;;(search-dirs (list text libs) 'part1 > true
(define(search-dirs lod f)
  (cond
    [(empty? lod)false];;if list-of-directory structures is empty,
then return false
    [else(or(find? (first lod) f);;else submit first directory to
'find?' and search rest of directories in list
            (search-dirs (rest lod) f))]))

16.3.4 – Solution to part 1 of ‘challenge’:

;;find: directory file-name > boolean or path
;;accepts a directory structure and file name; if file not found in
directories or subdirectories, returns 'false'; if file ;;is found,
returns path from input directory to nearest directory
;;(find ts 'read!) > (list 'ts)
(define(find d f)
  (cond
    [(boolean=? (find? d f)true);; if file found in either directory
or subdirectories, then
     (cond
       [(boolean=?(search-files(dir-files d)f)true);; if file found in
directory, list path from directory
        (list(dir-name d))]
       [else(cons(dir-name d)(make-path (dir-dirs d)f))])];;else start
list from directory and search subdirectories
    [else false]));; else file not found, so return false

;;make-path: list-of-directories file-name > boolean or path
;;accepts a list-of-directory structures and file-name: returns false
if file not found; a path from immediate ;;directory to nearest
directory if file is found
;;(make-path (list ts) 'read!) > (list 'ts)
(define(make-path lod f)
  (cond
    [(empty? lod)false];; if list-of-directories is empty, return
false
    [(boolean=?(find?(first lod)f)true);;if file-name not found in
first directory in list, search rest of directories
     (find(first lod)f)]
    [else (make-path (rest lod)f)]));; else, find the path from the
first directory in list

So far, so good?

16.3.4 – Proposed solution to part 2 of ‘challenge’:

I can only conceive of two ways to solve this problem.  The first is a
kind of ‘bottom-up’ approach, and adopts the mechanics employed by the
solution to HtDP 12.4.2, that is: recursively attaching the current
directory name to each path within a list of found paths.

Preventing this function from crashing, at least the way I’ve designed
it, relies on omitting ‘path’ as a possible outcome.  The current
function returns only a boolean or a list-of-paths.  It seems to me
that the function’s defects and my inability to conceive of a design
which delivers the desired output without resorting to some “post-
processing” are probably related…..

The second solution imagines a “top-down” approach by introducing
‘path’ as a third argument to ‘find’.  ‘Path’ is a list which grows
with each recursive call, and would serve as an index of the current
state of ‘find.’  When ‘find’ hits a list-of-directories, it would
append the name of each directory containing a matching file-name to
the end of ‘path:’

(append(path (list (dir-name d))))

My sense is that while this approach can be easily visualized and
might work, it probably violates the constraints of structural
recursion, and therefore constitutes a ‘workaround’ to a more formally
correct solution.  So I haven’t tried it.

Final note: for my examples, I’ve changed the definition of directory
‘code  to ---

(define code(make-dir 'code empty (list (make-file ‘read!  8 empty)
(make-file 'draw 2 empty))))

--  to include a third path to ‘read! It makes the tests more
rigorous.

Anyway, here’s what I have so far:

;;find-all-paths: a-directory symbol > boolean or a list-of-paths
;; accepts a directory structure: returns false if file-name not found
in directory files or sub-directories, or a ;;list-of-paths if file is
found among the directory or sub-directory files.
;;(find-all-paths ts 'read) > (list (list ts)(list ts libs docs)(list
ts libs code))))
(define(find-all-paths d f)
  (cond
    [(boolean=?(and(search-dirs(dir-dirs d)f)(search-files(dir-files
d)f))true);;if matches are found in the current ;;directory files and
subdirectories, then
     (append(list(list(dir-name d)))(add-header-to-path(dir-name d)
(list-paths(dir-dirs d)f)))];; return a list-of-paths by ;;appending
the list-of-the-path from the current directory to the list-of-paths
found by attaching the current ;;directory name to subsequent paths
found in the subdirectories.
    [(boolean=?(search-files (dir-files d)f)true);; otherwise, if a
match is found only in the current directory files, then return a list-
of-paths from the current directory
     (list(list (dir-name d)))]
    [(boolean=? (search-dirs(dir-dirs d)f)true);; otherwise, if a
match is found only somewhere in the subdirectories, ;;proceed as in
first condition without appending path from current directory
     (add-header-to-path(dir-name d)(list-paths (dir-dirs d)f))]
    [else false]));; else there is no match, so return false.

;;list-paths: list-of-directories symbol > list-of-paths
;; accepts a list-of-directory structures and a file-name: returns an
empty list of paths if no matches are found, or a ;;list-of-paths
containing paths to directories with
;;matching file names
;;(list-paths (list ts) 'read) > (list (list ts)(list ts libs docs)
(list ts libs code))))
(define(list-paths lod f)
  (cond
    [(empty? lod)(list empty)];;return empty list of paths for an
empty list-of-directories
    [(boolean=? (find? (first lod) f)false)(list-paths (rest
lod)f)];;recur on rest of list no match is found with the
first ;;directory in list-of-directories
    [else(append(find-all-paths(first lod)f)(list-paths (rest
lod)f))]));; else, append the list of paths returned by the first
directory to all other list-of-paths found ;;by recurring on the rest
of the list-of-directories.

;;add-header-to-path : symbol list-of-paths
;;accepts a directory-name and a list-of-paths: returns a new list-of-
paths with the directory-name attached to the ;;front of each path
;;(add-header-to-path 'ts (list(list 'libs 'docs)(list 'libs 'code)))
> (list(list 'ts 'libs 'docs)(list 'ts 'libs 'code)))
(define(add-header-to-path n lop)
  (cond
    [(empty? (rest lop))(list(cons n (first lop)))];; if the rest of
the list-of-paths is empty, then only one path in the list: ;;attach
the directory name to that path
    [else (cons(cons n(first lop))(add-header-to-path n (rest
lop)))]));;otherwise, cons the new path name (cons n ;;(first lop)
onto the list-of-paths generated by recurring  on the rest of the list-
of-paths

Evaluation:
(find-all-paths ts ‘read!)
Desired output > (list (list 'ts) (list 'ts 'libs 'code) (list 'ts
'libs 'docs)
Actual output > (list (list 'ts) (list 'ts 'libs 'code) (list 'ts
'libs 'docs) (list 'ts 'libs) (list 'ts))

Even worse:
(find-all-paths ts ‘draw)
Desired output: (list ‘ts ‘libs ‘code)
Actual output: (list (list 'ts 'libs 'code) (list 'ts 'libs) (list
'ts))

I’ve noted that in each case the extra paths included in the actual
output list only the mediating directories, and not those with
directories containing files with a match.  Can this be fixed, or is
the design fatally flawed?

I’ve found it difficult to isolate the problem within a single
function since they are all interrelated.

Again, all help is greatly appreciated!

Dave Yrueta