Em Lisp, quando o segundo elemento de um cons é outro cons, o Lisp escreve o resultado sob a forma de uma lista:
> (cons 1 (cons 2 (cons 3 (cons 4 5)))) (1 2 3 4 . 5)
Se o último elemento é a constante nil, o Lisp considera que ela representa a lista vazia, pelo que escreve:
> (cons 1 (cons 2 (cons 3 (cons 4 nil)))) (1 2 3 4)
Esta notação designa-se de lista e é esta que o Lisp usa para simplificar a leitura e a escrita. Uma lista é então uma sequência de elementos. Nesta óptica, a função car devolve o primeiro elemento de uma lista, enquanto a função cdr devolve o resto da lista. A função cons pode ser vista como recebendo um elemento e uma lista e devolve como resultado uma nova lista correspondente à junção daquele elemento no princípio daquela lista. Segundo esta abordagem, a função cons é um construtor do tipo abstracto de informação lista, enquanto as funções car e cdr são selectores.
Uma lista vazia é uma sequência sem qualquer elemento e pode ser escrita como nil ou ainda mais simplesmente (). A lista vazia é o elemento mais primitivo do tipo lista. nil é o constructor do elemento primitivo. Pode-se testar se uma lista é vazia com a função null. A função null é, portanto, um reconhecedor do tipo lista.
> (null nil) t > (null (cons 1 (cons 2 nil))) nil
Exercício 39
Escreva uma função que calcula uma lista de todos os números desde a até b.
Embora as listas não sejam mais do que uma estruturação particular de células cons, podendo por isso ser acedidas com as funções car e cdr, é considerado melhor estilo de programação usar as funções equivalentes first e rest. first devolve o primeiro elemento da lista enquanto rest devolve o resto da lista, i.e., sem o primeiro elemento. Do mesmo modo, o predicado null deve ser substituído pela seu equivalente endp.
> (first (enumera 1 10)) 1 > (rest (enumera 1 10)) (2 3 4 5 6 7 8 9 10)
Exercício 40
Escreva uma função que filtra uma lista, devolvendo uma lista com os elementos que verificam um determinado critério. Utilize-a para encontrar os números pares entre 1 e 20.
Quando se pretendem construir listas pode-se usar também a função list. Esta função recebe qualquer número de argumentos e constroi uma lista com todos eles.
> (list 1 2 3 4) (1 2 3 4) > (first (list 1 2 3 4)) 1 > (rest (list 1 2 3 4)) (2 3 4) > (list 1 2 (list 10 20) 3 4) (1 2 (10 20) 3 4)
Como se vê é possível construir listas dentro de listas. Lisp permite também a construção de listas directamente no avaliador. Idealmente, bastaria escrever (1 2 3 ...), só que isso seria avaliado segundo as regras de avaliação das combinações. O número 1 seria considerado um operador e os restantes elementos da lista os operandos. Para evitar que uma lista possa ser avaliada podemos usar a forma especial quote, que devolve o seu argumento sem o avaliar.
> (quote (1 . (2 . (3 . nil)))) (1 2 3) > (quote (1 2 3 4 5 6 7 8 9 10)) (1 2 3 4 5 6 7 8 9 10) > (filtro (function par?) (quote (1 2 3 4 5 6 7 8 9 10))) (2 4 6 8 10)
Uma vez que as formas especiais quote e function são bastante utilizadas, Lisp fornece um meio de se simplificar a sua utilização. Se dermos ao avaliador uma expressão precedida por uma plica (quote em Inglês), é como se tivessemos empregue a forma especial quote. A substituição é feita durante a leitura da expressão. Do mesmo modo, se precedermos uma função ou uma lambda por #' (cardinal-plica) é como se tivéssemos empregue a forma especial function. 'exp é equivalente a (quote exp), enquanto que #'exp é equivalente a (function exp).
> '(1 2 3 4 5) (1 2 3 4 5) > (filtra #'par '(1 2 3 4 5 6)) (2 4 6)
Exercício 41
O que é que o avaliador de Lisp devolve para a seguinte expressão: (first ''(1 2 3))?
Como é natural, as operações car e cdr podem ser encadeadas:
> (car '(1 2 3)) 1 > (cdr '(1 2 3)) (2 3) > (car (cdr '(1 2 3)) 2 > (car (cdr (cdr '(1 2 3)))) 3
Dado que aquele género de expressões é muito utilizado em Lisp, foram compostas as várias combinações, e criaram-se funções do tipo (caddr exp), que correspondem a (car (cdr (cdr exp))). O nome da função indica quais as operações a realizar. Um ``a'' representa um car e um ``d'' representa um cdr.
> (cadr '(1 2 3)) 2 > (cdddr '(1 2 3)) nil