# PicoLisp Explored: The enum function

Welcome back to our "Binary Tree" week!

Today we will discuss the ``enum `` function. It can be used to **emulate** arrays (as you might have noticed, [PicoLisp doesn't have an array data type](https://picolisp.com/wiki/?ArrayAbstinence)). But what do arrays have to do with binary trees...?!

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

*The ``enum`` function is only available in **pil21**. If you get a ``enum -- Undefined`` error when you executing the examples below, you probably haven't installed the latest version.*

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

### The ``enum`` function

Let's see what we can learn from the [documentation](https://software-lab.de/doc/index.html) about the ``enum`` function.

> ``(enum 'var 'cnt ['cnt ..]) -> lst``  
> ``(enum 'var) -> lst ``

> Enumerates cells by maintaining a binary tree in ``var``. The keys are implicit from the enumerated ``cnts``, and the resulting tree is balanced (independent from the insertion order). (...)  

> ``enum`` can be used to emulate (possibly sparse) arrays. 

The ``enum`` function expects a ``cnt`` - which means a (small) integer - which specifies the position of a cell in a **balanced tree**. Like for any cell, the corresponding value could be defined with the ``set`` function. 

The cell is returned if it already exists, otherwise it is created as a new node in the tree. A typical use case would be the conversion of a list, as in the following example:

```
: (for (I . S) '(a b c d e f g)
   (set (enum 'E I) S) )
-> o
```
The ``for`` loop takes the index (``I``) and value (``S``) of each list item. ``I`` is stored in the ``enum`` tree, then its value is set to ``S``.

Let's check the result: 
```
: (view E T)
      g
   c
      e
a
      f
   b
      d
```
We see a perfectly balanced tree. To read out some values, we use ``val (enum ...) )``:

```
: (val (enum 'E 1))
-> a

: (val (enum 'E 3))
-> c
```

We can check if a cell already exists using the ``enum?`` function. If it exists, the whole subtree is returned, otherwise ``NIL``.

```
: (enum? E 3)
-> (c (e) g)

: (enum? E 10)
-> NIL
```

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

### ``cache`` and ``enum`` - what's the difference?

1.    ``enum`` **doesn't store any keys**. The key is implicit due to its position in the tree.   
   On the other hand, ``cache`` is creating the index using hash function, which implies that **any key can be stored**. The backdraw is that the hashing step needs to be done everytime an item should be looked up.   

2. ``cache`` accepts a program as argument. If the program has already been evaluated, the value is returned without re-evaluating. ``enum?`` can only check if an index exists or not.

3. ``enum`` is creating balanced trees, ``cache`` is creating *probably*  balanced trees (in real applications, this gap should be rather small)

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

### Array emulation

Probably you can already guess in which regards ``enum`` is similar to arrays: Arrays can usually be indexed directly by a syntax like ``myArr[1]``. ``enum`` allows a very similar handling by ``(val (enum 'E 1))``.

But how does it look like in terms of efficiency? Let's take a list of 1 Mio. items and assume we want to look up the item at position 900.000.

1. **Arrays**. Usually arrays take up consecutive space in the memory. If we know the size per entry, the computer "knows" the required position by calculating "starting point + 900.000*size". --> approx. 1 calculation

2. **Lists**. In PicoLisp, lists are connected via pointers. Therefore we need to jump from pointer to pointer to get to our desired cell --> approx. 900.000 calculations.

3. **enum**/binary tree. The ``enum`` function guarantees that the tree is balanced, so we should be able to find our item within 20 steps --> approx. 20 calculations.

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

### Multidimensional Arrays

We can even create multidimensional arrays, since ``enum`` accepts more than one ``cnt`` variable. Let's create a 4x4 Matrix:

```
: (off A)

: (for I 4
      (for J 4
          (set (enum 'A I J) (pack I "-" J)) ))
```

To get the item in the "second line, second row":

```
: (val (enum 'A 2 2))
-> "2-2"
```

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

### Good old Fibonacci, revisited

And now finally, let's consider our Fibonacci example again and compare it to the ``cache`` version. We can expect a difference, because we can store and access the variables directly under the iteration number ``N``.

However, it requires some further work from us. While ``cache`` accepts a program as parameter and evaluates it only in case the value has not been stored yet, we need to do this manually for ``enum``:

1. check the value of ``enum '(NIL) N`` and set it to ``E``. If it has already been calculated, ``E`` will be non-``NIL``, otherwise it will be ``NIL``.
2. If ``(val E)`` evaluates to non-``NIL`` (i. e. has already been calculated), this value is returned.
3. Otherwise we set ``E`` to the result of the recursive calculation.

```
(de fiboEnum (N)
   (let E (enum '(NIL) N)
      (or
         (val E)
         (set E
            (if (>= 2 N)
               1
               (+ (fiboEnum (dec N)) (fiboEnum (- N 2))) ) ) ) ) )

```

In the previous post, we showed that the cached version can calculate 10.000 Fibonacci numbers in 0.1 s (of course depending on the respective hardware). How many can we do with ``fiboEnum`` in the same time?

```
: (bench (fiboEnum 14500))
0.098 sec
```

We get close to it at Fibonacci number **14500**. This a speed increase of almost 50% compared to the ``cache`` version!


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

If you still haven't seen enough of Fibonacci, stay tuned for the next Rosetta-Code post which will include analytic and iterative approaches, and the second [Euler Project challenge](https://projecteuler.net/problem=2) where we will sum up the **even** Fibonacci numbers.

After that we will start a new topic - Web Application Programming 😃

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

# Sources
https://picolisp.com/wiki/?ArrayAbstinence  
https://software-lab.de/doc/index.html