I'm writing an implementation for a common array structure.

As you would find already familiar, an array is an ordered data structure that you can transform with different (hopefully self-explained) operations like:

  • set object at index
  • insert object(s) starting at index i
  • remove object(s) starting at index i
  • splice
  • push
  • pop
  • shift
  • unshift
  • clear

And then you could intuitively see that you could just code a set of 'fundamental operations' from where you could construct all the other ones. For instance, you could use splice to emulate the behavior of all other operations but you could also use insert and remove to construct all of them.

My question is, then, how would you define those 'fundamental operations'?

Is splice a construct of insert and remove, therefore insert and remove being fundamental?

Or are insert and remove special cases of splice, therefore splice being the fundamental operation for the whole group?

Is there some theory or field of CS that deals with these things?

P.S. Sorry if I'm making a lot of mistakes when presenting the question. I don't know about the correct language for this and have never studied this stuff formally. I hope that I explained myself correctly.

  • $\begingroup$ Whoa a downvote, no feedback... wow $\endgroup$ – almosnow Oct 17 '13 at 20:39
  • 1
    $\begingroup$ Have you read the help center? Would you like to elaborate why you believe this question is on-topic (it is a research-level question about theoretical computer science)? Also, what makes you believe there will be a unique subset of fundamental operations? There might be many such subsets. $\endgroup$ – D.W. Oct 20 '13 at 1:49
  • $\begingroup$ Thanks for your comment. Yeah sure, both subsets could be fundamental, but how do you formally define that an operation is 'fundamental'? Do you know of a site of book that deals with this issues? $\endgroup$ – almosnow Oct 20 '13 at 21:52
  • 2
    $\begingroup$ Start with a book about data structures. $\endgroup$ – Andrej Bauer Oct 21 '13 at 6:43
  • 1
    $\begingroup$ Well, they'll tell you that there is a difference between a list, an array, a stack, and a queue. So then you'll be less puzzled by the Pythonesque do-it-all-in-one arrays. $\endgroup$ – Andrej Bauer Oct 22 '13 at 8:10

There is no standard notion of "fundamentalness". It's not clear that what you are looking for is meaningful or makes any sense. What is "fundamental" is a matter of perspective; I don't see any reason to privilege insert as more fundamental than splice, or vice versa.

So, if you need a concept of "fundamental" for some reason, you'll need to define for yourself what you mean by "fundamental". If you're going to head that path, I would suggest that you start by asking yourself, "Why do you care?"

Personally, I suspect an XY problem. I suspect you're asking the wrong question, and you should go back and ask yourself why you want to know and what you will do with the answer -- and that might help you identify a more sensible question or a more pragmatic path to achieving your real goals.

  • $\begingroup$ Very sensible answer. Fundamentalism as a purpose in itself is dangerous. $\endgroup$ – Andrej Bauer Oct 21 '13 at 6:44
  • 1
    $\begingroup$ In your case, 'fundamentalness' of your data structure is defined w.r.t. those features you are trying to achieve. $\endgroup$ – bellpeace Oct 22 '13 at 2:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.