Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow # Working with Lists - push, pop, and more.

Mia Temma
·Jan 14, 2022·

Writing code in PicoLisp means to think a lot in lists and list structures. This is because lists are one of only three data types in PicoLisp, the other two being numbers and symbols. So, every complex construct (like stacks, functions, trees, graphs, and so on), are basically lists.

Thus it is not surprising that PicoLisp has a lot of built-in functions to work with lists. We have already introduced some of them in the Getting Started series, especially in the post 60 PicoLisp Functions You Should Know - 6: Lists and Strings.

Today I will introduce some further functions that all have one thing in common - they allow us to manipulate a list by adding or removing one specific item from a given list.

### What is a list?

Before we dive into it, let's make a very quick review of the PicoLisp list structure. A list is built up of chained cells, where each cell has a CAR and a CDR. The CDR of each cell points to the next cell. While linear lists have `NIL` in the last element of the CDR, a circular list has a pointer back to the first cell.

This is an example of a linear list, `(1 2 3)`:

``````+-----+-----+     +-----+-----+     +-----+-----+
|  1  |  ---+---->|  2  |  ---+---->|  3  |  /  |
+-----+-----+     +-----+-----+     +-----+-----+
``````

This is a nested list, `(1 2 (3 4) 5)`:

``````   +-----+-----+     +-----+-----+     +-----+-----+     +-----+-----+
|  1  |  ---+---->|  2  |  ---+---->|  |  |  ---+---->|  5  |  /  |
+-----+-----+     +-----+-----+     +--+--+-----+     +-----+-----+
|
v
+-----+-----+     +-----+-----+
|  3  |  ---+---->|  4  |  /  |
+-----+-----+     +-----+-----+
``````

And this is a circular list `(1 2 3 .)`:

``````+-----+-----+     +-----+-----+     +-----+-----+
|  1  |  ---+---->|  2  |  ---+---->|  3  |  |  |
+-----+-----+     +-----+-----+     +-----+-----+
^                                         |
|                                         v
+-----------------------------------------+
``````

### The `push` function

A list of items can be used to represent a number of things - for example a stack). Like the name says, a stack is simply a number of items "piled up" (like a stack of plates). When you add or remove an item, you do so from the head of the list.

Stacks are famously used to allocate and access memory, but of course there are many other use cases as well (we will see example of this in the Project Euler series).

Adding items to a stack is also referred to as pushing. The usage is very straightforward:

``````: (push 'L 1)
-> 1
: (push 'L 2)
-> 2
: (push 'L 3)
-> 3
: L
-> (3 2 1)
``````

As we can see, the items have been pushed to the head of the list.

Now what happens if we push to a circular list?

``````: (setq L (3 2 1 .))
-> (3 2 1 .)
: (push 'L 4)
-> 4
: L
-> (4 . (3 2 1 .))
``````

The new item is added again to the head of the list, but not as part of the circular list, but as a linear element.

``````+-----+-----+     +-----+-----+
|  4  |  ---+---->|  |  |  /  |
+-----+-----+     +--+--+-----+
|
v
+-----+-----+     +-----+-----+     +-----+-----+
|  3  |  ---+---->|  2  |  ---+---->|  1  |  /  |
+-----+-----+     +-----+-----+     +-----+-----+
^                                         |
|                                         v
+-----------------------------------------+
``````

The resulting list is `(4 . (1 2 3 .))`. As we can see, the `.` after the 4 connects the circular list with the linear list so that the elements remain on the same level - `(1 2 3 .)` is not a sublist of `L`.

### The `pop` function

Now let's see what we can do with `pop`:

``````: L
-> (3 2 1)
: (pop 'L)
-> 3
: L
-> (2 1)
``````

Note: instead of `pop 'L`, you can also write `++ L`.

`pop` returns the CAR element of a list and sets the pointer of the list to its CDR. Now this has an interesting effect when we handle circular lists:

``````: (setq 'L (3 2 1 .))
-> (3 2 1 .)
: (pop 'L)
-> 3
: L
-> (2 1 3 .)
``````

Because of the nature of circular lists, the popped element is still in the circular list - but now at the tail! Why is that? Let's check CAR and CDR of the circular list `L` to understand what is happening:

``````: (car L)
-> 2
: (cdr L)
-> (1 3 2 .)
``````

`cdr L` still contains all elements, including the CAR.

This can be useful for alternating. Consider the following sequence 1, 2, 4, 5, 7, 8, 10, 11, 13, ... It is formed by adding 1 and 2 alternatingly. Now, with help of a circular list, we can create this list (and more complex ones) very easily by using a circular list `(1 2 .)` and always `pop`ping the next summand. The next post will show an example of this.

### The `fifo` function

Now a stack does not always represent what we need - sometimes we want to get the first item, i. e. the item at the very end of the list.

If this use case, we can use the `fifo` function. `fifo 'var 'any` adds an item `'any` to a list `'var`, and `fifo 'var` returns that item destructively:

``````: (fifo 'L 1)
-> 1
: (fifo 'L 2)
-> 2
: (fifo 'L 3)
-> 3
: (fifo 'L)
-> 1
: (fifo 'L)
-> 2
``````

The underlying data structure is a circular list, as explained in detail in this post.

### The `queue` function

Instead of `fifo`, we can also use a combination of `queue` and `pop` to get the first item back. `queue` adds an item to the tail of a (linear) list.

``````: (queue 'L 1)
-> 1
: (queue 'L 2)
-> 2
: (queue 'L 3)
-> 3
: L
-> (1 2 3)
: (pop 'L)
-> 1
``````

### Removing items: `del` and `rid`

Finally let's also check out how to remove specific items from a list. With `del` ("delete"), we can remove the first occurence of a specific symbol from a linear list.

``````: L
-> (1 1 2 2 3 3 4 4)
: (del 2 'L)
-> (1 1 2 3 3 4 4)
``````

In order to delete all occurences, we call `del` with a non-`NIL` flag:

``````: (del 3 'L T)
-> (1 1 2 4 4)
``````

In circular lists, it pushes the "deleted" item to the end (similar to `pop`). Effectively this means that the item is deleted only from the first "round".

``````: (setq L (1 1 2 2 3 3 .))
-> (1 1 2 2 3 3 .)
: (del 2 'L)
-> (1 1 . (2 3 3 1 1 2 .))
``````

However, this doesn't work with circular lists - the interpreter will hang in an infinitive loop until you kill the process (press `Ctrl-\` in the REPL or type `kill -9 <pid>` in a second terminal).

In order to remove all occurences, we can use `rid` (from "getting rid of"). This works in linear as well as in circular lists:

``````: (setq L ( 1 1 2 2 3 3 .))
-> (1 1 2 2 3 3 .)
: (rid 'L 3)
-> (1 1 2 2 .)

: (setq L2 (1 2 3 1 2 3))
-> (1 2 3 1 2 3)
: (rid 'L2 3)
-> (1 2 1 2)
``````

In the next post, we will see how `push` and `pop` can help us to get all prime divisors from an integer.