Follow

Follow

# Working with Lists - Mapping functions

Mia Temma
Â·Jan 25, 2022Â·

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.

Â