From Files to Lines, from Lists to Lists of Lists

Next: Binary Search Up: Variations on a Theme Previous: Fractals

From Files to Lines, from Lists to Lists of Lists

In section , we discussed the organization of computer files, which is one way to equip a computer with permanent memory. We did not discuss the nature of files per se. Roughly put, we can think of a file as a list of symbols:

Variations on a Theme

A file is either

empty, or
(cons s f) where s is a symbol and f is a file.

A fully faithful representation of files should include only symbols that correspond to characters, but for our purposes we may ignore this distinction.

Following a tradition that predates computers, one symbol is almost always treated differently: 'NL. The symbol stands for newline and separates two lines from each other. That is, 'NL indicates the end of one line and the beginning of another. In most cases, it is therefore better to think of files as data with more structure. In particular, a file could be represented as a list of lines, where each line is a list of symbols.

For example, the file

(list 'how 'are 'you 'NL
      'doing '? 'NL 
      'any 'progress '?)

should be processed as a list of three lines:

(list (list 'how 'are 'you)
      (list 'doing '?) 
      (list 'any 'progress '?))

Similarly, the file

(list 'a 'b 'c 'NL
      'd 'e 'NL 
      'f 'g 'h 'NL)

is also represented as a list of three lines, because, by convention, an empty line at the end is ignored:

(list (list 'a 'b 'c)
      (list 'd 'e) 
      (list 'f 'g 'h))

Exercises Exercise 27.2.1

Determine what the list-of-lines representation for empty, (list 'NL), and (list 'NL 'NL) should be. Why are these examples important test cases?

Hint: Keep in mind that an empty line at the end is ignored. Solution

Here are the contract, purpose statement, and header:

;; file->list-of-lines : file -> (listof (listof symbols))
;; to convert a file into a list of lines  
(define (file->list-of-lines afile) ...)

Describing the process of separating a file into a list of lines is easy. The problem is trivially solvable if the file is empty; in that case, the file doesn't contain a line. Otherwise, the file contains at least one symbol and thus at least one line. This line must be separated from the rest of the file, and then the rest of the file must be translated into a list of lines.

Let us sketch this process description in Scheme:

(define (file->list-of-lines afile)
  (cond 
    [(empty? afile) ...] 
    [else 
      ... (first-line afile) ... 
      ... (file->list-of-lines (remove-first-line afile)) ...]))

Because the separation of the first line from the rest of the file requires a scan of an arbitrarily long list of symbols, we add two auxiliary functions to our wish list: first-line, which collects all symbols up to, but excluding, the first occurrence of 'NL or the end of the list; and remove-first-line, which removes all those symbols and produces the remainder of afile.

;; file->list-of-lines : file -> (listof (listof symbol))
;; to convert a file into a list of lines  
(define (file->list-of-lines afile) 
  (cond 
    [(empty? afile) empty] 
    [else 
      (cons (first-line afile) 
            (file->list-of-lines (remove-first-line afile)))]))

;; first-line : file -> (listof symbol) 
;; to compute the prefix of afile up to the first occurrence of NEWLINE 
(define (first-line afile) 
  (cond 
    [(empty? afile) empty] 
    [else (cond 
            [(symbol=? (first afile) NEWLINE) empty] 
            [else (cons (first afile) (first-line (rest afile)))])]))

;; remove-first-line : file -> (listof symbol) 
;; to compute the suffix of afile behind the first occurrence of NEWLINE 
(define (remove-first-line afile) 
  (cond 
    [(empty? afile) empty] 
    [else (cond 
            [(symbol=? (first afile) NEWLINE) (rest afile)] 
            [else (remove-first-line (rest afile))])]))

(define NEWLINE 'NL)

Figure: Translating a file into a list of lines

From here, we can fill the gaps easily. In file->list-of-lines, the answer in the first clause must be empty because an empty file does not contain any lines. The answer in the second clause must cons the value of (first-line afile) onto the value (file->list-of-lines (remove-first-line afile)), because the first expression computes the first line and the second one computes the rest of the lines. Finally, the auxiliary functions process their inputs in a structurally recursive manner; their development is a straightforward exercise. Figure collects the three function definitions and a variable definition for NEWLINE.

Let us take a look at the process of turning the first file from above into a list of lines:

  (file->list-of-lines (list 'a 'b 'c 'NL 'd 'e 'NL 'f 'g 'h 'NL))

= (cons (list 'a 'b 'c) (file->list-of-lines (list 'd 'e 'NL 'f 'g 'h 'NL)))

= (cons (list 'a 'b 'c) 
        (cons (list 'd 'e) 
              (file->list-of-lines (list 'f 'g 'h 'NL))))

= (cons (list 'a 'b 'c) 
        (cons (list 'd 'e) 
              (cons (list 'f 'g 'h) 
                    (file->list-of-lines empty))))

= (cons (list 'a 'b 'c) 
        (cons (list 'd 'e) 
              (cons (list 'f 'g 'h) 
                    empty)))

= (list (list 'a 'b 'c) 
        (list 'd 'e) 
        (list 'f 'g 'h))

From this evaluation we can easily tell that the argument of the recursive application of file->list-of-lines is almost never the rest of the given file. That is, it is basically never an immediate component of the given file but always a proper suffix. The only exception occurs when 'NL occurs twice in a row.

Finally, the evaluation and the definition of file->list-of-lines show that its generative recursion is simple. Every recursive application consumes a list that is shorter than the given one. Hence the recursive process eventually stops because the function consumes empty.

Exercises Exercise 27.2.2

Organize the program in figure using local.

Abstract the functions first-line and remove-first-line. Then organize the resulting program using a local again. Solution

Exercise 27.2.3

Design file->list-of-checks. The function consumes a file of numbers and outputs a list of restaurant records.

A file of numbers is either

empty, or
(cons N F) where N is a number and F is a file, or
(cons 'NL F), where F is a file.

The output of file->list-of-checks is a list of restaurant structures with two fields:

(define-struct rr (table costs))

They are: a table number and a list of amounts charged to that table.

Example:

(equal? (file->list-of-checks
                                   (list 1 2.30 4.00 12.50 13.50 'NL 
                                         2 4.00 18.00 'NL 
                                         4 2.30 12.50)) 
        (list (make-rr 1 (list 2.30 4.00 12.50 13.50)) 
              (make-rr 2 (list 4.00 18.00)) 
              (make-rr 4 (list 2.30 12.50))))

Solution

Exercise 27.2.4

Develop the function create-matrix. It consumes a number n and a list of numbers. It produces a list of n lists of n numbers.

Example:

(equal? (create-matrix 2 (list 1 2 3 4))
        (list (list 1 2) 
              (list 3 4)))

Solution

Next: Binary Search Up: Variations on a Theme Previous: Fractals

PLT