CS2500 Lab 3 (honors) – Lists! Lists! Lists!

Programs must be written for people to read, and only incidentally for machines to execute. - SICP

Always code as if the person who ends up maintaining your code is a violent psychopath who knows where you live. - c2.com

Part I: Style

Importance

Style is important! Programs wind up having remarkably long lifespans in practice. Sometimes they even outlive their creators. Over the course of its life a program will be modified, extended and repaired countless times by many different people. It is therefore important that we learn to write code that will be easily readable by other developers.

If you don't find that argument persuasive consider that even if your program is correct if a tutor can't figure out what it does then you won't get full credit for your work. (Similarly, you probably want to make your grader's life as easy as possible; they hold your grade in their hands after all.)

With that in mind let's look at some guidelines on how to write clear, readable code in Racket.

Guidelines

Guideline 1: Break Lines

Consider the data definition for a Time:

;; A Time is (make-time Number Number)
(define-struct time (hours minutes))

Consider this program:

;; time->text : Time -> Image
;; Produce an image of the given time, as it appears on a digital clock.
(define(time->text a-time)
  (text(string-append(number->string(time-hours a-time))":"(cond[(< (time-minutes a-time)10)"0"]
  [else ""])(number->string(time-minutes a-time)))30'red))

How many arguments are there to text?
How many cond clauses are there?
What are the arguments to string-append?

The code above is a disaster. Because the body is squeezed onto two lines, we cannot answer these questions at a glance. If we insert line breaks, the code becomes much more readable.

;; time->text : Time -> Image
;; Produce an image of the given time, as it appears on a digital clock.
(define (time->text a-time)
  (text (string-append (number->string (time-hours a-time))
                       ":"
                       (cond [(< (time-minutes a-time) 10) "0"]
                             [else ""])
                       (number->string (time-minutes a-time)))
        30
        'red))

With this code, it is easy to see the three arguments to text, the four strings being appended, and the two cond clauses.

In general, try to break long lines by:

Giving each cond clause its own line. (Always a good idea.)
If a cond question or answer is long, then start the answer on the next line. (Often a good idea.)
Giving each function argument its own line. (Less common, but string-append is a typical offender.)

If even these formatting hints do not help, consider designing and using a helper function to make the code more compact. For example, in time->text above, it's probably a good idea to factor out the (string-append ..) expression as a separate helper function.

Every line of code should be no more than 80 characters long. DrRacket can help you with this—can you find where it indicates the current column of the cursor?

Rewrite time->text by developing and using a helper function that computes the (string-append ...) portion of the body. Be sure to invent a good name for this helper function.

Guideline 2: Indentation

Consider the following program:

;; count : LOS -> Number
;; Determine how many symbols are in a-los
(define (count a-los)
(cond
[(empty? a-los)0]
[(cons? a-los)
(+ 1 (count (rest a-los)))]))

This is not indented properly. Copy and paste this code into DrRacket. Then select “Reindent All” under the Racket menu. DrRacket will indent the code properly automatically!!

Make good use of this feature as you develop your programs. Also note that the tab key can be used to automatically indent just the line that the cursor is on. Indentation is a very important factor of readability because it denotes the structure of the program at a glance. And we can't grade what we can't read!!

Note: When you use the “Reindent All” feature or the tab key, you may notice that the indentation sems wrong... this usually means that your program is mis-parenthesized. Move the cursor through your code and use the grey highlighting to be sure that your parentheses are matched as you intend.

Guideline 3: Parentheses Layout

Let's reconsider count from above. The indentation is technically correct, but the parentheses are arranged poorly:

;; count : LOS -> Number
;; Determine how many symbols are in a-los

(define (count a-los)
  (cond
    [(empty? a-los) 0
    ]
    [(cons? a-los
     )
     (+ 1 (count (rest a-los)
          )
     )
    ]
   )
)

A programmer who arranges their parentheses like this is probably trying to use the vertical alignment of the open and closing parentheses to visually determine the code structure. It is much easier to compress the closing parentheses together, and then eyeball the program structure using its indentation. When you need to match parentheses visually, use DrRacket's grey highlighting instead.

;; count : LOS -> Number
;; Determine how many symbols are in a-los
(define (count a-los)
  (cond
    [(empty? a-los) 0]
    [(cons? a-los)
     (+ 1 (count (rest a-los)))]))

Proper indentation and parentheses placement render the parentheses and brackets nearly invisible to the trained eye.

Part II: Finger Exercises

Lots of finger exercises today; lists are important, and they should be second nature.

Consider the following definitions:


;; A LON (List of Numbers) is one of:
;; - empty
;; - (cons Number LON)

;; Examples:
(cons 1 (cons 2 empty))
(cons -3 (cons 3/4 (cons .2 empty)))
(cons 1 (cons 1
      (cons 2 (cons 3 (cons 5
        (cons 8 (cons 13 empty)))))))

For each of the following, make a data definition. Then make at least 3 examples of each.
1. A list of strings
2. A list of images
3. A list of movies, where a movie has a title and a duration
4. A list of a list of numbers (this should take no more work than defining a regular list of numbers)

Part III: List Calisthenics

Write the function sum, which consumes a list of numbers and produces a number which is the sum of the numbers in the list.

Write the function product which consumes a list of numbers and produces the product of all the numbers in the list.

Design the function join-los which consumes a list of strings and produces a string which is the concatenation of each string in the list. For example,

(define a-list-of-strings
  (cons "A"
            (cons "List"
                      (cons "Of"
                                (cons "Strings" empty)))))

(check-expect (join-los a-list-of-strings) "AListOfStrings")

Design the function join-los-with-space which consumes a list of strings and produces a string which is the concatenation of the strings in the list interspersed with a space (" "). For example:
```
(check-expect (join-los-with-space a-list-of-strings) "A List Of Strings ")
```

Design the function join-los-with-string which consumes a string and a list of strings and behaves like join-los-with-space, except it uses the given string instead of a space. For example:

(check-expect (join-los-with-string "!!!" a-list-of-strings)         "A!!!List!!!Of!!!Strings!!!")
(check-expect (join-los-with-string " wheeeeeee " a-list-of-strings) "A wheeeeeee List wheeeeeee Of wheeeeeee Strings wheeeeeee ")
(check-expect (join-los-with-string " " a-list-of-strings)           "A List Of Strings ")

Why might we say that join-los-with-string is "more powerful", "more general", or "more flexible" than join-los or join-los-with-space?

Design a function create-kandinsky which consumes a list of images and overlays them all on a red rectangle.

Here is the data definition for a list of stock trades:

;; A LOT (list of trades) is one of:
;; -- empty
;; -- (cons (make-stock-sale symbol number number) LOT)
;; -- (cons (make-stock-purchase symbol number number) LOT)
(define-struct stock-sale (company shares price-per-share))
(define-struct stock-purchase (company shares price-per-share))

Design a function that takes a list of stock trades and returns a list of the traded companies (that is, their stock symbols).

Design a function that takes a list of stock trades and a symbol and returns the total value of traded shares (both bought and sold).

Part IV: Journeyman Tools

In the Days of Yore, an enterprising young person would be apprenticed to a master in a craft. He would learn all he could, and eventually be able to work on his own, attaining so-called "Journeyman" status. In many professions, an aspiring Journeyman would have to learn to construct the tools of his trade before he might be able to practice that trade.

For this exercise, we'll learn to build our new tools cons, empty, first and rest. By learning to build them ourselves, we can be sure we know how they work when we use them later.

Consider the following structure definitions:

(define-struct empty-seq ())
(define-struct seq (hd tl))
;; A Seq (sequence) is one of
;; - (make-empty-seq)
;; - (make-seq Any Seq)

Now we can define our own implementation of lists, using empty-seq and seq structures.

Write each of the following functions:
```
;; kons : Any Seq -> Seq
;; head : Seq -> Any
;; tail : Seq -> Seq
;; kons? : Seq -> Boolean
;; mpty? : Seq -> Boolean
```
Also, define a value mpty which is the empty Seq. None of these functions should be at all complicated.

Part V: Common Mistakes

If debugging is the process of removing bugs, then programming must be the process of putting them in. - Edsger W. Dijkstra

The design recipe is a powerful tool, but it only works when used properly. The staff has identified a number of common errors that have been showing up on homeworks. Let's go over a few of them in detail.

Violating the Contract

Writing a contract is only useful if your function satisfies the contract. Consider the following example:

;; only-evens : list-of-numbers -> list-of-numbers
;; to create a list containing only the even numbers in a-list-of-nums
(define (only-evens a-list-of-nums)
  (cond [(empty? a-list-of-nums)
         0]
        [(even? (first a-list-of-nums))
         (cons (first a-list-of-nums)
               (only-evens (rest a-list-of-nums)))]
        [else
         (only-evens (rest a-list-of-nums))]))

There is a bug in the definition above. The first branch of the cond clause is violating the contract. 0 is a number, not a list of numbers. In its place we should be using empty. By carefully making sure each branch of our cond statements satisfy our contract we can avoid such errors.

No Data Definition

A contract is only as useful as the information it provides. If we fail to fully specify the kinds of data our functions consume and produce then we defeat the purpose of the contract. Consider the following example.

;; name->greeting : name -> greeting
;; to create a greeting from the provided name

It would make sense to assume that name and greeting are strings. We could write the following function for the contract:

(define (name->greeting name)
  (string-append "Hello, "
                 name
                 "!"))

But what if some other part of our program thought that name was a structure, (define-struct name (first last)), an equally reasonable assumption? We can only avoid such errors by providing data definitions for each kind of data our functions consume and produce.

The following data definition clears up the ambiguity:

;; name->greeting : Name -> string
;; to create a greeting from the provided name
;;
;; A Name is (make-name String String) where the two strings are
;; the person's first and last names.
(define-struct name (first last))

Practice

Identify whether there is a contract violation or a lack of a data definition. Correct the problem, fixing the code if necessary.

;; a Dog is (define-struct dog (name age breed)) where name is a
;; string, age is a number and breed is a symbol
(define-struct dog (name age breed))

;; dogs-older-than : list-of-Dogs number -> list-of-Dogs
;; All the dogs older than the given age
(define (dogs-older-than dogs age)
  (cond [(empty? dogs) empty]
        [(> (dog-age (first dogs)) age)
         (cons (dog-name (first dogs))
               (dogs-older-than (rest dogs) age))]
        [else (dogs-older-than (rest dogs) age)]))

Identify whether there is a contract violation or a lack of a data definition. Correct the problem, fixing the code if necessary.

;; numbers-between : list-of-numbers -> number-range
;; All the integers from the low number to the high number, inclusive.
(define (numbers-between low high)
  (cond [(> low high) empty]
        [else (cons low
                    (numbers-between (add1 low)
                                     high))]))

Challenge: Identify whether there is a contract violation or a lack of a data definition. Correct the problem, fixing the code if necessary.

;; pairify : list-of-any -> list-of-list
;; to group the elements of the input list into a list of two-element lists
(define (pairify a-list)
  (cond [(or (empty? a-list)
             (empty? (rest a-list)))
         empty]
        [else (cons (cons (first a-list)
                          (first (rest a-list)))
                    (pairify (rest (rest a-list))))]))

Part VI: More Recursion

We want you all to be able to write recursive functions as easily as (cons 1 (cons 2 (cons 3 empty)))), so we're going to practice. In the exercises below, write each function from scratch.

Design a function, string-of, that takes a positive number (n) and a string, and returns a string that contains the given string repeated n times, separated by a space.
```
(string-of 4 "Test")  ;==> "Test Test Test Test"
(string-of 2 "What")  ;==> "What What"
```

Using your function above as a helper, create another function, reducing that takes a number and a string, and returns a list of strings. Each element of the list is the string returned from string-of with a reduced n.

(reducing 4 "Test")  ;==> (cons "Test Test Test Test" 
		     ;          (cons "Test Test Test"
		     ;                (cons "Test Test"
		     ;  	            (cons "Test" empty))))
(reducing 2 "What")  ;==> (cons "What What" (cons "What" empty))

Now design the function lookup that takes a list of Symbols los, and a number n, and returns the n^th symbol of the list.

(lookup (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 0) ;==> 'a
(lookup (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 2) ;==> 'c

Next design the function replace that takes a list of Symbols los, a symbol s, and a number n. The function returns los with the n^th symbol replaced with s.

(replace (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 'new 2) 
    ;==> (cons 'a (cons 'b (cons 'new (cons 'd empty))))

(replace (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 'yay 0) 
    ;==> (cons 'yay (cons 'b (cons 'c (cons 'd empty))))

(replace (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 'end 3)
    ;==> (cons 'a (cons 'b (cons 'c (cons 'end empty))))

Consider the following problem:
Given two lists of strings, return a list of strings that contains all combinations of elements from the first list with elements from the second list.
Let's call the function all-comb. Here's an example:
```
;; This call
(all-comb (cons "Student: " (cons "Faculty: " empty))
          (cons "Mr." (cons "Ms." empty)))

;; Returns
(cons "Student: Mr."
      (cons "Student: Ms."
            (cons "Faculty: Mr."
                  (cons "Faculty: Ms." empty))))
```
How can we design such a function? Well, lets start with a smaller problem. How can we take a string s, and a list-of-strings los, and produce a list that contains the strings from los with s on the front? Call this helper function all-comb-help. Here's an example of its behavior:
```
(all-comb-help "A" (cons "B" (cons "C" (cons "D" empty))))
;==> (cons "AB" (cons "AC" (cons "AD" empty)))
```
Now… how can you put the helper function to work to solve the entire problem? Ask a TA/Tutor if you need help. Hint: you can use the builtin function append (or define your own for practice), which appends two lists.

Challenge: Can you do the above problem without using append?