# Learning Pilog - 5: Lists

Today we will talk about an important data structure which is often used in Pilog programming: Lists.

This post is based on [this tutorial](http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch4).


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

### What is a list in Pilog?

Basically, it's the same like in PicoLisp: A sequence of elements. Here are some examples:

```
(John Vincent Jules  Yolanda)
(John (robber Honey_Bunny) @X 2 John)
()
( () (dead z) (2 (b c)) () @Z (2 (b c))) 
```
(the empty list ``()`` is equivalent to ``NIL``).

From the examples we learn:
- list elements can be a mix of data structures, like numbers (``2``), variables (``@X``, complex terms (``(dead @Z``).
- a list can have duplicated values.
- an empty list is still a list.
- lists can be nested: ``(2 (b c))``.

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


A list can be divided by the built-in dot operator ``.``. By default, it splits the list in two parts: the **head**, which is the first element and the **tail**, which is a list of the remaining elements. 

```
: (? (equal (@X . @Y) (John Vincent Jules Yolanda)))
 @X=John @Y=(Vincent Jules Yolanda)
-> NIL

: (? (equal (@X . @Y) (John Vincent)))
 @X=John @Y=(Vincent)
-> NIL
```
As you can see, the tail of a list is always a list, even if there is only a single element inside. So, what is head and tail of an **empty list**?

```
: (? (equal (@X . @Y) ()))
-> NIL
```

**An empty list can't be split up**.


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

However, we don't always have to split up between the head and tail. We can also customize it further:

```
: (? (equal (@X @Y . @W) (John Vincent Jules Yolanda)))
 @X=John @Y=Vincent @W=(Jules Yolanda)
-> NIL
```

Now we have the first and second element stored in variables.

Or, if we only cared for the third element and don't need all the rest, we could also use the *anonymous variable* ``@``:

```
: (? (equal (@ @ @Z . @) (John Vincent Jules Yolanda)))
 @Z=Jules
-> NIL
```


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

### The ``member`` predicate

Pilog has a built-in predicate called ``member`` which takes two arguments: an element and a list. The usage is pretty straightforward:

- Query: Is ``john`` a member of the list?

```
: (? (member John (John Vincent Jules Yolanda)))
-> T
```

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

Its function is defined in the ``pilog.l`` library file:

```
(be member (@X (@X . @)))
(be member (@X (@ . @Y)) (member @X @Y))
```

These two lines use the **recursive** structures of list to find out if an element is a member or not. How does it work? 

1. The first line merely checks if the first list element is equal to ``@X``.
2. The second element splits the list in **head** and **tail**. We know that the head is not ``@X``, otherwise we would have already received ``T`` after the first line. So we can try our luck with the tail: ``member @X @Y)``.


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

### Example: A small Translator

Let's say we have a "dictionary" with the numbers from one to nine in German and English:

```
(be tran (eins one))
(be tran (zwei two))
(be tran (drei three))
(be tran (vier four))
(be tran (fuenf five))
(be tran (sechs six))
(be tran (sieben seven))
(be tran (acht eight))
(be tran (neun nine))
(be tran (zehn ten))
```

Let's write a Pilog script that translates a list of German number words to the corresponding list of English number words and vice versa. The structure should be like this: 

``(? (listtran (eins neun zwei) @X))`` should return ``@X = (one nine two)``, and ``(? (listtran (@X (one nine two)))`` should return ``@X=(eins zwei neun)``.


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

Let's implement our ``listtran`` predicate. We start with the base case: The translation of an empty list - if we have nothing to translate, the translated side will also be empty. The empty list is equivalent to ``NIL``.

```
(be listtran (NIL NIL))
```

Now let's say we have exactly one item (which means it's the **head** of the list). In this case, we can just look it up in our ``tran`` dictionary that we defined above:

```
(be listtran ((@Hg . @Tg) (@He . @Te))
   (tran @Hg @He)
```
*``@Hg/@Tg`` stands for ``Head-German``, ``Tail-German``, ``@He/@Te`` for the English equivalent.*

Now we have the translation of the **first** list element. The only thing we still need to do is travel down our list until the remaining list is empty.

```
(be listtran (NIL NIL))

(be listtran ((@Hg . @Tg) . (@He  . @Te))
   (tran @Hg @He)
   (listtran @Tg @Te) )
```

That's it!

```
: (? (listtran (eins zwei drei) @X))
 @X=(one two three)
-> NIL
```

You can find the finished script in [this folder](https://gitlab.com/picolisp-blog/web-applications/-/tree/main/pilog).


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

In the next post, we will study recursive patterns for **nested** lists.

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

# Sources
http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch4