13. Lists

Let's review how to work with lists and dig deeper into higher-order functions.

To understand how to access the elements of a list, go back to the functions lesson and review the car, cdr, first, second, rest, etc. functions.

To create a list, you can use the list function or the quote notation:

* (list 1 2 3)
(1 2 3)

(A B C)
* (list 'a 'b 'c)
(A B C)

* (list "Hola" "Mundo")
("Hola" "Mundo")

* '(1 2 3)
(1 2 3)

* '(A B C)
(A B C)

* '("Hola" "Mundo")
("Hola" "Mundo")

Now we are going to work with higher-order functions designed to operate on sequences (lists, vectors, etc.).

A higher-order function is one that can take other functions as arguments or return functions as a result. They do not modify the original sequence, but return a new sequence with the results. They are fundamental in functional programming and allow you to manipulate collections of data in a more declarative way.

Filtering

Filtering elements means selecting only those that meet a specific condition, defined by a predicate.

remove-if/ remove-if-not

Filters elements of a sequence according to a predicate.

;; Removes the even elements
* (remove-if #'evenp '(1 2 3 4 5 6))
(1 3 5)

find-if / find-if-not

Returns the first element that meets (or does not meet) a condition. It will return the same amount, or fewer, than the original sequence.

* (find-if #'evenp '(1 2 3 4 5 6))
2

* (find-if-not #'evenp '(1 2 3 4 5 6))
1

Mapping

It allows you to transform each element of a sequence by applying a function to each one. In other languages you will always get the same number of elements as the original sequence; in Common Lisp it depends on the function you apply.

mapcar

Applies a function to each element of a sequence and returns a new list with the results.

;; Squares each number
* (mapcar 'list (lambda (x) (* x x)) '(1 2 3 4 5))
(1 4 9 16 25)

mapcan

Applies a function to each element of a sequence and concatenates the results into a single list. It will return a list of equal or greater length.

;; For each number, returns a list with the number and its square
* (mapcan (lambda (x) (list x (* x x))) '(1 2 3))
(1 1 2 4 3 9)

It is an interesting function because it filters and transforms, as if you used a remove-if and a mapcar at the same time in a single step. For example, I could use it to flatten a list.

* (mapcan (lambda (x) (if (listp x) x (list x))) '(1 (2 3) (4 5) 6))
(1 2 3 4 5 6)

To extend a list.

* (mapcan (lambda (x) (list x "-")) '("Hello" "World"))
("Hello" "-" "World" "-")

Or to filter and transform at the same time.

* (mapcan (lambda (word) (when word (list (format nil "~a~a" "#" word)))) '("lisp" "clojure" nil "racket" nil))
("#lisp" "#clojure" "#racket")

maplist

It is a peculiar function. Instead of iterating over each element of the list, you receive the complete list on each iteration but with one fewer element each time. The first element is removed, until the list is empty.

* (maplist #'(lambda (x) x) '('a 'b 'c 'd 'e))
(('A 'B 'C 'D 'E) ('B 'C 'D 'E) ('C 'D 'E) ('D 'E) ('E))

* (maplist #'(lambda (x) (length x)) '('a 'b 'c 'd 'e))
(5 4 3 2 1)

You can use it for sorting matters, comparing lists, or to generate combinations of elements where you need to "look ahead" in the list (for example, to compare each element with the next one).

Reduction

reduce

Combines the elements of a list into a single value.

For example, to add up all the numbers in a list:

(reduce #'+ '(1 2 3 4))

Or being more explicit:

* (reduce #'(lambda (accumulator item)
    (+ accumulator item)) '(1 2 3 4 5) :initial-value 0)
15

• accumulator is the value accumulated so far.
• item is the current element of the list being processed.
• :initial-value is the initial value of the accumulator. In this case, we start with 0 for the sum.

Predicates on sequences

every

• some
• notary/notevery

Sorting

• sort
• stable-sort

Application

• funcall
• apply

Other useful functions

position-if

count-if

member-if

The ones you will probably use day to day are reduce, mapcar, remove-if, and sort.