Is there a language, or a language-agnostic design pattern, that makes
it easy to define a generic public interface that works with any data
Haskell seems like an awesome suggestion, but maybe a bit hardcore. At least I'm a little bit afraid of Haskell (it's a language whose code always inspires me, but I never actually got the nerve to try anything substantial).
I'd personally recommend C++ for this since the code generation of C++ templates allows you to eliminate any abstraction cost (dynamic dispatch, i.e.) out of the picture and just focus on the efficiency of the data structures themselves while likewise mutating the data structure easily (might be a little bit hard in functional languages without kind of changing the whole way you approach data structures). It's one of the few languages I personally know where you can write a contiguous data structure which performs just as well for random access as a plain old array, e.g., since the optimizer just squashes all that code structure you built down to smithereens.
It also comes with a pretty complete set of standard containers (though missing a few semi-common ones like tries) with a "near" data structure-agnostic interface. A little bit of wrapping should give you a universal interface that lets you do whatever you want, at least for value types (set vs. map). Key/value associative containers are a bit harder to generalize and might need to be in their own category, simply because they tend to call for a very different interface design.
The key to doing this to me is to define your universal interface. A C++ standard sequence like
vector has these functions:
push_back -- appends an element to the back of the container.
insert -- inserts an element to any place in the container.
erase -- erases an element from any place in the container.
range insert -- inserts multiple elements to any place in the container.
range erase -- removes a range of elements from any place in the container.
empty -- returns size() == 0.
size -- returns the number of elements.
clear -- removes all elements from the container.
begin -- returns an iterator pointing to the beginning of the container.
end -- returns an iterator pointing to the end of the container.
There's also a fill constructor, range constructor, etc. (and you can even pass in your own memory allocator which usually isn't that helpful for something like
vector but can make a huge difference for linked structures).
std::list, conforms to the same interface requirements except with some minor differences in this context like a
push_front member function which is omitted from
std::vector deliberately to discourage its use there.
You can easily wrap all these containers and, with little effort, apply a universal interface... maybe with functions like so:
push_front -- insert to front.
push_back -- insert to back.
erase -- erase anywhere.
insert -- insert anywhere with no regard about where the element goes.
insert_sorted -- do an insertion sort.
Etc. It won't take much time to wrap all applicable existing C++ containers to conform to this universal interface of your design as well as implement new ones that conform to it, and then you can benchmark your heart out and generate graphs and whatever you want.
A major thing to note about C++ is the iterator design driving algorithms. You can implement a custom data structure there, and by merely exposing iterators, hundreds of existing algorithms (not just standard but also third party) suddenly become applicable to your data structure with no extra effort. There's no need to implement like a
sort method for your custom data structure, for example, as
std::sort will work on it once you expose iterators to it.