5 ms·
I really don't like seeing this cited as a "proof" that 0-based indexing of lists is better. It is too shallow and ignores too many important facets of the ques
by curtisf 6y ago
I really don't like seeing this cited as a "proof" that 0-based indexing of lists is better. It is too shallow and ignores too many important facets of the question.
The main contrast Dijkstra is drawing is between closed and half open intervals. Typically, the choice "starting from one" is tied to "closed" intervals, but that's not strictly necessary. Nothing stops you from using half-open intervals on Lua lists any more than you can used closed intervals to index into C arrays.
The main advantage of the typical coupling is avoiding `+`s and `-`s in your "typical" loops over the first n indices:
for i = 1, n do -- closed
for (int i = 0; i < n; i++) { // half open
but what if you want to go in reverse? Getting the _final_ indexes requires arithmetic with half-open intervals, but it doesn't with closed (which also requires changing the operator from exclude-eq to include-eq):
for i = n, 1, -1 do -- closed
for (int i = n - 1; i >= 0; i--) { // half open
Of course, probably the most important property of half-open intervals is the way that they can be broken down into two disjoint intervals: `[A, C) = [A, B) U [B, C)`. But if your indexes are integers this is straightforward with closed intervals too: `[A, C] = [A, B - 1] U [B, C]` or `[A, C] = [A, B] U [B + 1, C]`.
But again, if you're using this property, you probably don't actually care about the "absolute" indexes at all; indexing with `[1, #list + 1)` isn't a problem _at all_ in Lua.
Plus, between the operations of "get final index" and "split interval into non-overlapping pieces", "get final index" is far more common (it's crucial to stacks, queues, etc, in addition to various uses like iterating backwards). Choosing "closed" intervals is then the cleaner option to avoid an ugly "+" or "-"!
Dijkstra mentions that requiring -1 to refer to an initial interval as "ugly" since -1 is not a valid index, but he has no qualms with using the length of the list, n, and allowing it to not be an index!
This is all said without even going into the awkwardness of having [k] being the {k+1}th element (e.g., [4] is how we write "fifth" in C -- I distinctly remember at least one conversation at work where the wrong thing was communicated because someone said "fourth" to mean [4])
Now, don't take this as a serious argument that 0-indexed-lists are inferior to 1-indexed lists. It's just a demonstration that it's easy to argue either side. That's because it's really just an unimportant convention. Pick one and stick with it and everything will work fine, modulo confusion about what "fourth" means.
- anonymoushn 6y ago> indexing with `[1, #list + 1)` isn't a problem _at all_ in Lua. That's not what string.sub accepts though. > Plus, between the operations of "get final index" and "split interval into non-overlapping pieces", "get final index" is far more common (it's crucial to stacks, queues, etc, in addition to various uses like iterating backwards). Choosing "closed" intervals is then the cleaner option to avoid an ugly "+" or "-"! It (rather unnecessarily) takes log time, so you probably shouldn't do it if you can avoid it.
- ufo 6y ago> It (rather unnecessarily) takes log time, so you probably shouldn't do it if you can avoid it. This is one of the things that improved in Lua 5.4. Now it caches the table length so that the # operator is O(1) in many common situations.
- ebg13 6y agoWill it still give the wrong answer if your table isn't sequentially indexed? That is, does #({[1]="a", [3]="b"}) return 1 or 2? edit: I see that it still returns 1. That's a shame. This trips up so many newcomers who've been told that "#" means "length". IMO they need to either start calling it something other than the "length operator" or make it _actually_ return the length. Sadly at this point it would just be yet another breaking change.
- anonymoushn 6y ago1 or 3 but not 2 edit: yes, in fantasy-lua there will be an array type that can represent [1,nil,3] (sequence of 3 values)
- ufo 6y agoThe ideal fix would to allow tables to store nil values, instead of always treating nil as a "hole". Instead of assigning nil to remove a value, you would call a separate "delete" function or operator. This way there would still be only one table type instead of separate types for tables and arrays. Some early alpha versions of Lua 5.4 played around with this idea but it turns out that it would break too many things. I'd expect that if Lua ever makes a major jump to Lua 6.0 then nils in tables will likely be one of the main changes.