CMSC 15100 — Lecture 11

Lists

It turns out that what we have just described are actually lists. Lists happen to be a fundamental structure in programming, functional programming, and in Racket. In fact, Lisp, the family of languages to which Racket belongs, is named so for List Processor.

Racket has built-in facilities for working with lists. This means we will need to translate the bespoke UnaryTree concepts that we've played with into their actual Racket built-in counterparts.

A list is either

• empty, denoted '(), or
• a pair containing a value (the first value, sometimes called the head of the list) and a list (the rest of the list, sometimes called the tail of the list), denoted by the pattern (cons first rest).

The fact that lists are really made of pairs is intriguing, but when you really sit down and think about it, our UnaryTree structure Cons is really a pair, since it contains exactly two fields: root and sub. So we could hypothetically envision it as a (Pairof A (UnaryTree A)).

Lists have type (Listof A), where A is a type variable as in our previous definitions. So just as we had (Tree Integer) for a binary tree of Integers, we would have (Listof Integer) for a list of Integers.

Our structure, Cons is meant to emulate the built-in function cons, which is short for construct. We can use this to draw analogies to the built-in functions for working with lists.

• The constructor for lists is called cons. In Racket, this is a function of type

  
  (All (A) (-> A (Listof A) (Listof A)))
      

  and is used in the same way that we've been using our bespoke structure, Cons. So to create a "node" containing 23, one writes

  
  (cons 23 '())
      

  and if we wanted a longer list, we could write

  
  (cons 2 (cons 8 (cons 104 (cons 23 '()))))
      

  Note that unlike our structure, the built-in cons is really a function. Despite this, cons can still be used in the same way as structure patterns in match statements.
• As described earlier, the view of a list is as the "first" or "root" value and the "rest" of the list. Just as our structure Cons would have selectors for the root and subtree (which are Cons-root and Cons-sub, respectively), we have the following functions:
  • first is a function of type (All (A) (-> (Listof A) A)), which when given a list produces the first element of that list. For example,

    
    (first (cons 2 (cons 8 (cons 104 (cons 23 '())))))
            

    produces the value 2, the first value in the list.
  • Similarly, the function rest is of type (All (A) (-> (Listof A) (Listof A))), which when given a list produces the tail of that list. For example,

    
    (rest (cons 2 (cons 8 (cons 104 (cons 23 '())))))
            

    produces the list (cons 8 (cons 104 (cons 23 '()))). Also keep in mind that the empty list is still a list, so

    
    (rest (cons 3 '()))
            

    produces the list '().

  One can also use pattern matching just as before. To do this, let's look at one of our functions on UnaryTrees and turn it into a function for lists.

  
  (: size (All (A) (-> (Listof A) Integer)))
  ;; Computes the number of nodes in a list
  (define (size xs)
    (match xs
      ['() 0]
      [(cons head tail) (+ 1 (size tail))]))
      

  It's time to play spot the differences. The first thing we notice is the change of the function type. Instead of using UnaryTree, we use Listof.

  Next, maybe not as important, it'd be kind of silly to call a list t, since "list" doesn't start with a "t" like "tree" does. Instead, functional programmers tend to use the name xs, which is read "$x$'s".

  More substantially, there are some notable changes to the patterns that we use in our match statements. As noted before, '() is used to denote an empty list. Then to split up a list into its head and the rest of the list, we use (cons h t), where h is the name you want to give to the "first" element, and t is the name you want to give to the "rest" of the list.

  One of the conveniences of working with a built-in structure is that there are many useful functions. For example, if you are tired of writing

  
  (cons 1 (cons 2 (cons 4 (cons 8 (cons 16 (cons 32 '()))))))
      

  you can write the following instead:

  
  (list 1 2 4 8 16 32)
      

  The list function does exactly what it sounds like: it constructs a list out of the values you give it. The result of the two previous expressions is the same.

  Another very handy function is the append function. Suppose we have two lists and we want to combine them into one, with all the elements of the first list followed by the elements of the second, like

  
  (append (list 1 2 4) (list 3 7 9))
      

  This produces the list

  
  (cons 1 (cons 2 (cons 4 (cons 3 (cons 7 (cons 9 '()))))))
      

  While this is a built-in function, we can take a moment to think through it. What is the formal definition of append? We can take some inspiration from string concatenation. Of course, in reality, these are the same definitions.

  The "append" (for lack of a better term) of two lists $\ell_1$ and $\ell_2$, denoted $\ell_1 \odot \ell_2$, is defined

  • if $\ell_1$ is empty, then $\ell_1 \odot \ell_2 = \ell_2$,
  • if $\ell_1$ is non empty, then it is a pair $(h_1, t_1)$. Then $\ell_1 \odot \ell_2 = (h_1, t_1 \odot \ell_2)$.

  This is all very mathematical, but as usual, it translates into Racket quite naturally.

  
  (: append (All (A) (-> (Listof A) (Listof A) (Listof A))))
  ;; Given two lists lst1 and lst2, create a list with values of lst1
  ;; followed by values of lst2
  (define (append lst1 lst2)
    (match lst1
      ['() lst2]
      [(cons head tail) (cons head (append tail lst2))]))
      

  We can "translate" the other unary tree functions we wrote to using lists:

  
  (: strings-lengths (-> (Listof String) (Listof Integer)))
  ;; Given a list of strings, computes a list with each string's length
  (define (first-letter t)
    (match t
      ['() '()]
      [(cons first rest) (cons (string-length first) 
                               (strings-lengths rest))]))
  
  (: lte140 (-> (Listof Integer) (Listof Integer)))
  ;; Given a list of integers, produce a list with only those 
  ;; integers that are at most 140
  (define (lte140 t)
    (match t
      ['() '()]
      [(cons first rest) (if (<= first 140)
                             (cons first (lte140 rest))
                             (lte140 rest))]))
  
  (: points (-> (Listof (Pairof Integer Integer)) Image))
  ;; Plots points (given in list), relative to (0,0) at top left.
  (define (points pts)
    (match pts
      ['() (empty-scene 100 100)]
      [(cons (Pairof x y) rest) (place-image (circle 2 'solid 'red)
                                             x y
                                             (points rest))]))