In one of the last posts, we discussed functions to add or remove items from lists with
pop and so on. Today, we will see how to apply functions to lists with mapping functions.
What is mapping?
In mathematics, the term mapping is often used as a synonym for function. It means that a set
X is assigned to elements of a set
X is also called "domain" and
Now in programming, a "set" is usually a collection of data (in PicoLisp often in form of a list). These sets are transformed via functions. In order to do this in a generic way, many functional programming languages provide higher-order functions that take the function to be mapped as one of its argument.
Input and Output values
Obviously, there are several ways to implement this specifically:
- We can apply a function to the list as a whole (I call this "one-to-X" function in this post),
- or to each single element ("many-to-X" function).
- Do we get a new list as return value ("X-to-many"),
- or a single element ("X-to-one")?
The table below shows an overview over some important higher-order functions based on their input/output classification.
We will go through all four categories in detail now, to understand what each of these functions does and what the subtle differences are.
Let's start with the many-to-many functions, as these are probably the most intuitive ones.
The typical example is
mapcar: It applies a function to each element of a list. If additional arguments are given, their elements are passed to the function too.
: (mapcar + (1 2 3) (4 5 6)) -> (5 7 9) : (mapcar + (1 2 3) 5) -> (6 7 8) : (mapcar '((X Y) (+ X (* Y Y))) (1 2 3 4) (5 6 7 8)) -> (26 38 52 68)
The second example is
filter, which applies a function to each element of a list, and returns all elements where the function returns non-
: (filter num? (1 A 2 (B) 3 CDE)) -> (1 2 3) : (filter < (2 9 3 8 4 7) (5 4 3 9 9 5)) -> (2 8 4)
Its counterpart is
extract, which returns all non-
NIL values of the function. Note the difference to
filter in the example below:
: (setq A NIL B 1 C NIL D 2 E NIL F 3) -> 3 : (filter val '(A B C D E F)) -> (B D F) : (extract val '(A B C D E F)) -> (1 2 3)
mapcan applies the function to each element just like
mapcar, but it returns a concatenated list of results. Observe the difference between
mapcan in the example below:
: (mapcan reverse '((a b c)( d e f)(g h i))) -> (c b a f e d i h g) : (mapcar reverse '((a b c)( d e f)(g h i))) -> ((c b a) (f e d) (i h g))
by takes two functions as argument, where the second one is typically either
group. It returns a sorted or grouped list of elements. Let's take the following data set "A=1, B=2, C=3":
: (setq A 1 B 2 C 3) -> 3 # sort "C A B" by their value: : (by val sort '(C A B)) -> (A B C)
In the second common use case of
by, we call it together with
group builds a list of lists by grouping all elements with the same CAR. Let's say we want to group a list of numbers by even and uneven values:
: (setq L (3 11 6 2 9 5 4 10 12 7 8 1)) -> (3 11 6 2 9 5 4 10 12 7 8 1) # group by even or uneven number: : (by '((N) (bit? 1 N)) group L) -> ((3 11 9 5 7 1) (6 2 4 10 12 8))
Now we come to the "Many-To-One functions" that apply a function to each element of a list, but return a single value instead of a list.
mapc is very similar to
mapcar, but it returns only the last calculation instead of all values. View
mapc in comparison:
: (mapcar '((X Y) (+ X (* Y Y))) (1 2 3 4) (5 6 7 8)) -> (26 38 52 68) : (mapc '((X Y) (+ X (* Y Y))) (1 2 3 4) (5 6 7 8)) -> 68
Another example is
: (apply + (1 2 3)) -> 6 : (apply * (5 6) 3 4) -> 360 : (apply '((X Y Z) (* X (+ Y Z))) (3 4 5)) -> 27
Note: One could argue that
apply doesn't apply a function to each element, but rather passes the list as arguments to a function. In this case it is rather a "one-to-one" mapping. I leave it up to you how you judge it.
extract, we can return a single element from a dataset based on certain criteria with
find. It returns the first element that fulfills the requirement and then stops the execution.
: (find '((A B) (> A B)) (1 2 3 4 5 6) (6 5 4 3 2 1)) -> 4 : (find > (1 2 3 4 5 6) (6 5 4 3 2 1)) # shorter -> 4
pick works similarly to
extract, as it returns the value of the function that fulfills the requirement.
pick in comparison:
: (setq A NIL B 1 C NIL D 2 E NIL F 3) -> 3 : (find val '(A B C D E)) -> B : (pick val '(A B C D E)) -> 1
More similar functions (you can tell the function from the name, I guess):
sum. Below you can find some examples:
: (fully gt0 (1 2 3)) -> T : (fully gt0 (1 -2 3)) -> NIL : (cnt cdr '((1 . T) (2) (3 4) (5))) -> 2 : (setq A 1 B 2 C 3) -> 3 : (maxi val '(A B C)) ->C : (mini val '(A B C)) -> A : (sum val '(A B C)) -> 6
Up to now, all functions have always been applied to each element of the provided list. Now we will discuss two functions that instead apply the function to the list as a whole and return a new list as result.
mapcon applies a function to a list, and to all successive CDRs. Then all results are concatenated.
: (mapcon copy '(1 2 3 4 5)) -> (1 2 3 4 5 2 3 4 5 3 4 5 4 5 5)
First the whole list
(1 2 3 4 5) is copied, after that its CDR
(2 3 4 5) and so on. Observe the difference between
: (mapcan reverse '((a b c)( d e f)(g h i))) -> (c b a f e d i h g) : (mapcon reverse '((a b c)( d e f)(g h i))) -> ((g h i) (d e f) (a b c) (g h i) (d e f) (g h i))
mapcan reverses each single list item, while
mapcon reverses the list as a whole, and after that each CDR successively. Both functions concatenate the result to a new list.
maplist also applies a function to a list as well as to all successive CDRs, but without concatenating the result:
: (maplist cons (1 2 3) '(A B C)) -> (((1 2 3) A B C) ((2 3) B C) ((3) C)) : (maplist reverse '((a b c)(d e f) (g h i))) -> (((g h i) (d e f) (a b c)) ((g h i) (d e f)) ((g h i)))
Another interesting example is
seek, which applies a function to a list and its CDR until non-
NIL is returned:
: (seek '((X) (> (car X) 9)) (1 5 8 12 19 22)) -> (12 19 22)
Finally, we have the plain
map function. Like
mapcon, it applies the function to list and all the successive CDRs, but returns only the result of the last application.
: (map println (1 2 3 4) '(A B C)) (1 2 3 4) (A B C) (2 3 4) (B C) (3 4) (C) (4) NIL -> NIL
Some thoughts about the
map function group
As you might have noticed, there are six functions with very similar names:
mapcan. Instead of the relations above, a better way to classify them might be by argument and return value:
Argument Return List CAR Value ------------+----------+--------- map mapc | last maplist mapcar | list mapcon mapcan | conc
mapcon take the whole list as argument,
mapcan iterate through the list and use each CAR. The return value is either the last element, a list or a concatenated list.
All the functions above can be emulated through these functions, and in fact, all
map- functions can be replaced by
(mapcar inc (1 2 3)) (mapcon '((L) (list (inc (car L)))) (1 2 3))
(maplist '((L) (+ (car L) (cadr L))) (1 2 3)) (mapcon '(((A B)) (list (+ A B))) (1 2 3))
(filter foo Lst) (mapcan '((X) (and (foo X) (list X))) Lst)
While some of these functions have really specific uses cases (like
by), other functions are widely used like
filter and so on. I hope this post helped to sort the different types of mapping functions.
We will see some interesting use cases of
mapcon in the next Euler riddle.