Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why do arrays start at 0?

buttondown.email

Post reply on HN
Print view View original

471–480 of 702 posts

Re: Why do arrays start at 0?

#471

Post by JadeNB »

salty_biscuits wrote: post #441
JadeNB wrote: post #382

Earlier quoted context omitted.

> Where 0 is the cardinality of the empty set, i.e. some empty collection. Not a convincing argument. Why not? "Every cardinality, except of the empty set , is a natural number" isn't very convincing to me, if we're making cardinal-based arguments.

I'm not arguing that the natural numbers should start from one, rather that the usual path for developing the natural numbers starting with set theory is that zero is the size of a set with nothing in it. In maths they always talk about the first element in a vector, not the zeroth. It is a bad argument to point to mathematics for using zero based indices. It is not at all common to use zero based indexing there.

I'm a mathematician, and 0-based indexing makes way more sense to me.

Dijkstra's argument (https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF) is that we count the number of predecessors. This fits well with the mathematical usage, at least among mathematicians who care to dig into the order-theoretic foundations: the von Neumann construction of ordinals (and of cardinals as least ordinals of a fixed, well, cardinality), each finite ordinal is equal to its cardinality: 0 = \emptyset is a set with 0 elements, 1 = {0} is a set with 1 element, 2 = {0, 1} is a set with 2 elements, etc.

Re: Why do arrays start at 0?

#472

Post by [deleted] »

atwood22 wrote: post #291
lupire wrote: post #252

Earlier quoted context omitted.

Nope. Is the empty set countable? (Yes.) Dictionary: nat·u·ral num·bers the positive integers (whole numbers) 1, 2, 3, etc., and sometimes zero as well Countable: https://en.wikipedia.org/wiki/Countable_set Set theory: https://en.wikipedia.org/wiki/Ordinal_number

From your own link on countable sets: > Equivalently, a set S is countable if there exists an injective function f : S → N from S to N; it simply means that every element in S corresponds to a different element in N. Defining N is usually done via a successor set, on which case 0 makes no sense to include.

[deleted]

Re: Why do arrays start at 0?

#473

Post by [deleted] »

kazinator wrote: post #386
atwood22 wrote: post #145

Earlier quoted context omitted.

Do you know the definition of countable? A set S is countable if there is a one-to-one mapping from S to N where N is the natural numbers. Do you know that 0 is not a member of the natural numbers? We literally start counting at 1 by definition of countable.

An empty set is countable; it has an empty mapping to the natural numbers. Its cardinality is zero.

[deleted]

Re: Why do arrays start at 0?

#474

Post by JadeNB »

thaumasiotes wrote: post #442
JadeNB wrote: post #382

Earlier quoted context omitted.

> Where 0 is the cardinality of the empty set, i.e. some empty collection. Not a convincing argument. Why not? "Every cardinality, except of the empty set , is a natural number" isn't very convincing to me, if we're making cardinal-based arguments.

It's not a convincing argument because you index into an array if you want to retrieve an element contained in the array. If 0 is the cardinality of an empty collection, it's not a valid index, because you can only index into non-empty collections.

Dijkstra's argument (https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF) is that the index counts the number of predecessors.

I think an age-based way to phrase it: in your 1st year, your age is 0; in your 2nd year, your age is 1; and so on. We can assign people numbers indicating what year of their lives they're in, or how many years they have lived, and both are fine, but we've settled on the latter.

Re: Why do arrays start at 0?

#475

Post by lupire »

kazinator wrote: post #386
atwood22 wrote: post #145

Earlier quoted context omitted.

Do you know the definition of countable? A set S is countable if there is a one-to-one mapping from S to N where N is the natural numbers. Do you know that 0 is not a member of the natural numbers? We literally start counting at 1 by definition of countable.

An empty set is countable; it has an empty mapping to the natural numbers. Its cardinality is zero.

And its ordinalitiy is also 0.

Standard construction of ordinals is that each ordinal is the set of all its predecessors. (0 has no predecessors , hence 0 is the empty set.) (And so finite ordinals have the same ordinaliity as cardinality).

Re: Why do arrays start at 0?

#476

Post by colejohnson66 »

ajg36 wrote: post #456
JadeNB wrote: post #292

Earlier quoted context omitted.

> Nats start at 0, end of discussion - it's only logical to index by the naturals. Now you'll just bring out the people who start the naturals at 1.

Starting the naturals at 1 is quite onerous.

That’s why I compromise and start at -1

Re: Why do arrays start at 0?

#477

Post by Someone »

alexcosan wrote: post #463
twobitshifter wrote: post #459

Earlier quoted context omitted.

Should work 99.99999% of the time until someone tries to put an array at 0x000001 :)

I think, in theory, it would work regardless of the starting address. As long as you don't try to access the invalid address (which you wouldn't assuming that it's starting in the index 1, you would always be accessing the first valid address)

In theory, it’s not guaranteed to work at all. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf#p... (emphasis added):

“In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, _provided_they_exist”

[…]

If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; _otherwise,_the_behavior_is_undefined.

In this case, the minus-one-th element doesn’t exist, so the expression

  int * b = a - 1;
triggers undefined behavior.

I think some compilers use this in practice to produce faster code (that, often, will not do what the programmer expects it to do). Start reading at https://stackoverflow.com/questions/56360316/c-standard-rega... if you’re sure they don’t. I expect that will change your opinion.

Re: Why do arrays start at 0?

#478

Post by karamanolev »

anigbrowl wrote: post #311
divbzero wrote: post #283

Earlier quoted context omitted.

The same applies to counting in other bases too. For instance, in 1-indexed counting grids for kids, the last column always feels out of place. 0-indexed decimal grid: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 8…

Are you sure it doesn't just look that way because you are used to monospaced fonts? Ask a kid to show you their zeroth finger.

Counting fingers (or other items) isn't a positional numeral system, so it's really apples to oranges. Also, "first" has a meaning of "nothing precedes it", which is separate from the indexing system", it shouldn't mean "at index 1", unless otherwise specified.

Re: Why do arrays start at 0?

#479

Post by Quekid5 »

wizofaus wrote: post #336
mananaysiempre wrote: post #179

Earlier quoted context omitted.

A rare case where 1-based indexing is more convenient is complete binary trees laid out breadth-first (as in a standard binary heap): parent is i div 2 and children are 2i and 2i+1 when starting at one and who knows what when starting at zero. But that’s the only one I know.

Except 1-based indexing is what we use in normal language. We don't use "zeroeth" or "player (number) zero" etc. And the word "first" is shortened to 1st etc. Personally I think we'd be better off if programming languages stuck to the same convention - off-by-1 errors aren't the hardest problems to deal with but they're still annoying.

> "player (number) zero"

That would be because any game worth playing has at least one player... and so it's natural to continue from there. (In terms of language.)

Re: Why do arrays start at 0?

#480

Post by kentonv »

The 1900's were the twentieth century. Except the year 1900 specifically was still the nineteenth century; the twentieth century started in 1901 and ended at the end of 2000, much to the chagrin of all the chumps who celebrated the millennium a year early.

You know what would make all this confusion go away? Zero-based indexing.

Post reply on HN