Many programming languages have only those 2 structures, and even some languages that have more structures still only provide special syntax for those 2; usually, [] and {}. Why is this? Is there anything special about those datatypes that is necessary for the completeness of the language?

  • 9
    Plenty of languages in the ML family have lists rather than arrays (head/tail semantics instead of random access). Also, q/kdb+ has a table container that mimics an in-memory SQL-like container. And C doesn't have built-in hashes at all. So I think your premise takes a narrow views of what's out there. – chrisaycock Mar 23 '13 at 2:46
  • 1
    It's not for completeness so much as convenience: Sure I could write a hash table... but I need one for most major programs so why not make it have nice syntax? And you're not going to make it far if you don't provide some method of storing groups of "stuff" be it in a singly linked list (functional) or an array (C family). Of course, not having them won't make your language "incomplete" but it'll sure make it annoying to work in. – Daniel Gratzer Mar 23 '13 at 2:55

There's nothing that particularly forces a language to have arrays and hashes as fundamental datatypes. Indeed, many don't (especially older languages). However, there are a few fundamental concepts involved which indicate that these sorts of mappings make for good data structures.

Firstly, the ordered collection where you perform lookups by index number. These are a very common structure that is very useful for the case where you've got a bunch of things and you want to be able to walk through them one by one or look the up by some index. The key reason why this is so popular is that the variation where the collection is compact and mapped onto a contiguous region of memory — the array — is very efficient and fast with modern hardware. It is this efficiency which is why arrays are very common (though not universal). The major alternative to the array is the linked list, which are also quite common; linked lists have linear time lookup (whereas arrays have constant-time lookup) but super-cheap insertion and deletion from the middle of the sequence.

The second major category of collection is a mapping from values of one type (that supports an equality test) to another type. This is a way of realizing a whole class of very simple functions in a memory-based data structure, and it is superb for implementing all sorts of other basic datatypes. The name of these things does vary though (e.g., “dictionary”, “associative array”) as does the implementation strategy; the most common three implementation strategies are the record/struct, the mapping tree, and the hash table. Structs are very common (and are in fact a partial hybrid between dictionaries and arrays, where the key is mapped to an offset into an array/memory block). Trees used to be very common, but have become less so as it turns out they tend to have surprisingly poor performance (their memory access pattern turns out to work poorly with the way CPU memory cache predictors work, which is unfortunate). Hash tables, which were relatively uncommon a few decades ago, work pretty well: they've got reasonable memory access patterns and are easy to implement well (which is definitely not true of trees!). Their major down-side is that they don't guarantee the order of iteration (though that is fixable with some extra complexity in the data structure design).

So, the real thing that languages are providing is ℤ⁺→α and α⁼→β maps. These are both generally very useful! One is done with arrays normally, because they are easy to implement and highly efficient for lookup (typically the most common operation), and the other is done with hash tables (or structures) normally, again because they are easy to implement and usually efficient for lookup. The reason why these two particular maps? They turn out to be sufficient for creating a great many other structures with minimal extra code (which in turn means minimal extra mistakes).

| improve this answer | |
  • Great answers but this one was the most spot on, thanks. – MaiaVictor Mar 25 '13 at 0:21

Is there anything special about those datatypes that is necessary for the completeness of the language?


Many languages don't have hashes as a fundamental data structure in the language. And indeed, there are examples of languages that don't have arrays or lists either. (BCPL for instance).

And many languages have other fundamental data structures; e.g. structs, unions, classes and so on.

The real answer is that there is a complicated trade-off between expressiveness, simplicity and implementability that the language designer has to make. Depending on the nature and purpose of the language, different choices are more appropriate. One of the choices is whether a particular "useful" data structure requires linguistic support, or whether it is better provided as a (standard) library.

| improve this answer | |
  • 3
    C# has neither Arrays nor Hash Tables as fundamental data structures in the language itself. All data structures of the list or tree kind are in the .NET Framework. – Robert Harvey Mar 23 '13 at 3:40
  • 2
    @RobertHarvey: C# arrays are not part of the language? Sure? I am pretty sure you are thinking about generic lists, not arrays. – Doc Brown Mar 24 '13 at 18:03
  • @DocBrown: The array class is in the System namespace. C# has direct support for it in the language, but the implementation is in the framework, not in the compiler. – Robert Harvey Mar 25 '13 at 16:50

My comment received a lot of up votes, so I am expanding it as an answer.

This question's premise takes a narrow view of what programming languages actually have. Plenty of languages in the ML family have lists rather than arrays (head/tail semantics instead of random access). And C doesn't have built-in hashes at all. Also, q/kdb+ has a table container that mimics an in-memory SQL-like database.

Having said that, all practical programming languages have loops and/or recursion. This kind of control flow requires that data can be addressed indirectly.

For example, I can't give a unique name to all of my data. That is, I can't call my variables alpha, bravo, charlie, etc.; not only will I run out of names, I'll also be unable to generically reference one variable in relation to another.

So instead I must have indirect addressing, like x1, x2, x3, etc. This is very nature of arrays! Alternatively, I can take a recursive view and investigate first-of-xs and remainder-of-xs. As long as I have indirect addressing, I can use loops or recursion.

As @DonalFellows mentions in the comments, there are models of computation that are Turing complete and yet don't have indirect addressing. Nobody actually writes code that way though.

So from a practical standpoint, I believe that arrays or lists are required for completeness in a programming language since they support the traditional control-flow mechanisms. All other containers like hashes and tables are more for convenience.

| improve this answer | |
  • 2
    There are turing-complete languages which have neither arrays or lists. SKI combinators for one, or counter machines for another. (The former uses very large formal structures, and the latter uses unbounded-precision arithmetic encoding.) – Donal Fellows Mar 24 '13 at 17:23
  • @DonalFellows Good point. I notice that counter machines require "obscure coding" rather than indirect addressing. As for SKI combinators, how would one represent state changes in that? – chrisaycock Mar 24 '13 at 18:54

You've got two basic choices. You have either direct memory access (malloc with C and the resulting pointer arithmetic) or you have to provide some basic data structures to the programmer.

The first, and simplest data structure is a list of some sort (be it implemented with an array or a linked list or some other list structure behind the scenes).

With a list, one could ask the programmer to write his or her own map / associative array / hashtable / dictonary structure. Most people who have taken an undergraduate data structures class have done this. The problem is, most people have done it poorly.

To both make good use of the computer (by not having another poorly implemented hash function) and the programmer's time (to not have to write another poorly implemented hash function again and again - think back to C, basic, and fortran days), many language designers have incorporated this structure into the base language - either as a base structure (perl's %hash) or as part of the standard library (java.util.map).

These really end up as the only two basic structures necessary (and really, only the ability to have a list/array/block of indexable memory is critical). With them, one can build sets, trees, skip lists, and all the rest of the complex data structures that one can dream of.

| improve this answer | |
  • You explained hashes are often part of the language itself because they are important, but I'm asking: why they're so important? – MaiaVictor Mar 23 '13 at 4:52
  • 1
    @Dokkat: They're so important because it's often useful to create an associative mapping of some sort. Arrays map a set of values to consecutive integers; hashes map a set of values to other arbitrary values. – Mason Wheeler Mar 24 '13 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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