In one of the last posts, we discussed functions to add or remove items from lists with push, 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 Y. X is also called "domain" and Y "codomain".
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:
Input handling:
- 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).
Function output:
- 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.
Many-to-Many functions
Let's start with the many-to-many functions, as these are probably the most intuitive ones.
mapcar
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)
filter and extract
The second example is filter, which applies a function to each element of a list, and returns all elements where the function returns non-NIL.
: (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
mapcan applies the function to each element just like mapcar, but it returns a concatenated list of results. Observe the difference between mapcar and 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
by takes two functions as argument, where the second one is typically either sort or 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. 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))
Many-to-One functions
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
mapc is very similar to mapcar, but it returns only the last calculation instead of all values. View mapcar and 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
apply
Another example is apply:
: (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.
find and pick
Similarly to filter/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. find and 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
fully, cnt, maxi, mini, sum
More similar functions (you can tell the function from the name, I guess): fully, cnt, maxi, mini, 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
One-to-Many functions
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
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 mapcon and mapcan:
: (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
Similarily, 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)))
seek
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)
One-to-One functions: map
Finally, we have the plain map function. Like maplist and 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: map, mapc, maplist, mapcar, mapcon, 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
While map, maplist and mapcon take the whole list as argument, mapc, mapcar and 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 mapcon only.
Examples: Emulate mapcar by mapcon:
(mapcar inc (1 2 3))
(mapcon '((L) (list (inc (car L)))) (1 2 3))
Emulate maplist by mapcon:
(maplist '((L) (+ (car L) (cadr L))) (1 2 3))
(mapcon '(((A B)) (list (+ A B))) (1 2 3))
Emulate filter by mapcan:
(filter foo Lst)
(mapcan '((X) (and (foo X) (list X))) Lst)
Wrap-up
While some of these functions have really specific uses cases (like by), other functions are widely used like mapcar, 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 by and mapcon in the next Euler riddle.