Мы называем структуру данных (как реализацию абстрактного типа данных англ.ATD) полностью персистентной, если она эффективно реализует все операции предполагаемого, полностью персистентного ADT.
===Интерфейс===
# * [X] статический конструктор, который принимает элемент X и возвращает массив, который содержит X в качестве его единственного элемента.# * '''LENGTH''' [A] возвращает длину массива A.# * ε является пустым массивом, иногда также обозначается []# * '''A''' [i] принимает массив A = [''a''<sub>0</sub>, ..., an-1] и индекс ''i'' = 0..''n''-1, затем возвращает ''a''<sub>i</sub>.# * '''CONCATENATE'''(A,B) конкатентирует два массива: if ''A'' = [''a''<sub>0</sub>,...,''a''<sub>n-1</sub>] and ''B'' = [''b''<sub>0</sub>,...,''b''<sub>m-1</sub>], ''n'',''m'' ≥ 0, результат будет [''a''<sub>0</sub>,...,''a''<sub>n−1</sub>,"b"<sub>0</sub>,...,''b''<sub>m-1</sub>]. Часто записывается как ''A'' · ''B'' вместо '''CONCATENATE'''(''A'',''B'').# * '''HEAD'''(A,''i'') принимает на вход массив ''A'' = [''a''<sub>0</sub>,...,''a''n−1] и производный ''int'', возвращает массив [''a''0,...,''amin(i−1,n−1)'' ]. Если ''i'' < 0 результатом будет [].# * '''TAIL'''(''A'',''i'') принимает на вход массив ''A'' = ["a"<sub>0</sub>,...,an−1] и производный int, возвращает массив [''amax(''i'',0)'' ,...,''a''n−1]. Если ''i'' ≥ ''n'', результатом будет [].# * '''B''' - структура, то ''seq (''B'')'' обозначает строку, которая представлена ''B''.
Основываясь на вышеприведенных операциях, ADT может быть расширен следующими операциями:
# * [''x''0,..., ''x''n−1] является сокращением для '''CONCATENATE'''([x0],'''CONCATENATE'''([x1],'''CONCATENATE'''(...,'''CONCATENATE'''([''x''n−2],[''x''n−1])))) . Обратите внимание, что в программе оценка этого выражения всегда включает ''n-2'' конкатенации.# * '''REVERSE'''[''A''] принимает на вход массив A = [''a''0,...,''a''<sub>n-1</sub>] и возвращает [''a''<sub>n-1</sub>,...,a0]. # * '''REPLACE'''[A,i, x] принимает на вход массив A = [''a''0,...,''a''<sub>n-1</sub>], индекс ''i'' = 0..''n'' − 1, и новый элемент ''x'', выводит [''a''<sub>0</sub>,...,''a''<sub>i-1</sub>, ''x'',''a''<sub>i+1</sub>,...,''a''<sub>n-1</sub>]. # * '''A'''[i] ← ''x ''является сокращенным обозначением A ← REPLACE(A,''i'', ''x''). # * '''INSERT'''[A,i, x] получает массив A = [''a''0,...,''a''<sub>n-1</sub>], индекс ''i'' = 0..n−1, и новый элемент x и возвращает массив [''a''0,...,''a''<sub>i-1</sub>, x,''a''i ,...,''a''n−1] = '''HEAD'''(A,''i'') · [''x''] · '''TAIL'''(A,''i)'', длина которого ''n''-1.# * '''LEFTPART'''(A): возвращает (non-deterministically) массив, представляющий последовательность префикса A.
* ''' RIGHTPART'''(A): возвращает (non-deterministically) массив, представляющий последовательность суффикса A.
Реализация персистентных массивом в виде сбалансированных деревьев
