Proposal: Ordered data structures

[mavnn]

Some recent discussion¹ made it clear that while "[Inkle has] always been against replicating array structures in ink because ink is not intended as a coding language ... there ARE use cases for ordered event data"²

The initial proposal that kicked off the discussion is pretty rough and ready because of the constraints of being implemented in Ink, but if an ordered data structure is added to the runtime we can get something such cleaner.

I'd be happy to put together a pull request to add support for some sort of ordered collection for Ink if Inkle are happy to accept it, but the more I've thought about it the more it seems there are two different designs that have very different trade offs, depending on how closely LISTs and the new ordered structure are connected.

In either case, stacks (final name pending) need some basic functionality:

LIST fruits = banana, apple, orange

STACK fruitBasket

// OR maybe we could allow initialization as a VAR like list variables?
// That would allow things like temporary stacks in functions
// VAR fruitBasket = [orange, banana]

fruitBasket += apple
fruitBasket += banana
fruitBasket += banana
fruitBasket += orange

STACK_COUNT(fruitBasket) // 4
STACK_OLDEST(fruitBasket) // apple - use as a queue
STACK_NEWEST(fruitBasket) // orange - use as a stack

That's about all the functionality a basic stack requires, and with this interface the contents could be anything; literal values, list variables, diverts, etc. There's no need for indexed access or any special "empty" markers here; in the same way that calling LIST_MIN on an empty list returns nothing, calling STACK_OLDEST or STACK_NEWEST on an empty stack will return nothing. And you can write iterators or functions to get a value at a certain position if you need to:

// Note that stack is *not* passed by ref so this function doesn't change
// the stack contents
=== function print(stack)
{ STACK_COUNT(stack) == 0:
  ~return
- else:
  {STACK_OLDEST(stack)}
  ~return print(stack)
}

If we limit stacks to only holding unique list values, then some new features become possible. Mainly, it would allow us to make stacks implement things like the intersection operator and min/max value, combining the most useful "flaglike" aspects of lists with tracking the order in which things were added. It could even be implemented by adding order tracking to the existing list dictionary in the run time and adding LIST_OLDEST and LIST_NEWEST to the built in functions.

The downside of this approach is twofold; firstly, you are forced to wrap anything you want to track in a list, even if it is something as trivial as (for example) a series of dice rolls; the second is that the behavior becomes confusing in some scenarios, such as when you try and add the same item twice to a LIST. Is that now the newest item, or does it keep its original "age"?

What do the Inkle team think? Would you be interested in a pull request for either of these proposals, or for something better that I haven't thought of yet?

Footnotes

1. Started by a blog post and carried on in the Inkle Discord #ink channel ↩

2. Discord message from @joningold ↩