CSc 520 - Principles of Programming Languages
38 : Scheme -- List Processing

Christian Collberg

Department of Computer Science

University of Arizona

1 Constructing Lists

• The most important data structure in Scheme is the list.
• Lists are constructed using the function cons:
  1#1
  cons returns a list where the first element is first, followed by the elements from the list rest.

2#2

2 Constructing Lists...

• There are a variety of short-hands for constructing lists.
• Lists are heterogeneous, they can contain elements of different types, including other lists.

3#3

3 Examining Lists

• (car L) returns the first element of a list. Some implementations also define this as (first L).
• (cdr L) returns the list L, without the first element. Some implementations also define this as (rest L).
• Note that car and cdr do not destroy the list, just return its parts.

4#4

4 Examining Lists...

• Note that (cdr L) always returns a list.

5#5

5 Examining Lists...

• A shorthand has been developed for looking deep into a list:
  6#6
  Each "a" stands for a car, each "d" for a cdr.
• For example, (caddar L) stands for
  7#7
  

8#8

6 Lists of Lists

• Any S-expression is a valid list in Scheme.
• That is, lists can contain lists, which can contain lists, which...

9#9

7 List Equivalence

• (equal? L1 L2) does a structural comparison of two lists, returning #t if they ``look the same''.
• (eqv? L1 L2) does a ``pointer comparison'', returning #t if two lists are ``the same object''.

10#10

8 List Equivalence...

• This is sometimes referred to as deep equivalence vs. shallow equivalence.

11#11

9 Predicates on Lists

• (null? L) returns #t for an empty list.
• (list? L) returns #t if the argument is a list.

12#12

10 List Functions -- Examples...

13#13

11 Recursion over Lists -- cdr-recursion

• Compute the length of a list.
• This is called cdr-recursion.

14#14

12 Recursion over Lists -- car-cdr-recursion

• Count the number of atoms in an S-expression.
• This is called car-cdr-recursion.

15#15

13 Recursion Over Lists -- Returning a List

• Map a list of numbers to a new list of their absolute values.
• In the previous examples we returned an atom -- here we're mapping a list to a new list.

16#16

14 Recursion Over Two Lists

• (atom-list-eq? L1 L2) returns #t if L1 and L2 are the same list of atoms.

17#17

15 Recursion Over Two Lists...

18#18

16 Append

19#19

17 Deep Recursion -- equal?

20#20

18 Patterns of Recursion -- cdr-recursion

• We process the elements of the list one at a time.
• Nested lists are not descended into.

21#21

19 Patterns of Recursion -- car-cdr-recursion

• We descend into nested lists, processing every atom.

22#22

20 Patterns of Recursion -- Maps

• Here we map one list to another.

23#23

21 Example: Binary Trees

• A binary tree can be represented as nested lists:
  24#24
  
• Each node is represented by a triple
  25#25
  
• Empty subtrees are represented by ().

22 Example: Binary Trees...

26#26

23 Example: Binary Trees...

27#27

24 Binary Trees using Structures

• We can use structures to define tree nodes.

28#28

25 Binary Trees using Structures...

29#29

26 Homework

• Write a function swapFirstTwo which swaps the first two elements of a list. Example: (1 2 3 4) 30#30 (2 1 3 4).
• Write a function swapTwoInLists which, given a list of lists, forms a new list of all elements in all lists, with first two of each swapped. Example: ((1 2 3) (4) (5 6)) 30#30 (2 1 3 4 6 5).