Implementing core data structures

Question

Data structures are your friend. Using the right data structure in the right place means better performance and less work on the programmer's part.

This poses a problem in Mathematica, of course, since Mathematica has very few of the key structures built in. As of v10 it (finally) has hash-maps, but we're still missing some of the big ones. In particular we don't have a:

• Stack
• Queue
• Heap
• Tree
• Trie

On the other hand, even more than just these I'd like to be able to take whatever efficient data structure I need and apply it to my problem at hand.

To make this possible, though, I can't just wait on WRI, but need to actually implement these myself.

So how can I do this efficiently and cleanly. This means three things:

• The data must be well-encapsulated. I don't want to have to remember that a specific List is a stack when I pass it around in my program. It has to be able to support a reasonable API (object-oriented is best, of course, but to be idiomatic maybe it makes more sense to expose 5000 StackModifyLikeThis, StackModifyLikeThat functions...

• The time-complexity and memory-consumption of all the core operations must be in line with what a real programming language would provide in its core data structures

• The operations can't be too much worse that native operations. Obviously this will be somewhat slower than the kernel-implemented data types, but I don't want the performance to be so much worse I can't use these much more convenient structures.

---

As a concrete example of this, how might one implement a FIFO-queue efficiently?

This means we want to create an automatically resizable Queue data structure that gives us a two things:

• A constant time QueuePush operation
• A constant time QueuePop operation

How would you go about doing so and how does this illustrate best practices for Mathematica data-structure design?

Answer 1

Here is an implementation of a FIFO queue using an Association:

SetAttributes[{QueuePush, QueuePop}, HoldFirst]

QueuePush[q_, foo_] := Module[{}, AssociateTo[q, $ModuleNumber->foo]]

QueuePop[q_] := With[{first=Take[q,1]},
    KeyDropFrom[q, Keys@first];
    first[[1]]
]

Example:

q = <||>;
SeedRandom[1]
QueuePush[q, RandomInteger[10^6]]; //RepeatedTiming
Length[q]

{5.140*10^-6, Null}

7768

Let's check that the elements of the association contain the expected values:

SeedRandom[1]
expected = RandomInteger[10^6, Length[q]];
Values @ q === expected

True

Now, for popping the queue:

QueuePop[q]; //RepeatedTiming
Length[q]

{4.2*10^-6, Null}

412

Check that the queue contains the expected values:

SeedRandom[1]
Values @ q === expected[[-Length[q] ;; ]]

True

So, the push and pop operations are about 5 microseconds.

By the way, note that this approach will be very slow for a LIFO queue.