1

我正在尝试编写一个函数 find ，它使用目录树和文件名，并确定具有该名称的文件是否出现在目录树中。我所写的内容适用于树的第一级中的文件（读取！），但没有“看到”更远的文件。知道文件是否不在树中的唯一方法是每个目录和文件被选中，但有些目录没有文件，有些没有目录，但有些有。对于我知道在树中的文件，我所写的远远返回 false。我不知道如何写假条件。

(define-struct dir (name dirs files))
(define-struct file (name size content))

(define fs (make-dir 'TS
                     (list (make-dir 'Text empty
                                     (list
                                      (make-file 'part1 99 empty)
                                      (make-file 'part2 52 empty)
                                      (make-file 'part3 17 empty)))
                           (make-dir 'Libs
                                     (list
                                      (make-dir 'Code empty
                                                (list
                                                 (make-file 'hang 8 empty)
                                                 (make-file 'draw 2 empty)))
                                      (make-dir 'Docs empty
                                                (list
                                                 (make-file 'read! 19 empty)))) (list)))
                     (list (make-file 'read! 10 empty))))

(define (find fs name)
  (cond
    [(not (empty? (dir-dirs fs)))
    (dp (dir-dirs fs) name)]
    [(not (empty? (dir-files fs)))
     (fc (dir-files fs) name)]
    [else false]))

(define (dp dirs name) ;consumes lists of directories
  (cond
    [(empty? dirs) false] ;I don't know what else to put here but false
    [else (find (first dirs) name)
          (dp (rest dirs) name)]))

(define (fc files name) ;consumes lists of files
  (cond
    [(empty? files) false]
    [(symbol=? name (file-name (first files))) true]
    [else (fc (rest files) name)]))
4

1 回答 1

1

这是解决方案，（请参阅代码中的注释）：

(define (find fs name)
  ; either in sub-directories list OR sub-files
  (or (fc (dir-files fs) name) (dp (dir-dirs fs) name)))

(define (dp dirs name)
  (cond
    [(empty? dirs) false] ; the base case is o.k.
    [else
     ; either in the first dir OR in the rest
     (or (find (first dirs) name)
         (dp (rest dirs) name))]))

(define (fc files name) ; this is o.k.
  (cond
    [(empty? files) false]
    [(symbol=? name (file-name (first files))) true]
    [else (fc (rest files) name)]))

数据定义

(define-struct file [name size content])
; A File is a structure: 
;   (make-file Symbol N List)

(define-struct dir [name dirs files])
; A Dir is a structure: 
;   (make-dir Symbol Dir* File*)

; A Dir* is one of: 
; – '()
; – (cons Dir Dir*)

; A File* is one of: 
; – '()
; – (cons File File*)

例子

; TS
; ├── Libs
; │   ├── Code
; │   │   ├── draw
; │   │   └── hang
; │   └── Docs
; │       └── read!
; ├── Text
; │   ├── part1
; │   ├── part2
; │   └── part3
; └── read!


; files
(define hang (make-file 'hang 8 empty))
(define draw (make-file 'draw 2 empty))
(define read!-in-docs (make-file 'read! 19 empty))
(define read!-in-ts (make-file 'read! 10 empty))
(define part1 (make-file 'part1 99 empty))
(define part2 (make-file 'part2 52 empty))
(define part3 (make-file 'part3 17 empty))

; directories
(define code (make-dir 'Code '() (list hang draw)))
(define docs (make-dir 'Docs '() (list read!-in-docs)))
(define text (make-dir 'Text '() (list part1 part2 part3)))
(define libs (make-dir 'Libs (list code docs) '()))
(define ts (make-dir 'TS  (list text libs) (list read!-in-ts)))

模板

; Dir -> ...
(define (dir-temp d)
  (... (dir-name d) ... (dir*-temp (dir-dirs d)) ... (file*-temp (dir-files d)) ...))

; File -> ...
(define (file-temp f)
  (... (file-name f) ... (file-size f) ... (file-content f) ...))

; Dir* -> ...
(define (dir*-temp d*)
  (cond
    [(empty? d*) ...]
    [else (... (dir-temp (first d*)) ... (dir*-temp (rest d*)) ...)]))

; File* -> ...
(define (file*-temp f*)
  (cond
    [(empty? f*) ...]
    [else (... (file-temp (first f*)) ... (file*-temp (rest f*)) ...)]))

测试

(check-expect (dir-find ts 'hang) true)
(check-expect (dir-find ts 'part1) true)
(check-expect (dir-find ts 'part99) false)
(check-expect (dir-find text 'read!) false)
(check-expect (dir-find text 'part2) true)
(check-expect (dir-find docs 'read!) true)
(check-expect (dir-find docs 'draw) false)

功能

; Dir Symbol -> Boolean
; does d have a file with the name filename?
(define (dir-find d filename)
  (or (dir*-find (dir-dirs d) filename) (file*-find (dir-files d) filename)))

; File Symbol -> Boolean
; does file f has the name filename?
(define (file-find f filename)
  (symbol=? (file-name f) filename))

; Dir* Symbol -> Boolean
; does d* have a file with the name filename?
(define (dir*-find d* filename)
  (cond
    [(empty? d*) false]
    [else (or (dir-find (first d*) filename) (dir*-find (rest d*) filename))]))

; File* Symbol -> Boolean
; does f* have a file with the name filename?
(define (file*-find f* filename)
  (cond
    [(empty? f*) false]
    [else (or (file-find (first f*) filename) (file*-find (rest f*) filename))]))

如果我们对 Dir 使用这个数据定义，那么我们可以使用列表抽象：

; A Dir is a structure: 
;   (make-dir Symbol [List-of Dir] [List-of File])

; Dir Symbol -> Boolean
; does d have a file with the name filename?
(define (dir-find d filename)
  (or (dir*-find (dir-dirs d) filename) (file*-find (dir-files d) filename)))

; File Symbol -> Boolean
; does file f has the name filename?
(define (file-find f filename)
  (symbol=? (file-name f) filename))

; Dir* Symbol -> Boolean
; does d* have a file with the name filename?
(define (dir*-find d* filename)
  (ormap (λ (d) (dir-find d filename)) d*))

; File* Symbol -> Boolean
; does f* have a file with the name filename?
(define (file*-find f* filename)
  (ormap (λ (f) (file-find f filename)) f*))

我们也可以使用local的强大功能来去掉filename参数

; Dir Symbol -> Boolean
; does d have a file with the name filename?
(define (dir-find d filename)
  (local (; Dir -> Boolean
          ; does d have a file with the name filename?
          (define (dir-find-lcl d)
            (or (dir*-find (dir-dirs d)) (file*-find (dir-files d))))

          ; File -> Boolean
          ; does file f has the name filename?
          (define (file-find f)
            (symbol=? (file-name f) filename))

          ; Dir* -> Boolean
          ; does d* have a file with the name filename?
          (define (dir*-find d*)
            (ormap dir-find-lcl d*))

          ; File* -> Boolean
          ; does f* have a file with the name filename?
          (define (file*-find f*)
            (ormap file-find f*)))
    (dir-find-lcl d)))

事实上，还可以做进一步的简化：

; Dir Symbol -> Boolean
; does d have a file with the name filename?
(define (dir-find d filename)
  (or (ormap (λ (d) (dir-find d filename)) (dir-dirs d))
      (ormap (λ (f) (symbol=? (file-name f) filename)) (dir-files d))))
于 2020-06-01T06:50:43.407 回答