(list-of problems)

Matt Jadud and Noel Welsh

These problems were either made up or cribbed shamelessly from all over the internet.

When working through these problems, think about the data and your contracts if you get stuck.

1  Naturally Recursive Problems

A list is a special type of structure. It has two differences to the structures we've looked at before:

  1. The functions to create and access members have goofy names

  2. A list can contain a list; it has a recursive structure

The latter is more important than the former. A list is either the empty list, or a list of one element and a list. This recursive structure means that a list can have an arbitrary length. It also establishes the natural pattern of recursion over a list: a cond with two clauses, one to handle the empty list case, one to handle the non-empty case.

The data definition for a list of symbols is

  ;; A list-of-symbol is a
  ;;   empty, OR
  ;;   (cons symbol list-of-symbol)

To construct lists you need to know:

1.1  Constructing Lists

The following procedures all construct lists from lists

  1. Define a procedure called square-list that consumes a (list-of numbers)and returns a list where each element has been squared.

  2. Define a procedure called add-one-to-list that consumes a (list-of numbers)and returns a (list-of numbers)where each element has had one added to it.

  3. Define a procedure called replace-name that consumes a (list-of symbols)and returns a (list-of symbols)where each occurrence of 'noel has been replaced by 'matt.

  4. Define a procedure called double that takes a symbol and a (list-of symbols), and doubles every occurrence of the symbol in the list.

        ;; All examples should evaluate to true.
        (equal? (double 'a '(a b c)) '(a a b c))
        (equal? (double 'foo '(bar geeble woe)) '(bar geeble woe))

1.2  Reducing Lists

The following functions all process a list to single result.

  1. Define a procedure called sum-list that consumes a (list-of numbers) and returns the sum of the elements of that list. The contract for this first procedure has been provided for you:

        ;; sum-list : lon -> number

  2. Define a procedure called mult-list that consumes a (list-of numbers)and returns the result of multiplying all the numbers in the list together.

  3. Define a procedure called average that consumes a (list-of positive-numbers)and returns the result of averaging all the numbers in the list together.

  4. Define a procedure called all-numbers? that consumes a (list-of numbers)and returns true if all the elements of the list are numbers.

  5. Define a procedure called all-symbols? that consumes a (list-of symbols)and returns true if all the elements of the list are symbols.

  6. Define a procedure called all-positive-numbers? that consumes a (list-of numbers)and returns true if all the elements of the list are positive numbers. Note: We will revisit how to abstract over these two procedures later.

  7. Define a procedure called average-wrapper that consumes a (list-of numbers)and averages all the numbers in the list if and only if they are all positive numbers, and returns false otherwise. (Note this procedure breaks our normal rule of attempting to only return one type of data.)

        ;; average-wrapper : (list-of numbers) -> number | boolean
        ;; All examples should be true.
        (= (average-wrapper '(1 2 3)) 2)
        (= (average-wrapper '(2 3 4 5 0)) 3)

  8. Define a procedure called count-symbols that consumes a (list-of symbols)and returns the number of symbols in the list.

  9. Define a procedure called my-length that takes a (list-of thingies)and returns the length of the list. Is this different than the previous question?

  10. Given the data definition

        ;; A Schemer is a 
        ;;   -- first-name      isa symbol
        ;;   -- mental-age      isa positive-number
        ;;   -- walks-on-coals? isa boolean
        (define-struct schemer (first-name 

    write a procedure called extract-mental-ages that consumes a (list-of schemers) and returns a list of mental-ages. You may need to create a few Schemers first.

  11. Define a procedure called average-mental-age that, given a (list-of schemers), computes the average mental age of the Schemers. Hint: You've already written everything you need to do this problem.

  12. Define a procedure called remove that takes a symbol and a (list-of symbols), and returns a list with all occurances of the symbol removed from the list.

  13. Define a procedure called uniqify that takes a (list-of symbols)and removes all duplicates from the list. Hints: Your solution will not be optimal given the tools you have so far. One solution might involve the use of member.

      ;; member : thingie list -> boolean | list

    Member is typically used in any context where a boolean result is expected, although you should not that it returns either #f or the list beginning with the first occurence of the found thingie. member might only work in a full Scheme, as opposed to one of the HtDP learning levels.

  14. Define a procedure called adjacent-sums that takes a (list-of numbers)and returns a (list-of numbers), where adjacent pairs have been added together. Assume the input list is at least two elements in length and even in length.

        ;; All examples should evaluate to true.
        (equal? (adjacent-sums '(1 2 3 4 5 6)) '(3 7 11))
        (equal? (adjacent-sums (adjacent-sums '(1 1 1 1))) '(4))

  15. Define a procedure called adjacent-sums-wrapper that takes a (list-of numbers)and returns a (list-of numbers)if and only if the length of the list is even and greater than two. Otherwise, return false. Hint: Don't forget procedures you have written previously. (Note this procedure breaks our normal rule of attempting to only return one type of data.)

2  Mixed Data

The whole point of covering structures was to provide you with tools that might help you avoid ugly mixed-data situations. We know that this isn't always possible; the next section lets you play with some of the type predicates in Scheme (number?, integer?, symbol?, pair?, list?, boolean?, void?, null?) as you make your way down the list. (Are null? and void? really type predicates?)

One kind of mixed data is the most common Schemely representation of trees. So far, we've been recurring on lists based on the following data definition:

  ;; A LIST is either
  ;;   - empty, or
  ;;   - (cons thing LIST)

where car is used to grab the head, or first item, of the list, and cdr is used to grab the tail, or rest, of the list.

  ;; '(a b c d e f g)
  ;;   ^ -----------
  ;;   |     cdr
  ;;   car 
  ;; These should evaluate to true.
  ;; (symbol? (car '(a b c d e f g)))
  ;; (list?   (cdr '(a b c d e f g)))

This means that when recurring on lists, we have to remember to ask two questions (or, one question and an else):

  1. Is the list empty? (null?)

  2. Is it a list? (pair?, list?)

In moving on to working with trees, we start with the data definition:

  ;; A tree is either
  ;;   - empty, or
  ;;   - (cons thing tree tree)

The critical difference here is that there are two points where we recur. You can already see why we don't like working with Scheme lists for structured trees like a binary tree; it would be much nicer to do something like

  ;; A binary-tree is either
  ;;   - an empty-binary-tree
  ;;   - (make-binary-tree item binary-tree binary-tree)
  (define-struct empty-binary-tree ())
  (define-struct binary-tree (item left right))

In writing code for the latter definition, our code would look like (assuming we were summing the nodes of the tree):

(define (bin-tree-sum bt)
    [(empty-binary-tree? bt) 0]
      (+ (binary-tree-item bt)
         (bin-tree-sum (binary-tree-left  bt))
         (bin-tree-sum (binary-tree-right bt)))]))

It is very clear what we're working with. Our code comes out being structured a little differently when working with Scheme lists of arbitrary data, because a sublist can appear at any point in the list. So, we are constantly asking of the car is a list?, and branching our recursion in two different cond clauses based on the result of this test.

Hope that all helped; if not, good luck.

  1. Define a procedure called deep-count-only-symbols that extends count-only-symbols by recurring into any lists encountered along the way.

        (= (deep-count-only-symbols '(a b (c 4 #f (d e)) (g 3))) 6)

  2. Define a procedure called deep-sum-list that extends sum-list and sums all the numbers encountered in a (deep-list-of numbers).

  3. Define a procedure called add-only-numbers that takes a (list-of thingies)and returns the result of summing the numbers in the list. For your first solution, only traverse the top level of the list.

        ;; All examples should evaluate to true.
        (= (add-only-numbers '(1 a 2 b 3 c (4 d) 5 e)) 11)

  4. Define a procedure called deep-add-only-numbers that extends add-only-numbers by doing a deep addition, traversing down any sublists encountered along the way.

        ;; All examples should evaluate to true.
        (= (add-only-numbers '(1 a 2 b 3 c (4 d) 5 e)) 15)

  5. Define a procedure called gather-symbols that takes a (list-of thingies)and returns a (list-of symbols)built from all the symbols encountered in the list.

        ;; All examples should evaluate to true.
        (= (gather-symbols '(1 #t a foo (3 4 goes) #f shopping))
           '(a foo goes shopping))

    Hint: You may find append useful in this solution. Maybe. I don't know if it is necessary, actually...

3  Bindings, APS

Up until now, you haven't worked with any binding forms in Scheme other than define. There are three common binding forms that you should come to know and love: let, letrec, and lambda.

This section will introduce two of the three.

3.1  let

let binds Scheme values to variables in a lexical scope. This means that variables bound in a let are only visible inside the let. For example

(let ([x 3]
      [y 4])
      ... inside the let ...)

In the snippet above, any code written inside the letwill be able to access the variables x and y, which will have the values 3 and 4, respectively.

letcan bind any Scheme value to a variable. For example, we might want to bind the result of some calculation to use it several times in a nested cond:

  [(null? ls) 0]
    (let ([sqr (square (car ls))]
          [len (length (cdr ls))])
	[(= sqr len)  ... do something ...]
	[(> sqr len)  ... do something else ...]
	[(<= sqr len) ... keep doing things ...]))])

let can appear anywhere a Scheme expression can appear. The value of a let expression is the value of the last expression in the let.

Note that a let will fail at compile time if you attempt something like the following:

(let ([x 4]
      [y (* x 2)])
      ... inside the let ...)

The left-hand sides of the let cannot see the right-hand sides, or bindings, of the let. You could always nest your let expressions if you must have them be visible to each-other:

(let ([x 4])
  (let ([y (* x 2)])
     ...inside both lets...))

This isn't poor form, but if you find yourself nesting too many let expressions, you might want something else.

3.2  letrec

letrec looks just like let, mostly. It's behavior is different, and you will truly be wise when you fully understand letrec.

(letrec ([x 4]
         [y (* x 2)])

will evaluate to 4. In a letrec, the bindings (right-hand sides) are visible to each-other. The example given is a bit trivial; letrec is more often used to bind a recursive procedure that is only needed within the scope of the letrec.

Which leads me to...

3.3  lambda

lambda is the anonymous procedure. When you have been writing

(define (foo x y z) ...)

that has been equivalent to

(define foo (lambda (x y z) ...))

The reason lambda is a binding form is because, inside it's body (the ... above), the identifiers (x, y, z, above) are bound to the values passed in. So lambda is both the anonymous procedure and also a perfectly capable binding form. In fact, it is an insanely powerful binding form, which we will make use of later when we move into the Really Cool Stuff.

The second example makes explicit the fact that define is binding a procedure of one argument to the name foo. For the moment, this is the extent to which we are going to dazzle you with lambda; consider it as nothing more than a way to create a procedure. If you wonder why letrec is something you can aspire to understanding, you can wonder even more why lambda is the Ultimate. Caution grasshopper, and all that.

With what we have so far, we can write procedures like:

;; funky-func : ls -> ls
;; Takes a list, and returns a list of all even, negative numbers and 
;; all sublists composed entirely of symbols with a length equal to 3.
(define funky-func
  (lambda (ls)
    (let ([even-negative? 
            (lambda (n) (and (number? n)
                             (even? n)
                             (> 0 n)))]
	    (lambda (ls)
	      (and (list? ls)
	           (all-symbols? ls)
	           (= (my-length ls) 3)))])
	  [(null? ls) '()]
	    (let ([first (car ls)]
	          [rest  (cdr ls)])
	      (if (or (even-negative? first) 
		      (all-sym-len-3? first))
		  (cons first (funky-func rest))
		  (funky-func rest)))]))))

Whoa. The outermost let binds two weird predicates that we wouldn't want defined at the top level, because they're only going to be used in this procedure, and they're kinda dumb. Note, though, that because I know I'm working on mixed, ugly data, that I included predicates like number? and list? in my helpers; I'm taking advantage of the fact that the and will short-circuit, and evaluate to #f if it fails the first type-check. Ahh.

The second use of let is a bit more gratuitous, but since we don't want to keep re-evaluating (car ls), I bound it to a variable called first. The binding of rest was just because I was binding parts of the list; sometimes it helps to help yourself with a little bit of renaming.

3.4  Accumulator-passing style

Now a (not very impressive) reason why you might want a letrec. Furthermore, I'm going to show you how you can program tail-recursively. Note that this is not a Good Thing necessarily; any Scheme compiler worth its salt will optimize all recursions equally well, so writing in the accumulator-passing style will (generally) not make your code N-times faster.

And we're not here to write fast code, we're here to program Schemely. This way, we can write cool compilers in Scheme that make our code screaming fast. Chez is a pretty good example of this; at 125K lines of code, it has always bootstrapped itself on reasonably current hardware in under 6 seconds. Dybvig would only add features to Chez as he developed it over the years if it improved or maintained the bootstrap time of the compiler. Kinda neat, I think.

Right. I digress.

Take sum-list as an example. In it's naturally recursive form, we might write:

(define sum-list
  (lambda (ls)
      [(null? ls) 0]
	(+ (car ls) (sum-list (cdr ls)))])))

if fed the list '(1 2 3), this will build up a recursive series of calls that look like:

(sum-list '(1 2 3)) 
(+ 1 (sum-list '(2 3)))
(+ 1 (+ 2 (sum-list '(3))))
(+ 1 (+ 2 (+ 3 (sum-list '()))))
(+ 1 (+ 2 (+ 3 0)))
(+ 1 (+ 2 3))
(+ 1 5)

We could, however, add a variable to ``collect'' or ``accumulate'' the result of the additions, instead of building the recursive expression to be evaluated.

So, we add an accumulator

;; sum-list-acc : lon number -> number
;; Sum a list of numbers.
(define sum-list-acc
  (lambda (ls acc)
      [(null? ls) acc]
	(sum-list-acc (cdr ls) (+ (car ls) acc))])))

Now, as we recur through the list, we're not building context. Instead, we're simply increasing the value of acc as we zip down the list.

(sum-list-acc '(1 2 3) 0)
(sum-list-acc '(2 3) 1)
(sum-list-acc '(3) 3)
(sum-list-acc '() 6)

Unfortunately, we have a leaky abstraction now. You shouldn't have to remember to initialize the accumulator; the procedure should just take a list, and be done with it. So, we write a wrapper (call it sum-list*), and use letrec to help us out.

;; sum-list* : lon -> number
;; Sum a list of numbers.
(define sum-list*
  (lambda (ls)
    (letrec ([sum-list-acc
               (lambda (ls acc)                  
                   [(null? ls) acc]
		     (sum-list-acc (cdr ls) (+ (car ls) acc))]))])
      (sum-list-acc ls 0))))

In a letrec, the right-hand side can see the left-hand side, and visa versa. So, we locally bind a procedure of two arguments to sum-list-acc, and use it in the body of the letrec. Because letrec evaluates to the value of the last expression in its body, we're left with the same result as if we called sum-list, with the same number of arguments and same contract, but we've changed the implementation transparently.

(I'm not confident what the local LShift style is, but there is another way to do this with internal defines. Most compilers, I imagine, just expand internal definitions into a letrec anyway, so these two methods are equivalent.

(define sum-list*
  (let ()

    (define sum-list-acc*
      (lambda (ls acc)
        (if (null? ls)
            (sum-list-acc* (cdr ls) (+ (car ls) acc)))))

    (lambda (ls)
      (sum-list-acc ls 0))))

But I'd encourage you not to work on developing styles like this until you are comfortable with what we've been doing. We used this style often in Scorth when writing compiler passes, because each pass would be a procedure with a large, locally defined match expression that we wanted to stay local to the pass we were working on. This saved us nesting a lot of letand letrec expressions.)

  1. Define a procedure called my-reverse that reverses the contents of a list.

  2. Redefine a whole mess of the previous stuff in the accumulator-passing style.

4  Higher Order Functions

By now you've probably noticed a characteristic pattern when recurring on a list. You have a cond expression with two branches:

    [(null? ls) (do-stop-action)]
    [else (do-something-with-car) (recur)])

It would be nice to abstract this pattern in some way so we don't have to keep typing it out. Consider three examples:

  1. Define a procedure called square-list that consumes a (list-of numbers)and returns a list where each element has been squared.

  2. Define a procedure called add-one-to-list that consumes a (list-of numbers)and returns a (list-of numbers)where each element has had one added to it.

  3. Define a procedure called replace-name that consumes a (list-of symbols)and returns a (list-of symbols)where each occurrence of 'noel has been replaced by 'matt.

Write down the contracts of each function. What's similar? What's different?

If we use 'a to stand for any type, we can write the contract of these functions as (list-of 'a) -> (list-of 'a). These functions only differ by what they do to the list they receive.

Assume the function fn is defined to perform the correct operation of each example above. Write a function that assumes fn has been defined correctly and can express each of the three examples above by changing the value of fn. Call this function my-map.

Scheme lets us pass a function as a value. Change your definition of my-map to accept fn as a parameter. It should have a contract my-map : ('a -> 'a) (list-of 'a) -> (list-of 'a)

Now define procedures square, add1 and replace that you can pass to my-map to complete the three examples. Congratulations, you just used a higher-order function!

Often times we won't to write a separate procedure like we did with square, add1 and replace. In these cases we can use a lambda to create the higher order function without giving it a name.

  1. Write square-list using my-map and lambda

  2. Write add-one-to-list using my-map and lambda

  3. Write replace-name using my-map and lambda

  4. Define a function called filter that takes a predicate and a list. It returns a list containing each member of the input list for which the predicate didn't return #f.

  5. Write remove using filter.

  6. Using filter write a function that removes all even numbers from a (list-of numbers).

Let's look at capturing other patterns with higher order functions. A lot of the examples we did above returned a single value such #t or #f, or the sum of all the numbers of the list.

  1. Define a function reduce that takes three values: a function of two arguments, a value (the seed), and a list. The result of applying reduce to the empty list is the seed. The result of applying reduce to a non-empty list is the value of the function applied to the first element of the list and the result of applying reduce to the rest of the list.

  2. Write all-numbers? using reduce

  3. Write all-symbols? using reduce

  4. Write count-symbols using reduce

  5. Write my-length using reduce

  6. Write sum using reduce. sum takes a (list-of numbers)and returns the sum of all the numbers in the list.

  7. Write using sum and my-length. Can you write average using reduce and lambda?

Let's now look at the structure of a list again. There is a simple recursive defintion for a list:

(list-of 'a) (cons 'a (list-of 'a)) nil

This matches the natural recursive form we used to write out first functions on lists. At this point you might be interested to know if there is a function like my-map that we can write that will capture all the possible functions on a list. There is, and it's called fold. It's not hard to write. We already have, except we called in reduce! By choosing appropriate values for the seed we can do any processing we want on a list. Note how the definition of fold mirrors the recursive definition of a list. Each distinct part of list (cons or nill; we call these constructors) has a transformation specified for it (the function and the seed respectively).

  1. Write fold

  2. Write my-reverse using fold

  3. Write uniqify using fold

  4. Write my-map using fold

  5. Write filter using fold

The version of fold we have written in usually known as fold-right. If we had written an accumulator-passing version it would be what is normally known as fold or sometimes fold-left.

For any regular (or algebraic) type we can write a fold function that can express all uses of data of the that type. Better yet we can derive the definition of fold automatically from the type definition. The rigourous theoretical foundations of functional programming allow us to prove these kind of statements.

Last modified: Thurs, Nov 21, 2002, 3:41 pm
HTML conversion by TeX2page 4p4k3