CodePlexProject Hosting for Open Source Software

Lists are represented in scheme in a form of nested *pairs*, where the first element is the next value in the list, and the 2nd - next pair. You cal also imagine this as binary tree, where all child nodes are always connected to
the right branch.

The keyword*cons* used to construct such pairs, and the last pair is terminated with
*empty* (comments start with ';').

To access the list you can use*first* to get the current element, or *rest* to get remaninig part of the list (some people are used to
*car* and *cdr* operators, which are synonyms to *first* and *rest* accordingly).

Let's now see a simple example of recursive function which iterates such list, and calculates the total number of elements:

It first checks whether reached the end of the list*(empty? l)*, and returns 0 for empty list, or number of elements in
*rest* plus 1.

Similar function to find the largest element:

(this implementation assumes that all numbers are positive)

And final example, which, instead of returning single value, constructs a new list, where each element is generated by doubling original element at same position:

The line (cons (* (first l) 2) (multiply (rest l))))) returns a pair, where the first element is*(* (first l) 2)* - first (current) element in the list miltiplied by 2, and the second part of the pair is the value (the list) returned by recursive call to same function on the
*rest* of original list.

; Define list (10, 15, 11, 7) (define lst (cons 10 (cons 15 (cons 11 (cons 7 empty)))))

The keyword

To access the list you can use

> (first lst) 10 > (rest lst) (cons 15 (cons 11 (cons 7 empty)))

Let's now see a simple example of recursive function which iterates such list, and calculates the total number of elements:

(define (count l) (if (empty? l) 0 (+ 1 (count (rest l))))) > (count lst) 4

It first checks whether reached the end of the list

Similar function to find the largest element:

(define (largest l) (if (empty? l) 0 (if (> (first l) (largest (rest l))) (first l) (largest (rest l)))))

(this implementation assumes that all numbers are positive)

And final example, which, instead of returning single value, constructs a new list, where each element is generated by doubling original element at same position:

(define (multiply l) (if (empty? l) empty (cons (* (first l) 2) (multiply (rest l))))) > (multiply lst) (cons 20 (cons 30 (cons 22 (cons 14 empty))))

The line (cons (* (first l) 2) (multiply (rest l))))) returns a pair, where the first element is

Last edited Nov 30, 2007 at 4:27 AM by migo, version 1