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.
; Define list (10, 15, 11, 7)
(define lst (cons 10 (cons 15 (cons 11 (cons 7 empty)))))

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).
> (first lst)
> (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) 
      (+ 1 (count (rest l)))))

> (count lst)

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:
(define (largest l) 
  (if (empty? l)
      (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)
      (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 (* (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.

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


No comments yet.