List Operations
The use of pairs to represent sequences of elements as lists is accompanied by conventional programming techniques for manipulating lists by successively "cdr
ing down" the lists. For example, the function list-ref/2
takes as arguments a list and a number and returns the th item of the list. In Erlang, and thus LFE, is customary to number the elements of the list beginning with 1. The method for computing list-ref/2
is the following: 1
- For ,
list-ref/2
should return thecar
of the list. - Otherwise,
list-ref/2
should return the th item of thecdr
of the list.
(defun list-ref
((items 1)
(car items))
((items n)
(list-ref (cdr items) (- n 1))))
> (set squares (list 1 4 9 16 25))
(1 4 9 16 25)
> (list-ref squares 4)
16
Note, though, that with LFE we can simplify this process: when we use pattern matching on the function arguments, we don't need to explicitly call car
and cdr
-- we get those for free. The previous function can be rewritten to take advantage of this: 2:
(defun list-ref
(((cons head _) 1)
head)
(((cons _ tail) n)
(list-ref tail (- n 1))))
Often we "cdr
down" the whole list. The function len/1
,3 which returns the number of items in a list, illustrates this typical pattern of use:
(defun len
(('())
0)
((items)
(+ 1 (len (cdr items)))))
> (set odds (list 1 3 5 7))
(1 3 5 7)
> (len odds)
4
Again, we can rewrite that using LFE cons
ing in the function arguments:
(defun len
(('())
0)
(((cons _ tail))
(+ 1 (len tail))))
The len/1
function implements a simple recursive plan. The reduction step is:
- The length of any list is 1 plus the length of the
cdr
of the list.
This is applied successively until we reach the base case:
- The passed list matches the pattern of the empty list.
We could also compute length in an iterative style:
(defun len (items)
(len items 0))
(defun len
(('() count)
count)
(((cons _ tail) count)
(len tail (+ 1 count))))
Another conventional programming technique is to "cons
up" an answer list while cdr
ing down a list, as in the function append/2
,4 which takes two lists as arguments and combines their elements to make a new list:
> (append squares odds)
(1 4 9 16 25 1 3 5 7)
> (append odds squares)
(1 3 5 7 1 4 9 16 25)
append/2
is also implemented using a recursive plan. To append lists list1
and list2
, do the following:
- If
list1
is the empty list, then the result is justlist2
. - Otherwise, append the
cdr
oflist1
andlist2
, andcons
thecar
oflist1
onto the result.
We will first show without cons
pattern-matching:
(defun append
(('() list2)
list2)
((list1 list2)
(cons (car list1) (append (cdr list1) list2))))
With cons
pattern-matching, we have this as
(defun append
(('() list2)
list2)
(((cons head tail) list2)
(cons head (append tail list2))))
1. This function is provided for pedagogical purposes and that one should usually rely upon the function from the Erlanglists
module:(lists:nth 4 squares)
. ↩
2. Pattern-matching bycons
ing in function arguments is very common in both Erlang and LFE code. We will be making good use of it in further examples. ↩
3. One should normally not define one's ownlen/1
function, but instead use the built-inerlang:length/1
function which is also available as simplylength/1
. ↩
4. Similarly, the Erlang functionlists:append/2
(orlists:append/1
) generally should be used instead. ↩