Lists

Lists

Robbert Haarman

2010-12-11


Introduction

One of the most common and powerful data structures in Scheme is the list. Scheme comes with a set of procedures to elegantly and efficiently work with lists.

A list is actually a chain of pairs, where each cdr contains the next element, until the last cdr, which contains an empty list. E.g. the list of integers from 1 through 3 is represented as (1 . (2 . (3 . ()))). This is abbreviated more legibly to (1 2 3).


Operations on Lists


; Create lists
(list 1 2 3) ; => (1 2 3)
(cons 1 (cons 2 (cons 3 (cons '())))) ; => (1 2 3)
'(1 2 3) ; => (1 2 3)

; Test if something is a list
(list? '(1 2 3)) ; => #t
(list? "123")) ; => #f

; A list is also a pair
(pair? '(1 2 3)) ; => #t
(car '(1 2 3)) ; => 1
(cdr '(1 2 3)) ; => (2 3)

; But a pair is not a list
(list? (cons 1 2)) ; => #f

; Length of a list
(length '(1 2 3)) ; => 3

; Return element of a list
(list-ref '(1 2 3) 1) ; => 2

; Append lists
(append '(1 2 3) '(one two three)) ; => (1 2 3 one two three)

; Some operations on lists
(map - '(1 2 3)) ; => (-1 -2 -3)
(for-each display '(1 2 3)) ; outputs "123"
(reverse '(1 2 3)) ; => (3 2 1)

Quote and Quasiquote

Recall that for symbols, we can get the symbol itself, rather than its value, by quoting it (e.g. 'foo). The same can be done for lists (e.g. '(1 2 3))), and in fact any other data type.

There is variant of quote called quasiquote which can be very useful when working with lists. Quasiquote can be used to quote lists just like the normal quote, but it allows certain elements of the list to be unquoted using commas. For example

`(foo bar ,x ,y 14)

would be the list consisting of the literal symbols foo and bar, followed by the values of x and y, followed by 14. The same value could have been obtained using list, but quasiquote is sometimes more convenient.

Besides unquote, there is also unquote-splicing, written ,@. This can be used to insert the elements of another list in a quasiquoted list, like so:

(define foo '(1 2 3))
(define bar '(4 5 6))
(display `(,@foo ,@bar ,@(reverse bar) ,@(reverse foo)))
Valid XHTML 1.1! Valid CSS! Viewable with Any Browser