# Learning Pilog - 6: More Lists

In the last post, we showed how lists look like and discussed recursion concepts and the ``member`` predicate. Today we will look into some further list functions: appending and reversing, and the concept of accumulators.

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

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

### The ``append`` predicate

Another built-in predicate in Pilog is the "append" predicate, which takes three arguments: The first two are the sublists and the third one is the concatenated list.

```
: (? (append (a b) (c) @X))
 @X=(a b c)
-> NIL
```

Let's see how many possibilities we have to create ``[a,b,c]`` out of two sublists:

```
: (? (append @X @Y (a b c)))
 @X=NIL @Y=(a b c)
 @X=(a) @Y=(b c)
 @X=(a b) @Y=(c)
 @X=(a b c) @Y=NIL
-> NIL
```

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

Let's now take a look at the definition of ``append`` (you can find it in the ``pilog.l`` library file of your PicoLisp installation). Like ``member``, it is defined recursively. The base case is appending a list ``@L`` to an empty list ``NIL``, which means that the result is equal to the final list ``@L``.

```
(be append (NIL @X @X))
```

If we are at the base case, the resulting list is equal to the second argument. Now, if the first argument only had **one** item ``@A``, the new list would be equal to the second argument (now called ``@Y``) prepended by the **head** of of the first list, right? And this can be repeated recursively, like this:

```
(be append ((@A . @X) @Y (@A . @Z)) (append @X @Y @Z))
```

So, to be precise, the (Prolog) predicate name ``append`` was maybe not the best choice. ``concatenated`` would have fit better ([see SWI prolog docs](https://www.swi-prolog.org/pldoc/man?predicate=append/3)). Let's trace what is happening:

```
: (? append (append (a b) (c) @X))
2 (append (a b) (c) (a . @Z))
2 (append (b) (c) (b . @Z))
1 (append NIL (c) (c))
 @X=(a b c) 
-> NIL
```

The first list is reduced down to an empty list, then the second argument is set equal to the third argument. After that, the third argument is "filled up" until we reach the final result.

As you can see, it works, but it takes a lot of steps and can become quite unefficient quickly. 

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

### The ``reverse``predicate

Let's look at another predicate called ``reverse`` (not built-in in pilog). It returns true if the elements of the first argument are in reverse order compared to the second argument:

```
: (? (reverse (a b c) @X))
 @X = (c b a)
```

We could implement it using ``append`` again with a recursive approach: starting from an empty list and then building it up by concatenating the head. 


```
(be reverse (NIL NIL))

(be reverse ((@A . @X) @R)
   (reverse @X @Z)
   (append @Z (@A) @R))
``` 

However, due to the low efficiency of ``append``, this is not to be recommended. Let's find a better approach.

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

### Using an accumulator

A better idea is to use an **accumulator** to solve this task. An accumulator is basically a list that "takes up" the elements that are processed.


```
(be accRev ((@H . @T) @A @R)
   (accRev @T (@H . @A) @R) )

(be accRev (NIL @A @A))
```

The result (which is the third argument) corresponds exactly to the reversed list. So all we need to do is then to define our ``(reverse (@L @R))`` predicate as follows:


```
(be reverse (@L @R)
   (accRev @L NIL @R))
```

Let's trace it in order to check if it does what we think it does:

```
: (? reverse accRev ( reverse (a b c) @X))
1 (reverse (a b c) @R)
1 (accRev (a b c) NIL @R)
1 (accRev (b c) (a) @R)
1 (accRev (c) (b a) @R)
2 (accRev NIL (c b a) (c b a))
 @X=(c b a)
-> NIL
```

The advantage is that the result is directly available after the last step, while our "naive" reverse needed to travel the whole recursion tree back up.


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


### Example: Palindrome Checker

Speaking of reversed lists, one example should not be missing: How to write a simple palindrome checker. Actually we have all we need already except for the actual ``palindrome`` predicate which only takes one argument, a list:

```
(be palindrome (@L)
   (reverse @L @L) )
```

For ``reverse``, we can use one of our previously defined predicates. Let's test it:

```
: (? (palindrome ( r o t a t o r)))
-> T

: (? (palindrome ( a b c d e f g)))
-> NIL
```

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

You can find the sources for all examples [here](https://gitlab.com/picolisp-blog/web-applications/-/tree/main/pilog).

In the last post of the Prolog Crash Course series, we will take a look at "Cuts and Negations".

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

### Sources

https://www.swi-prolog.org/pldoc/man?predicate=append/3