PicoLisp Explored: The fifo function
Tags: picolisp, datastructures, list
Published: 2021-12-12 09:51:41

Today we will discuss an interesting function called ``fifo``: **F**irst-**I**n-**F**irst-**O**ut.

As always in "PicoLisp Explored", we will check the documentation and the internal representation of the data to understand what is happening. 

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

### The FIFO principle

The FIFO principle is nothing special or fancy - it just says that "old" items should be used first. Think of a supermarket where the employee always puts the new items **behind** the old ones. 

Obviously the same principle is also possible with data, for example a task list, where the older items should be done first. We can create such a list and take out its items using the ``fifo`` function.

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

### Creating a ``fifo`` list

Let's check the documentation of the ``fifo`` function.

> ``(fifo 'var ['any ..]) -> any``   

>    Implements a first-in-first-out structure using a circular list. When called with ``any`` arguments, they will be concatenated to end of the structure. Otherwise, the first element is removed from the structure and returned. 

Sounds pretty straightforward - let's create a simple to-do List using the ``fifo`` function. We need to define the list variable, for example ``ToDo``, followed by its items.

```
: (fifo 'ToDo "buy groceries")
-> "buy groceries"
: (fifo 'ToDo "make dinner")
-> "make dinner"
: (fifo 'ToDo "clean up the kitchen")
-> "clean up the kitchen"
```
Now let's check the content of  ``ToDo``. 

```
: ToDo
-> ("clean up the kitchen" "buy groceries" "make dinner" .)
```

What do you think? Well, we have all the items, but isn't it a bit strange that the list is starting with "clean up the kitchen", ? Isn't that supposed to be the last point?

Actually, it is not. The point is that **the list is circular** (note the ``.`` at the end!). Internally, or ``ToDo`` list looks something like this:

![fifopointer.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1631815266329/Zih6dyCYW.png)

We can confirm this by checking the ``car`` and ``cdr`` of ``fifo``. 

```
: (car ToDo)
-> "clean up the kitchen"
: (cdr ToDo)
-> ("buy groceries" "make dinner" "clean up the kitchen" .)
``` 

As you can see, ``(cdr ToDo)`` delivers us the output that we expected - **all list items in chronological order**. This is because of the circular nature of the list.

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

### Taking out items

As the docs told us, we just need to write ``(fifo <var>)`` to get out the next item. After that, there will be only two more items in our list.

```
: (fifo 'ToDo)
-> "buy groceries"
: (cdr ToDo)  
-> ("make dinner" "clean up the kitchen" .)
```

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

### What's the point?

Imagine you have a really super large list. We add new items to the beginning, and always take out the item at the end. What does that mean?

If the list is not circular, we would need to traverse **the whole list** down and basically jump from pointer to pointer until we reach the last item. This means the cost of this operation increases **linearly** with the list length. 

On the other hand, with our``fifo`` function, we can do it in constant time: No matter how long the list, we can always get the last item by ``(cadr list)``. 

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

### A little teaser

Well, that's basically all there is to say about the ``fifo`` function.

If this post was too easy for you, here is a little homework: **How can we implement the ``level-inorder`` function of the binary tree traversal?**

```
         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

Expected output: 1 2 3 4 5 6 7 8 9
```


*Hint 1: Use the ``fifo`` function.*  
*Hint 2: No recursion needed.*

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

# Sources

- Photo by <a href="https://unsplash.com/@franki?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Franki Chamaki</a> on <a href="https://unsplash.com/s/photos/supermarket?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>  
- https://software-lab.de/doc/index.html