# Working with Lists - push, pop, and more. 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](https://picolisp-explored.com/concepts-and-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](https://picolisp-explored.com/series/getting-started), especially in the post [60 PicoLisp Functions You Should Know - 6: Lists and Strings](https://picolisp-explored.com/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**](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)). 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](https://picolisp-explored.com/series/euler-project)). --- 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](https://picolisp-explored.com/picolisp-explored-the-fifo-function). ---- ### 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 `` 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. --- ### Sources - https://software-lab.de/doc/index.html