# Working with Lists - Mapping functions In one of the [last posts](https://picolisp-explored.com/working-with-lists-push-pop-and-more), 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". ![mapping-example.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1643025739586/MZJ5ooVoC.png) 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. ![map-list.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1643106718723/Ag7r0Jx66.png) 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. ```undefined : (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``. ```undefined : (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: ```undefined : (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: ```undefined : (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": ```undefined : (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: ```undefined : (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: ```undefined : (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``: ```undefined : (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. ```undefined : (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: ```undefined : (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: ```undefined : (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. ```undefined : (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``: ```undefined : (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: ```undefined : (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: ```undefined : (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*. ```undefined : (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: ```undefined 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``: ```undefined (mapcar inc (1 2 3)) (mapcon '((L) (list (inc (car L)))) (1 2 3)) ``` Emulate ``maplist`` by ``mapcon``: ```undefined (maplist '((L) (+ (car L) (cadr L))) (1 2 3)) (mapcon '(((A B)) (list (+ A B))) (1 2 3)) ``` Emulate ``filter`` by ``mapcan``: ```undefined (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. --- # Sources - https://software-lab.de/doc/index.html