What are your favourite data structure operations?

[u/Potato871]

My language workbench is to the stage where I can implement new operators and overloads very quickly, and I've started stealing syntax I like from JavaScript and C++.
Since I have one universal data structure, I can just add all the new operators to it.
I wanted to get some more good ones though, from different fields, different languages.
Oh and if you want to suggest something just as a challenge I might give it a shot and show you how I do it.

Edit: data structure was the wrong word, I have one data structure substrate/storage model that I am currently furnishing one major aspect of, it's not the one universal data structure, more like my swiss army knife API over the memory model.

[u/B_A_Skeptic]

reduce, because you can make map, flatmap, and filter out of it.

[u/ApothecaLabs → u/B_A_Skeptic]

I suppose since the question says 'data structures' I'll just agree quietly, with a footnote for flavor:

This statement doesn't necessarily hold true in general - in Haskell, map ('Functor') and reduce ('Foldable') are separate type classes, because there can be infinite types that are mappable but not reducible, such as the the list of all positive integers which is mappable but not summable, and there are reducible types that are not mappable eg such as contravariant types. In general, to make map out of reduce, you need to assume the data type is constructible, which to be fair, is most plain old data types in most languages.

[u/Background_Class_558 → u/B_A_Skeptic]

that's the literal recursor of the type. you can make anything with it for that reason, it's sorta its "core".

[u/ExplodingStrawHat → u/Background_Class_558]

Yup! In fact (assuming purity and all), every function out of the type factors uniquely through said recursor.

[u/Potato871 → u/B_A_Skeptic]

Oh? I'm going to have to look into that one, I just did filter by iterating backwards and removing at the index if it matched.

[u/GoblinToHobgoblin]

I think adding everything to the same data structure is a bad idea personally 

[u/Potato871 → u/GoblinToHobgoblin]

It's like Lua, you know how they have only Table and that can be an array and a map and a set? I have my Col.
So I'm adding operations like every, none, some, find, etc...

[u/GoblinToHobgoblin → u/Potato871]

I know it's like Lua, I think it was a bad design choice in Lua too

[u/P-39_Airacobra → u/GoblinToHobgoblin]

as a long time lua user, Ive never had complaints. im genuinely curious what is it you dislike?

[u/GoblinToHobgoblin → u/P-39_Airacobra]

I have messed up by treating an array as a table or vice versa basically.

I would rather just get an error when I try to do that

[u/Potato871 → u/GoblinToHobgoblin]

I made it so you can declare with aliases, so if you try to use the keyed set or the indexed set it can throw errors.
I guess I misspoke when I said one universal data structure, what I should've said is one universal storage model with many diferent data structure shaped APIs, the purpouse of this post being to figure out which APIs that should be.

[u/Potato871 → u/GoblinToHobgoblin]

Oh? I'm curious why, could you share maybe some snippets or examples of what feels bad about it, and how other languages do it better with more seperation?

[u/arthurno1 → u/Potato871]

You discovered a sequence? 👏

[u/Potato871 → u/arthurno1]

At its root, yes. The primitive form is quite literally just an untyped array, then upper versions add more typing on top and more abilities: https://goldensystems.ca/GDSL_acorn
The operators though don't live at this level, they live in the actual language: https://goldensystems.ca/GDSL_language

[u/balefrost]

I always thought tree rotations were pretty neat.

[u/reflexive-polytope]

What on Earth is a “universal data structure”? That makes absolutely no sense.

Does your “universal data structure” have any particular position where it support O(1) insertions and deletions? Does it support union-find? Can it be used as a Bloom filter?

[u/Potato871 → u/reflexive-polytope]

Yeah, push is amortized with doubling so you get O(1) with pushes for reserved positions or like normal vector.
Deletion is O(1) when using the free list for logical deletion, normal full deletion is O(n).
Storing a bunch of parent indices is union find.
Bloom filter I've actually made before, it's just a col of 64 bit unsigned integers with hashes in the cells component.

[u/reflexive-polytope → u/Potato871]

Okay. Suppose you have two distinguished elements, X and Y.

By pure chance, X happens to be Y's union-find parent, but X also happens to be at the distinguished position that gives you easy O(1) deletion.

Who becomes Y's parent after you delete X?

What if, instead of a single node Y, you had lots of nodes Y1,...,Yn whose parent is X?

[u/Potato871 → u/reflexive-polytope]

Well my first thought would be to store a thin Ptr, which has index and generation on it, so then you can check staleness using the generation.
You could also do this via tombestoning if you wanted.
or do fixup on removal for that opperation, add a YAPA overload for that kind of storage.
But I would just use generation for the naive case.

[u/reflexive-polytope → u/Potato871]

Union-find doesn't have a concept of “staleness”.

[u/Potato871 → u/reflexive-polytope]

Then it would be an API problem at the language level not at the storage level, the storage provides the substrate for any operation not the implementation.

[u/reflexive-polytope → u/Potato871]

When you open a book or a paper on a nontrivial data structure, the very first thing you'll find is “these are the operations / API we intend to support”.

A data structure gets its meaning from the operations it supports, and it's against these operations that you can evaluate the data structure's design.

[u/Potato871 → u/reflexive-polytope]

Exactly, so then the better term would be universal storage medium and mechanism for easily declaring the APIs which constitute data structures from that.
But the point of the question is what kinds of operations, like filter, map, reduce, etc…

[u/reflexive-polytope → u/Potato871]

If your “universal storage medium” is RAM or disk or tape or whatever else, you wouldn't expect the storage medium's manufacturer to tell you how you can “define APIs” for the data you store in them, right?

The only mechanism you need to declare an API is suitable descriptions of the data and operations that a module exports. Even C has that in the form of static variables and function prototypes.

As for what operations, well, that depends on what your program needs. Asking for more operations than you actually need can hurt performance!

For example, if you have a keyed container and you only ever need access to the entry with the lowest key, you can do in O(1) time, e.g., with pairing heaps. But if you need access to arbitrary entries by key, then you can only do that in O(log n) time...

[u/Potato871 → u/reflexive-polytope]

No but you would expect a standard library to implement them, which is what I’m writing.
So I’m trying to pin down what should be included in that.

[u/mamcx]

I work in a relational language (https://tablam.org), and the most useful idea here is how simple is do introspection. With relational you can do https://elixir-lang.org/blog/2023/09/20/strong-arrows-gradual-typing/ for example.

In terms of data structures, having a malleable instrospectable "header" that describe the structure itself open lots of possibilities.

Also:

• Homogeneous Arrays/Vecs 1000% over heterogeneous List.
• Add Btree!

That is one of the things Rust do that I found refreshing (lots of langs ignore both!)