60 PicoLisp Functions You Should Know - 6: Lists and Strings
Tags: picolisp, lisp, functional, functions
Published: 2021-10-28 07:55:24

Welcome back! This is the last post of the **60 most common PicoLisp functions** series. Today we will cover **lists** and **strings**.

We will handle the topic **lists** quite extensively as it is one of the most important data types in PicoLisp. After that, we will quickly have a look at some basic **String** functions as well.

-------------

### Fundamentals, revisited

In order to really understand how lists work, we need to go back to the ["Concepts and Data Types" post](https://picolisp-blog.hashnode.dev/concepts-and-data-types) (consider to read it first if you haven't). As we learned there, PicoLisp has only three data types: **Numbers, Symbols and Lists**.

Summary: A **cell is a pair of 64-bit machine words**, which traditionally are called **CAR** and **CDR** in the Lisp terminology. These words can represent either a numeric value (scalar) or the address of another cell (pointer). 

![cell.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1629396578340/G-Dusv0Ep.png)

What are lists? **A list consists of chained cells**, where the CDR of the cell points to the next cell in order to connect the cells to a list. We will see some examples below.


----------------------

### Defining Lists

To define a list, they are surrounded by parentheses. Some examples:

- ``(A)`` is a **single cell list**, with the symbol ``A`` in its CAR, and ``NIL`` in its CDR.

   ```
      +-----+-----+
      |  A  | NIL |       single cell list
      +-----+-----+
```

- ``(A B C)`` is a list consisting of three cells, with the symbols ``A``, ``B`` and ``C`` respectively in their CAR, and ``NIL`` in the last cell's CDR.

   ```
      +-----+-----+
      |  A  |  |  |
      +--+--+-----+
               |
               V
               +-----+-----+
               |  B  |  |  |   
               +--+--+-----+
                        |
                        V
                        +-----+-----+
                        |  C  | NIL |
                        +-----+-----+
```

- ``(A . B)`` is a "dotted pair", also called "cons pair" - a list consisting of a single cell, with the symbol ``A`` in its CAR, and ``B`` in its CDR.

   ```
      +-----+-----+
      |  A  |  B  |       dotted pair
      +-----+-----+
```
- Lists can also be nested, i. e. a list item can also be a list.

-----------------------

### List access

PicoLisp has some handy features to handle the access to list items, which are **based on the cell architecture** of the cell. That makes it so helpful to understand how the list is internally built up.

- ``car`` returns the first element of a list

   ```
: (car (1 2 3 4 5 6))
-> 1
```

- ``cdr``, on the other hand, returns all but the first element - because, as we can see on the drawings above, the CDR **points to the rest of the list**.

   ```
: (cdr (1 2 3 4 5 6))
-> (2 3 4 5 6)
```

There are several shortcuts to combine ``car`` and ``cdr``. For example, if we want to take the **second** item in a list, this equals to the **first item of the ``cdr``**. It can be written like abbreviated to ``cadr`` (first ``cdr``, then ``car``):

```
: (cadr (1 2 3 4 5 6))
-> 2
```
On the other hand, if we have a nested list, we might want to access the "rest" of the first item of a list. This would equal to ``cdar`` (first ``car``, then ``cdr``):

```
: (cdar '((1  2) 3 4 ))
-> (2)
```
Or the first item of the first item:

```
: (caar '((1  2) 3 4 ))
-> (1)
```
You get the principle. The functions can be shortcutted for up to 4x a's or b's. To be precise, these are the valid combinations: ``caaaar``, ``caaadr``, ``caaar``, ``caadar``, ``caaddr``, ``caadr``, ``caar``, ``cadaar``, ``cadadr``, ``cadar``, ``caddar``, ``cadddr``, ``caddr``, ``cadr``, ``car``, ``cdaaar``, ``cdaadr``, ``cdaar``, ``cdadar``, ``cdaddr``, ``cdadr``, ``cdar``, ``cddaar``, ``cddadr``, ``cddar``, ``cdddar``, ``cddddr``, ``cdddr``, ``cddr``.

-----------------------

Similarly, specific items can be accessed by ``nth``, which returns the tail of a given list. ``(nth 'lst 2)`` is equivalent to ``(cdr 'lst)``. 

```
: (nth '(a b c d) 2)
-> (b c d)
: (nth '(a (b c) d) 2 2)
-> (c)
```

-----------------------

### Creating lists 

If a list of numbers in a certain range is required, the easiest way is to produce it using the ``range`` function. It takes two arguments for the range limits plus an additional parameter for the step width.

```
: (range 1 6)
-> (1 2 3 4 5 6)
: (range 6 1)
-> (6 5 4 3 2 1)
: (range -3 3)
-> (-3 -2 -1 0 1 2 3)
: (range 3 -3 2)
-> (3 1 -1 -3)
```

For more complex lists, the list-building process is initialized and executed with ``make`` to start the environment, ``link``to add items to the end and ``yoke`` to add items to the beginning. Pointers to the head and the tail of the list are maintained internally, which makes the operation also efficient for long links. Some examples:

```
: (make (link 1) (link 2 3) (link 4))
-> (1 2 3 4)

: (make (link 2 3) (yoke 1) (link 4))
-> (1 2 3 4)
```
-----------------------

An alternative way to build up lists is using ``cons``, which constructs a new list cell with the first argument in the CAR and the second argument in the CDR. If more than two arguments are given, a corresponding chain of cells is built. (cons 'a 'b 'c 'd) is equivalent to (cons 'a (cons 'b (cons 'c 'd))). 

Note that unlike ``make / link``, the second argument is added to the **CDR**, not to the **end of the list**, which is in an important difference in terms of internal representation.

```
: (cons 1 2)
-> (1 . 2)
: (cons 'a '(b c d))
-> (a b c d)
: (cons '(a b) '(c d))
-> ((a b) c d)
: (cons 'a 'b 'c 'd)
-> (a b c . d)
```
-----------------------

### Length of a list

``length`` returns the "length" of a list in terms of **number of cells**. If the argument of ``length`` is not a cell but a number, the digits in the value are returned (plus 1 for negative values); for symbols it is the number of characters in the name.  

```
# List
: (length (1 (2) 3))
-> 3
: (length (1 . 2))
-> 1

# Symbol
: (length "abc")
-> 3

# Number
: (length 123)
-> 3
```

-----------------------

### List functions

It is a quite common requirement to apply functions on **every item** in a list. Below you can find the most common functions.


``apply`` applies a function to a list. If additional any arguments are given, they are applied as leading elements of the list. 

```
: (apply + (1 2 3))
-> 6
: (apply '((X Y Z) (* X (+ Y Z))) (3 4 5))
-> 27
: (apply println (3 4) 1 2)
1 2 3 4
-> 4
```

``mapcar`` takes a function and a list, and applies the function to **each** element of the list. *Notice the difference to ``apply``, which applys a function to the list as such.*

When additional list arguments are given, their elements are also passed to the function. ``mapcar`` returns the list with all results.

```
: (mapcar sqrt (4 9 16))
-> (2 3 4)
: (mapcar + (1 2 3) (4 5 6))
-> (5 7 9)
: (mapcar + (1 2 3) 5)
-> (6 7 8)
```

``mapcar`` with anonymous function:
```
# add element of first list to square of element of second list

: (mapcar '((X Y) (+ X (* Y Y))) (1 2 3 4) (5 6 7 8))
-> (26 38 52 68)
```

``mapc`` is very similar to ``mapcar``, except that only the **result of the last application** is returned.

```
: (mapc println (1 2 3 4) '(A B C))
1 A
2 B
3 C
4 NIL
-> NIL
```

--------------------------

## String functions

Now let's quickly go through some basic string functions as well.

``pack`` transforms the given arguments to a string in the given order. A ``NIL`` arguments contributes nothing to the result string, a number is converted to a digit string, a symbol supplies the characters of its name, and for a list its elements are taken. 

```
: (pack 'car " is " 1 '(" symbol " name))
-> "car is 1 symbol name"
```

``chop`` returns the name of a symbol as a list of single-character strings.

```
: (chop 'car)
-> ("c" "a" "r")
: (chop "Hello")
-> ("H" "e" "l" "l" "o")
```

``char`` converts unicode to symbol and vice versa:

```
: (char 100)               # Convert unicode to symbol
-> "d"
: (char "d")               # Convert symbol to unicode
-> 100 
```

-------------------

**Congratulations: We have now covered more than 60 of the most common PicoLisp functions!**

In the next post, let's have a quick look at **Fixed Point Arithmetics** in order to understand how to do mathematic calculations in PicoLisp. After that we will finally write our first PicoLisp script, and close our beginner's by learning to use the help function and the debugger.

-------------------

### Sources

- Cover: https://pixabay.com/de/users/erik_stein-2524241  
- https://picolisp.com/wiki/?ArrayAbstinence  
- https://picolisp.com/wiki/?Documentation   
- https://picolisp.com/wiki/?RosettaCodeAnalysis