We have recently seen several examples of functions which take multiple complex arguments. By "complex", we mean they involve structures and/or cases in their data definitions, like points, lists, and trees. As always, we want our templates to include all the structural data knowledge that we have, and now we have multiple arguments we can use.
In general, for any particular kind of arguments, there is one template. E.g., for functions involving two lists, we have
(define (f list1 list2)
(cond
[(and (empty? list1) (empty? list2))
...]
[(and (empty? list1) (cons? list2))
...(first list2)...
...(f list1 (rest list2))...]
[(and (cons? list1) (empty? list2))
...(first list1)...
...(f (rest list1) list2)...]
[(and (cons? list1) (cons? list2))
...(first list1)...
...(first list2)...
...(f list1 (rest list2))...
...(f (rest list1) list2)...
...(f (rest list1) (rest list2))...]
The template includes all possible combinations of the arguments'
cases:
cond,
4 cases = (2 cases for 1st argument) * (2 cases for 2nd argument).
In many cases, the function we want can be much simpler than this. This is sufficiently common that we can identify two subcases and use more specialized templates. When writing a program, if we correctly identify that a function corresponds to either special case, we can save time by using a simpler template. As a result we have three cases:
The function examines the structure of only one of the
arguments. The appropriate template is the standard template for that
one argument.
Examples: append
For example, for lists:
(define (f list1 list2)
(cond
[(empty? list1) ...]
[(cons? list1) ...(first list1)...(f (rest list1) list2)...]))
The arguments have similar structures of the same size, and the
function always recurs in a step-wise fashion on each argument.
The template needs only have cases for the structure of one argument,
because the other arguments are the same.
Examples: make-points.
For example, for lists: (define (f list1 list2) (cond [(empty? list1) ...] [(cons? list1) ...(first list1)...(first list2)... ...(f (rest list1) (rest list2))...]))
The general case, as described above.
Example: merge
|
| Sample solutions. |
The following example is tougher, and so is broken into a series of parts.
|
Our goal is to write a function which takes a directory and a natural number, and which returns a list of all files which are at that depth in the directory. We'll say that a file is at depth 0 if it is in the given directory, at depth 1 if it is a directory in the given directory, etc. While this example might sound complicated, it shouldn't be difficult if you follow the template. As a reminder, the following are the relevant data definitions:
; A file is a symbol.
;
; A directory is
; (make-dir name contents)
; where name is a symbol, and contents is a lofd.
;
; A list of files and directories (lofd) is one of
; - empty
; - (cons f r)
; where f is a file, and r is a lofd
; - (cons d r)
; where d is a directory, and r is a lofd
(define-struct dir (name contents))
; Here's an example to work with. It has directories and files up to
; depth 2.
(define sample-dir
(make-dir
'dir0
(list 'file0.0
'file0.1
(make-dir
'dir1.0
(list 'file1.0
(make-dir
'dir2.0
(list 'file2.0
'file2.1))
(make-dir
'dir2.1
(list 'file2.2))
'file1.1))
(make-dir
'dir1.1
empty)
'file0.2
(make-dir
'dir1.2
(list (make-dir
'dir2.2
(list 'file2.3
'file2.4))
'file1.2
'file1.3
(make-dir
'dir2.3
(list 'file2.5)))))))
;(files-at-depth sample-dir 0) = (list 'file0.0 'file0.1 'file0.2)
;(files-at-depth sample-dir 1) = (list 'file1.0 'file1.1 'file1.2 'file1.3)
;(files-at-depth sample-dir 2) = (list 'file2.0 'file2.1 'file2.2 'file2.3 'file2.4 'file2.5)
|
| Sample solution. |