3 ms·

Well, most of those really conflate two things: static heterogeneous "maps", and dynamic homogeneous maps. The former being a structure whose keys are known at

Well, most of those really conflate two things: static heterogeneous "maps", and dynamic homogeneous maps. The former being a structure whose keys are known at compile time (static) and whose values may be of different types (heterogeneous); the latter being a structure whose keys are not known until run time (dynamic) and whose values must all be of the same type (homogeneous). Most languages conflate these, because they kind of look the same, but they are entirely different use cases, with different use patterns, permit different optimizations, and their generalization (a dynamic heterogenous structure) is pretty useless. The relational model [1], which has been around since 1969, does distinguish these. The static heterogeneous structure is called a "tuple", and the dynamic homogeneous structure is called a "relation". If only language designers would stop conflating the implementation of these structures with how they are used, we could drop the cringeworthy names "associative array" and "hash", stop calling tuples "maps" (which is a specific kind of relation), and stop calling relations "tables" (which are two-dimensional arrays, which are another kind of relation). Erlang at least as of R17 has mostly kept this distinction (Erlang maps mostly support the static heterogeneous use case). However the majority of users are keen to jump on the "maps" bandwagon as a way to get syntax support for dynamic homogeneous use (which makes utterly no sense to me, as most of the syntax is for pattern matching and construction, which makes little sense in the dynamic case!). I am glad R17 does not include many of the proposals for such syntax that I've seen on the mailing list; and instead sticks closely to the original static heterogeneous design proposed by Richard O'Keefe. [1] http://en.wikipedia.org/wiki/Relational_model http://en.wikipedia.org/wiki/Relational_model

Morgawr 13y ago
I agree with what you said but I don't see how a heterogeneous dynamic structure is "pretty useless" though
- colanderman 13y ago
  In a dynamic structure, you're adding and removing key/value pairs at runtime, when you generally don't know what the keys are. When you later access the structure, since you don't generally know what's in it, you can't know the type of any of the values, and hence you can't know what operations are valid on them. The way around this of course is to tag the values with their type. This is usually done implicitly in dynamically typed languages (e.g. Javascript), and always must be done explicitly in statically typed languages (e.g. OCaml). But once you do that, you have a single type for all the things in the structure (a tagged union type) and it's now a homogeneous structure. Either that, or you can split your mapping into multiple mappings, one for each type of thing. That has the benefit of permitting better optimization (you don't need to store per-value tags, among other benefits). (Even in dynamically typed languages, it's better to explicitly tag things anyway. If you have a structure that can legitimately contain two kinds of things, one which happens to be an integer, and one which happens to be a string, then it's pretty likely it might later need to contain a third kind of string, which, if it happens to be an integer or a string, well, you're screwed.)
jeffdavis 13y ago
I don't follow how a relation is a "dynamic homogenous map". Can you elaborate?
- colanderman 13y ago
  In the context of relational databases, a relation is "dynamic" in that the keys (i.e. values of the primary key column(s)) are not know a priori – they are generally derived from external input to the system. A relation is "homogeneous" because its rows are all of the same type (i.e. they have the same columns and types). This is in direct contrast to the rows/tuples, a set of which form a relation: the "keys" of a row (i.e. the column names) are determined a priori and are fixed ("static"). (Yes, even in a schemaless database – your program almost definitely operates on a fixed set of column-keys.) Whereas, the values in a row almost always are of different types ("heterogeneous"). There are of course two other combinations – static homogeneous and dynamic heterogeneous. The static homogeneous case is the degenerate form of the static-heterogeneous and dynamic-homogeneous: the keys are fixed and the values all the same type. You can view such a structure as either dynamic-heterogeneous (ex.: a structure which tracks run-time statistics) or static-homogeneous (ex.: a structure containing configuration settings that just happens to all be of the same type) without losing anything. The dynamic heterogeneous case is not really a useful one: generally, dynamic structures support some form of aggregation or iteration, since the keys by definition are not known beforehand. But if the types of each value may differ, such operations are ill-defined: how can you operate on a value whose type you do not know? I contend that any claimed use of such a structure is best broken down as a combination of the two: either a static-heterogeneous structure containing one dynamic-homogeneous map for each value type, or a single dynamic-heterogeneous map whose values are static-heterogeneous tuples which include a tag indicating the type of the value.
  - jeffdavis 13y ago
    I was already with you on the other points. And, technically, you can look at a relation as a dynamic homogenous map, and that's not wrong per se. But there seem to be some relevant points left out. First of all, a relation is a set of tuples. You can say that a set is just the degenerate case of a dynamic homogenous map in which the values are empty and you use only the keys. That seems like a useless generalization though, and more likely to cause confusion than clarity. Let's say you have a simple relation of person to product: this person has bought this product. It would be awkward to try to group them like: "this person has bought these products" because you could just as well invert it to "this product has been purchased by these people" and there's not a good reason to choose one over the other. Making it arbitrarily asymmetrical just makes it harder to reason about, so that's not a good choice. And neither attribute is unique. So, you are left saying that the key is {person, product} and the value is empty (or "unit", if you prefer). And yes, that is the key of the relation, so that's not wrong. But what have we gained through this exercise? We are calling a binary relation a "map", but confusingly it's not a map of the first attribute to the second -- it's a map of both attributes to nothing! You could say that relations representing something more map-like are common enough. But even in that case, it's common to have multiple candidate keys (which can be true even for normalized relations), and it's hard to say what's mapping to what. Again, more confusion than clarity. I think it's best to just call a relation the set of all tuples which satisfy the relation predicate. That's the model.

Morgawr 13y ago

I agree with what you said but I don't see how a heterogeneous dynamic structure is "pretty useless" though

colanderman 13y ago
In a dynamic structure, you're adding and removing key/value pairs at runtime, when you generally don't know what the keys are. When you later access the structure, since you don't generally know what's in it, you can't know the type of any of the values, and hence you can't know what operations are valid on them. The way around this of course is to tag the values with their type. This is usually done implicitly in dynamically typed languages (e.g. Javascript), and always must be done explicitly in statically typed languages (e.g. OCaml). But once you do that, you have a single type for all the things in the structure (a tagged union type) and it's now a homogeneous structure. Either that, or you can split your mapping into multiple mappings, one for each type of thing. That has the benefit of permitting better optimization (you don't need to store per-value tags, among other benefits). (Even in dynamically typed languages, it's better to explicitly tag things anyway. If you have a structure that can legitimately contain two kinds of things, one which happens to be an integer, and one which happens to be a string, then it's pretty likely it might later need to contain a third kind of string, which, if it happens to be an integer or a string, well, you're screwed.)

jeffdavis 13y ago

I don't follow how a relation is a "dynamic homogenous map". Can you elaborate?

colanderman 13y ago
In the context of relational databases, a relation is "dynamic" in that the keys (i.e. values of the primary key column(s)) are not know a priori – they are generally derived from external input to the system. A relation is "homogeneous" because its rows are all of the same type (i.e. they have the same columns and types). This is in direct contrast to the rows/tuples, a set of which form a relation: the "keys" of a row (i.e. the column names) are determined a priori and are fixed ("static"). (Yes, even in a schemaless database – your program almost definitely operates on a fixed set of column-keys.) Whereas, the values in a row almost always are of different types ("heterogeneous"). There are of course two other combinations – static homogeneous and dynamic heterogeneous. The static homogeneous case is the degenerate form of the static-heterogeneous and dynamic-homogeneous: the keys are fixed and the values all the same type. You can view such a structure as either dynamic-heterogeneous (ex.: a structure which tracks run-time statistics) or static-homogeneous (ex.: a structure containing configuration settings that just happens to all be of the same type) without losing anything. The dynamic heterogeneous case is not really a useful one: generally, dynamic structures support some form of aggregation or iteration, since the keys by definition are not known beforehand. But if the types of each value may differ, such operations are ill-defined: how can you operate on a value whose type you do not know? I contend that any claimed use of such a structure is best broken down as a combination of the two: either a static-heterogeneous structure containing one dynamic-homogeneous map for each value type, or a single dynamic-heterogeneous map whose values are static-heterogeneous tuples which include a tag indicating the type of the value.
- jeffdavis 13y ago
  I was already with you on the other points. And, technically, you can look at a relation as a dynamic homogenous map, and that's not wrong per se. But there seem to be some relevant points left out. First of all, a relation is a set of tuples. You can say that a set is just the degenerate case of a dynamic homogenous map in which the values are empty and you use only the keys. That seems like a useless generalization though, and more likely to cause confusion than clarity. Let's say you have a simple relation of person to product: this person has bought this product. It would be awkward to try to group them like: "this person has bought these products" because you could just as well invert it to "this product has been purchased by these people" and there's not a good reason to choose one over the other. Making it arbitrarily asymmetrical just makes it harder to reason about, so that's not a good choice. And neither attribute is unique. So, you are left saying that the key is {person, product} and the value is empty (or "unit", if you prefer). And yes, that is the key of the relation, so that's not wrong. But what have we gained through this exercise? We are calling a binary relation a "map", but confusingly it's not a map of the first attribute to the second -- it's a map of both attributes to nothing! You could say that relations representing something more map-like are common enough. But even in that case, it's common to have multiple candidate keys (which can be true even for normalized relations), and it's hard to say what's mapping to what. Again, more confusion than clarity. I think it's best to just call a relation the set of all tuples which satisfy the relation predicate. That's the model.