What is the name of immutable data structure, which has O(1) access to the head element and logarithmic increasing access cost for the following elements?
It can be implemented by converting tail into an array, when prefix size becomes larger than the tail size. I.e. (cons prefix array)
Name:
Anonymous2014-05-26 3:46
>>1 balanced binary tree with path copying for insertion and deletion.
good operations would be random access, creating a clone of the array where an item at a specific index is changed, and creating clones where new elements are inserted at the back.
Name:
>>112014-05-26 7:30
Though you could implement it as a balanced binary tree sorted by the index of the element and then just save another reference to the front element at the left end of the tree to improve its access time.
(cons x xs) and (cdr xs) would still be O(log2(n))
Name:
Anonymous2014-05-26 7:34
>>14 I don't think you can get around (cons x xs) being O(log2(n)) but since its immutable you could save a reference to the old tree to speed up (cdr xs). But it would use memory up the ass.
Name:
Anonymous2014-05-26 7:59
also cdr is typically used for traversal, which can be replaced with a functional iterator.