Do you think Computer Science equals building websites and mobile apps?
Are you feeling that you are doing repetitive and not so intelligent work?
Are you feeling a bit sick about reading manuals and copy-pasting code and keep poking around until it works all day long?
Do you want to understand the soul of Computer Science?
If yes, read SICP!!!
Sequence is an important data structure in any programming language, especially in Lisp. In this article, we will look at how it is built and what can we do with it.
Pair is a very simple data structure, it glues two objects together, and provides selectors for each of them.
In Scheme the function
cons is used to create pairs. For example,
(cons 1 2). This can be illustrated by using the box-and-pointer notation:
Each object is shown as a pointer to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a number. The box for a pair is actually a double box, the left part containning the first object of the pair, and the right part containning the second one.
car is the selector for the first object and
cdr is the selector for the second object.
(car (cons 1 2)) ;;=> 1 (cdr (cons 1 2)) ;;=> 2
Let’s say we want to combine 1, 2, 3, 4 using pairs. There are actually many ways of doing this. For example:
;; Two ways of combining 1,2,3,4 using pairs (cons (cons 1 2) (cons 3 4)) (cons (cons 1 (cons 2 3)) 4)
They can be illustrated respectively as follows:
Now we can construct sequences(an ordered collection of data objects) by chaining pairs.
For example to construct sequence of 1, 2, 3 and 4, we can do:
(cons 1 (cons 2 (cons 3 (cons 4 '()))))
Such a sequence of pairs formed by nested
cons is called a list, and Scheme provides a primitive called
list to help with creating lists.
;; the followings are the same (list 1 2 3 4) (cons 1 (cons 2 (cons 3 (cons 4 '()))))
car and cdr
car selects the first item in the list and
cdr select the rest items (a sublist) of the list.
(car (list 1 2 3 4)) ;; 1 (cdr (list 1 2 3 4)) ;; (2 3 4)
nth element of the list
We implement this by
cdring down the list and stop at the right element.
(define (list-ref items n) (if (= n 0) (car items) (list-ref (cdr items) (- n 1))))
The Length of the List
Sometimes we need to
cdring down the whole list, so we need a way to stop. Primitive
null? tells if a list if an empty list.
(null? '()) ;Value: #t (null? (list 1 2)) ;Value #f
Now let’s implement a function to calculate the length of the list.
(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)))))
We can also write a iterative version.
(define (length items) (define (iter items result) (if (null? items) result (iter (cdr items) (+ 1 result)))) (iter items 0))
Append Two Lists
This is implemented by cons up a result list while cdring down a list.
(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2))))
Write a function to reverse a list.
(define (reverse items) (if (null? items) '() (append (reverse (cdr items)) (list (car items)))))
Write a function to get the last pair in the list.
(define (last-pair items) (cond ((null? items) '()) ((null? (cdr items)) items) (else (last-pair (cdr items)))))
Part II of this series can be found here.