4 ms·

> accessing an arbitrary list index is O(N) I think you mean linked-list here. Parent is talking about "arrays".

• chriswarbo 4y ago
  > I think you mean linked-list here Yes, I specified this explicitly, e.g. "The Zipper acts like a linked-list with a cursor" and "Where [a, b, c] denotes a singly-linked list". > Parent is talking about "arrays" You're using quotation marks, but I don't see what you're quoting? The parent explicitly says: "a list and an index" In any case, arrays come with most of the same problems I mentioned for lists: - They have invalid states, e.g. ([], 42) - They require bounds-checking, a consistent notion of subtraction on the index type, etc. - They can't be infinite - They require O(N) time, O(N) memory (and O(N) garbage if we're discarding the old value) to replace the focused element - etc. Plus, arrays come with all sorts of extra gotchas, like buffer-overflows, pre-allocation/re-allocation decisions, over/under-provisioning, etc.