Posted in Simply Scheme, Unit One

Simply Scheme: Chapter 17 – Lists

Yay! Lists finally. Super excited. This was a really meaty chapter. Just a ton of information.

Lists Overview:

  • Like a sentence, but elements of a list can be anything
    • words
    • #t/#f
    • procedures
    • other lists
      • known as a sublist
      • a structured list is a list that contains sublists
  • Lists are self-referential, meaning they can contain elements the same as themselves, whereas sentences are not
  • Sentences were added to Scheme by the writers of this book and are not an inherent feature of Scheme. Lists are the backbone of Lisp

Selectors and Constructors

  • car: used to select the first element of a list (like first)
  • cdr: used to select all but the first element of a list (like bf)
    • pronounced “could-er”
  • null?: checks to see if a list is empty (like empty?)
  • list: takes any number of arguments and returns a list with those arguments as its elements
    • remember, you can have a list of lists
  • cons: when you already have a list and want to add a new element. takes two arguments, an element and a list (in that order) and returns a new list whose car is the first argument and whose cdr is the second.
    • requires that its second element be a list
  • append: combines the elements of two or more lists into a larger list
    • rather than create a list of lists, merges two lists together
  • car and cdr can be combined up to four deep for something like:
    • cddadr which means (cdr (cdr (car (cdr something))))
      • cddadr the letters in between the “c” and the “r” are the important ones.
      • note the order of the “Ds” and the “As” match the order of the function above.
      • most commonly used are:
        •  cadr: second element of a list
        • caddr: third element
        • cadddr: fourth element

Higher-Order Functions

  • Map: takes two arguments, a function and a list, and returns a list containing the result of applying the function to each element of the list (like every)
    • Standard Scheme primitive
  • Filter: takes a function and a list as its arguments, returns a list containing only those elements of the argument list for which the function returns a true value (like keep)
    • elements may be sublists and their structure is preserved in the result.
    • Not a standard Scheme primitive, but a universal convention
  • Reduce: works like accumulate
    • not a scheme primitive

Other Primitives for Lists

  • list?: predicate that returns #t if the argument is a list and #f otherwise
  • member: like member? except that the second argument must be a list. Instead of returning #t, it returns the portion of the argument starting with the element equal to the first argument or #f
    • for example:
      • (member ‘d  ‘(a b c d e f g) ==> (defg)
      • (member ‘h ‘(a b c d e f g) ==> #f
    • considered a semipredicate: returns other values than just #t and #f, but works as a predicate because any non-#f value is considered true
  • list-ref: works like item, except that it starts at 0 instead of 1 and takes its arguments in the other order.
    • (list-ref ‘(happiness is a warm gun) 3) ==> warm
  • length: just like count except it doesn’t work on words.

Association Lists

  • defined as a list of names and corresponding values
  • also known as an a-list
  • Assoc: a primitive that looks up a name in an a-list
    • > (assoc ‘george ‘((john lennon)(paul mccartney)(geroge harrison)(ringo starr)))
      • returns (george harrison)
    • if the value doesn’t exist it returns #f, so it is also a semipredicate

Functions That Take Variable Numbers of Arguments

  • . – In listing the formal parameters of a procedure, you can use a dot just before the last parameter to mean that that parameter represents any number of arguments, including zero. The value that will be associated with this parameter when the procedure is invoked will be a list whose elements are the actual argument values.
    • rest parameter: a parameter that follows a dot and therefor represents a variable number of arguments
    • There can be only one formal parameter after the dot, but any number before it
  • apply: invokes the given procedure with the elements of the given lists as its arguments and returns whatever value the procedure returns.

Pitfalls

  • Remember not to use List as a formal parameter, often used alternatives are:
    • lst
    • L
    • seq
  • Pair or Dotted pair: The result you get when you cons onto something that isn’t a list
    • “if dots appear in your result you’re consing backwards”

I haven’t mentioned in a while, but just as a reminder: at times there may be a direct quote from the text that is not enclosed in quotation marks. This will most often occur when defining a term.


Boring Exercises

17.1  What will Scheme print in response to each of the following expressions? Try to figure it out in your head before you try it on the computer. For this one I’m going to put my responses below each of the questions. My responses will be in bold.

> (car '(Rod Chris Colin Hugh Paul))
Rod
> (cadr '(Rod Chris Colin Hugh Paul))
Chris
> (cdr '(Rod Chris Colin Hugh Paul))
(Chris Colin Hugh Paul)
> (car 'Rod)
I put Rod, but it would be an error.
> (cons '(Rod Argent) '(Chris White))
I thought it would be (Rod Argent Chris White),
but actually it's ((rod argent)) chris white)
> (append '(Rod Argent) '(Chris White))
(rod Argent Chris White)
> (list '(Rod Argent) '(Chris White))
((rod argent)(chris white))
> (caadr '((Rod Argent) (Chris White)
           (Colin Blunstone) (Hugh Grundy) (Paul Atkinson)))
Chris
> (assoc 'Colin '((Rod Argent) (Chris White)
		  (Colin Blunstone) (Hugh Grundy) (Paul Atkinson)))
(colin blunstone)
> (assoc 'Argent '((Rod Argent) (Chris White)
		   (Colin Blunstone) (Hugh Grundy) (Paul Atkinson)))
#f

17.2  For each of the following examples, write a procedure of two arguments that, when applied to the sample arguments, returns the sample result. Your procedures may not include any quoted data.

> (f1 '(a b c) '(d e f))
((B C D))

> (f2 '(a b c) '(d e f))
((B C) E)

> (f3 '(a b c) '(d e f))
(A B C A B C)

> (f4 '(a b c) '(d e f))
((A D) (B C E F))
  1. (define (f1 L1 L2)
      (append (cdr L1)(list (car L2))))
  2. (define (f2 L1 L2)
      (list (cdr L1)(cadr L2)))
  3. (define (f3 L1 L2)
      (append L1 L1))
  4. (define (f4 L1 L2)
      (list (list (car l1)(car l2))(append (cdr l1)(cdr l2))))

17.3  Describe the value returned by this invocation of map:

> (map (lambda (x) (lambda (y) (+ x y))) '(1 2 3 4))
  • I assumed that it would add each of the numbers to each of the other numbers, but it just throws an error when I try, so I’m not sure…

Real Exercises

17.4  Describe the result of calling the following procedure with a list as its argument. (See if you can figure it out before you try it.)

(define (mystery lst)
  (mystery-helper lst '()))

(define (mystery-helper lst other)
  (if (null? lst)
      other
      (mystery-helper (cdr lst) (cons (car lst) other))))
  • It will reverse the order of the list

17.5  Here’s a procedure that takes two numbers as arguments and returns whichever number is larger:

(define (max2 a b)
  (if (> b a) b a))

Use max2 to implement max, a procedure that takes one or more numeric arguments and returns the largest of them.

  • (define (max2 . b)
      (max-helper (cdr b) (car b)))
    
    (define (max-helper b sofar)
      (if (null? b) sofar
          (max-helper (cdr b)
                      (if (> (car b) sofar) (car b) sofar))))

17.6  Implement append using carcdr, and cons. (Note: The built-in append can take any number of arguments. First write a version that accepts only two arguments. Then, optionally, try to write a version that takes any number.)

  • (define (append-test L1 L2)
      (append (cons (car L1)(cdr L2))))
  • (define (append-test L1 . L2)
     (append (cons (car L1)(cdr L2))))

17.7  Append may remind you of sentence. They’re similar, except that append works only with lists as arguments, whereas sentence will accept words as well as lists. Implement sentence using append. (Note: The built-in sentence can take any number of arguments. First write a version that accepts only two arguments. Then, optionally, try to write a version that takes any number. Also, you don’t have to worry about the error checking that the real sentence does.)

  • (define (sentence2 a b)
      (cond ((and (word? a)
                  (not (word? b)))
              (append (list a) b))
            ((and (word? b)
                  (not (word? a)))
              (append a (list b)))
            ((and (word? a)
                  (word? b))
              (append (list a)(list b)))
            (else (append a b))))
    
    (define (sentence3 . b)
      (cond ((null? (car b))'())
            ((word? (car b))(append (list (car b)) (sentence3 (cdr b))))
            (else (append (car b)(sentence3 (cdr b))))))
  • The sentence3 one was tough, but I finally got it…

17.8  Write member.

  • (define (member2 a b)
      (cond ((null? b)#f)
            ((equal? a (car b)) b)
            (else (member2 a (cdr b)))))

17.9  Write list-ref.

  • (define (list-ref2 L n)
      (helper L n 0))
    
    (define (helper L n n2)
      (cond ((null? L)'error)
            ((= n n2) (car L))
            (else (helper (cdr L) n (+ 1 n2)))))

17.10  Write length.

  • (define (length2 L)
      (length-helper L 0))
    
    (define (length-helper L n)
      (cond ((null? L) n)
            (else (length-helper (cdr L) (+ n 1)))))

17.11  Write before-in-list?, which takes a list and two elements of the list. It should return #t if the second argument appears in the list argument before the third argument:

> (before-in-list? '(back in the ussr) 'in 'ussr)
#T

> (before-in-list? '(back in the ussr) 'the 'back)
#F

The procedure should also return #f if either of the supposed elements doesn’t appear at all.

  • (define (before-in-list? L i1 i2)
      (cond ((null? L)#f)
            ((equal? i1 (car L))(member? i2 (cdr L)))
            (else (before-in-list? (cdr L) i1 i2))))
  • Is it cheating to still use member? Going with it for now…

17.12  Write a procedure called flatten that takes as its argument a list, possibly including sublists, but whose ultimate building blocks are words (not Booleans or procedures). It should return a sentence containing all the words of the list, in the order in which they appear in the original:

> (flatten '(((a b) c (d e)) (f g) ((((h))) (i j) k)))
(A B C D E F G H I J K)
  • So played around with this one for a really long time. Finally referenced the solutions by buntine for some help.
  • The used the word? predicate, which I had guessed as much, but the rest of it I was just making far more complicated than it should have been. The solution buntine provided is as follows:
  • (define (flatten l)
        (cond ((null? l) '())
              ((word? l) (list l))
              (else (append (flatten (car l))
                            (flatten (cdr l))))))

17.13  Here is a procedure that counts the number of words anywhere within a structured list:

(define (deep-count lst)
  (cond ((null? lst) 0)
	((word? (car lst)) (+ 1 (deep-count (cdr lst))))
	(else (+ (deep-count (car lst))
		 (deep-count (cdr lst))))))

Although this procedure works, it’s more complicated than necessary. Simplify it.

  • I needed help on this one again from buntine. I’ll get there.
  • (define (deep-count lst)
       (cond ((null? lst) 0)
             ((word?  1))
             (else (reduce + (map (lambda (n) (deep-count n)) lst)))))

17.14  Write a procedure branch that takes as arguments a list of numbers and a nested list structure. It should be the list-of-lists equivalent of item, like this:

> (branch '(3) '((a b) (c d) (e f) (g h)))
(E F)

> (branch '(3 2) '((a b) (c d) (e f) (g h)))
F

> (branch '(2 3 1 2) '((a b) ((c d) (e f) ((g h) (i j)) k) (l m)))
H

In the last example above, the second element of the list is

((C D) (E F) ((G H) (I J)) K)

The third element of that smaller list is ((G H) (I J)); the first element of that is (G H); and the second element of that is just H.

  • Easier than anticipated…
  • (define (helper n lst)
      (if (= n 1)
          (car lst)
          (helper (- n 1)(cdr lst))))
    
    (define (branch nlst lst)
      (if (= (length nlst) 1)
           (helper (car nlst) lst)
           (branch (cdr nlst)(helper (car nlst) lst))))

17.15  Modify the pattern matcher to represent the known-values database as a list of two-element lists, as we suggested at the beginning of this chapter.

  • I’ll be skipping over this one. The chapter for the pattern matcher isn’t one that was assigned as part of CS3

17.16  Write a predicate valid-infix? that takes a list as argument and returns #t if and only if the list is a legitimate infix arithmetic expression (alternating operands and operators, with parentheses—that is, sublists—allowed for grouping).

> (valid-infix? '(4 + 3 * (5 - 2)))
#T

> (valid-infix? '(4 + 3 * (5 2)))
#F
  • (define (valid-infix? lst)
      (cond ((and (= (length lst) 1)
                  (number? (car lst))) #t)
            ((list? (car lst))(valid-infix? (car lst)))
            ((and (number? (car lst))(operand? (cadr lst)))
                (valid-infix? (cddr lst)))
            (else #f)))
  • Getting the sublists to work was a little tricky, but I got it.

Total amount of time spent on this chapter: 8 hours and 7 minutes