Implementing list functions in scheme

I've been messing a bit with scheme lately, and one thing I want to get well is list mangling. As you know, lists are the most basic and pure datastructure in scheme (and I think they are the only true datastructure in scheme).

This is why I want to get them right, and I'm rewriting some basic functions related to lists.

First of all, a little explanation of lisp lists in general.

Lists are based on a more simple structure called "cons". A cons is just a pair. The only thing that can contain a cons in the first (car) or the second (cdr) cell are:

• string
• number
• symbol
• cons

Yeah, pretty simple, right? The funny thing is that with cons containing conses, we can write all kind of datastructures.

First we'll see two axioms that must always be true related to conses.

(= x (car (cons x y)))
(= y (cdr (cons x y)))

Everything that guarantees this is a cons. Well, at least at this level...

a cons is represented by (x . y) , and a cons with another cons in the cdr would be (x . ( y . z))

A list is a special kind of cons with a determined structure.

( x . (y . (z . nil))) . A way to visually simplify this is ( x y z ) . That means that in a list of n elements, there are n conses linked through cdr's, with the last cdr pointing to nil. If you had to build (1 2 3) with conses, you could do it with (cons 1 (cons 2 (cons 3 nil))) .

Here I show the few scheme functions I wrote along with some explanations that davazp kindly gave me at #emacs-es and #lisp-es.

Theese are my first versions of some functions.

	(define (build-list n)
	(cond ((= 1 n) (list n))
	(else (append (build-list (- n 1)) (list n) ))))
	(define (build-reverse a)
	(cond ((= a 0) (list a))
	(else (cons a (build-reverse (- a 1))))))
	(define (my-reverse l)
	(cond ((null? l) '())
	(else (append (my-reverse (cdr l)) (list (car l))))))
	(define (my-append l1 l2)
	(if (null? l1) l2
	(cons (car l1) (append (cdr l1) l2))))
	(define (my-length l)
	(if (null? l) 0
	(+ 1 (my-length (cdr l)))))
	(define (last-pair l)
	(if (null? (cdr l)) (car l)
	(last-pair (cdr l))))

view raw my-list-funcs.scm hosted with ❤ by GitHub

Here we see build-list can be abstracted to a more general (and easier to write) procedure called build-range, and I just call it with a start point = 1.

On the reverse function, we can use a different "happy idea".

	(define (build-list x)
	(define (range a b)
	(if (> a b) '()
	(cons a (range (+ a 1) b))))
	(range 1 x))
	(define (my-cool-reverse l)
	(define (my-reverse l1 l2)
	(if (null? l1)
	l2
	(my-reverse (cdr l1)
	(cons (car l1) l2))))
	(my-reverse l '()))

view raw list-pro.scm hosted with ❤ by GitHub

Enough for today. Thanks to davazp and other #emacs-es -ers for their help and motivation.