# Enumerated Trees in PicoLisp

```Hi all,

PicoLisp has a really cool new function!```
```
It is called 'enum', because it "enumerates" arbitrary Lisp values. That is, it
associates values with numbers, by storing them in a binary tree structure.

The cool points are:

1. The numeric keys themselves are not stored. They are implicit. This saves
half of the space: Only one and a half cell on the average are needed per
entry.

2. It allows to emulate (possibly sparse) arrays with acceptable overhead.

3. The tree is automatically balanced, independent of the insertion order.

And it hopefully silences those always demanding arrays in PicoLisp ;)

'enum' is similar to 'idx' with numeric keys. But with 'idx', the keys take up
one additional cell per entry, and the insertion order is relevant.

(enum 'var 'cnt 'any) -> any  # stores a value
(enum 'var 'cnt) -> any  # looks up a value

Example:

: (for (I . S) '(a b c d e f g h i j k l m n o)
(enum 'E I S) )
-> o

: E
-> (a (b (d (h) l) f (j) n) c (e (i) m) g (k) o)

: (view E T)
o
g
k
c
m
e
i
a
n
f
j
b
l
d
h
-> NIL

: (enum 'E 6)
-> f

\$: (enum 'E 1)
-> a

: (enum 'E 12)
-> l

: (enum 'E 99)
-> NIL

In this example, the keys are ordered as:

1
2                       3
4           6           5           7
8     12    10    14    9     13    11    15

In binary representation:

0001
0010                    0011
0100        0110        0101        0111
1000  1100  1010  1110  1001  1101  1011  1111

The algorithm traverses the key from the lowest bit to the highest, branching
left for zero and right for one.

Probably this algorithm exists already, because it is so simple and obvious. But
I found it by myself and did not bother to search for it (mainly because I don't
know what name to search for).

As another example, we might replace 'cachedFibo' (from misc/fibo.l in older
PicoLisp releases)

(de cachedFibo (N)
(cache '(NIL) N
(if (>= 2 N)
1
(+ (cachedFibo (dec N)) (cachedFibo (- N 2))) ) ) )

with

(de enumFibo (N)
(let E '(NIL)
(or
(enum E N)
(enum E N
(if (>= 2 N)
1
(+ (enumFibo (dec N)) (enumFibo (- N 2))) ) ) ) ) )

'enumFibo' is about twice as fast, and reduces the space by almost two thirds.

☺/ A!ex

--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
```