Lists! Lists! Lists!

This lab gives you an opportunity to work with lists, a topic to which we'll be returning in the future.

Finger Exercises

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

Consider the following definitions:

(define-struct empty-lon ())
(define-struct lon (num tail))
;; A LoN (List of Numbers) is one of:
;; - (empty-lon)
;; - (make-lon Number LoN)

;; Examples:

(make-lon 1 (make-lon 2 (make-empty-lon)))
(make-lon -3 (make-lon 3/4 (make-lon .2 (make-empty-lon))))
(make-lon 1 (make-lon 1
      (make-lon 2 (make-lon 3 (make-lon 5
        (make-lon 8 (make-lon 13 (make-empty-lon))))))))

For each of the following, make a structure and data definition. Then make at least 3 examples of each.

List Calisthenics

  1. Write the function sum, which consumes a list of numbers and returns their sum.

  2. Write the function product which consumes a list of numbers and returns their product.

  3. Design the function join-los which consumes a list of strings and concatenates them. For example,

    > (define a-list-of-strings
                      (make-los "Strings" (make-empty-los))))))
    > (join-los a-list-of-strings)
  4. Design the function join-los-with-space which consumes a list of strings and concatenates them, with space " " characters in-between. For example:

    > (join-los-with-space a-list-of-strings)
    "A List Of Strings "
  5. 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:

    > (join-los-with-string "!!!" a-list-of-strings)
    > (join-los-with-string " wheeeeeee " a-list-of-strings)
    "A wheeeeeee List wheeeeeee Of wheeeeeee Strings wheeeeeee "
    > (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?

  6. Design a function create-kandinsky which consumes a list of images and overlays them all on a 400 x 400 empty scene.

  7. Here is the data definition for a list of stock trades:
    ;; A list-of-trades is one of:
    ;; -- empty
    ;; -- (cons (make-stock-sale string string number number) list-of-trades)
    ;; -- (cons (make-stock-purchase string string number number) list-of-trades)
    (define-struct stock-sale (seller company shares price-per-share))
    (define-struct stock-purchase (buyer 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).

  8. Design a function that takes a list of stock trades and a string, where the string represents an entity that buys and sells stocks, and returns the net profit for that entity (that is, stock sales are added and stock purchases are subtracted, starting at 0).
  9. Bonus: Alter the data definition for stock trades to factor out the common data (company, shares, price-per-share) into a separate structure that is then used in a new new-list-of-trades union. Copy, rename, and adjust the functions you wrote on list-of-trades to operate on new-list-of-trades instead.

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
;; - (empty-seq)
;; - (make-seq Any Seq)

Now we can define our own implementation of lists, using empty-seq and seq structures. Write the following functions:

Also, define a value mpty which is the empty Seq. None of these functions should be at all complicated.

Cons-(and kons!)-tructing Lists

Consider the following data definition:

;; A SoN (sequence of Numbers) is one of
;; - mpty
;; - (kons Number SoN)

Rewrite the data definitions and examples from the Finger Exercises using kons and mpty.

Redesign the functions from List Calisthenics using kons, head and tail.

Now, check that your work was correct by rewriting these functions one more time using cons, first, rest and empty. (Isn't it convenient that the names of our kons-style functions are so similar to Beginning Student's?)

Fun and Games

For those who finish the rest early:

Design the snake game from top to bottom.