Позиционирование в списках

Рассмотрим следующую задачу. Пусть требуется в списке заменить значение элемента с заданным номером на другое значение. Разумеется, поскольку в функциональном программировании нет понятия присваивания, «замена» фактически означает, что нужно построить новый список, отличающийся от исходного только в одном элементе. Задачу легко решить различными способами, например, следующая функция вполне удовлетворительно решает эту задачу: change:: Int -> а -> [а] -> [а] change index value list = pre ++ (value: post) where (pre, elem: post) = splitAt index list.

Конечно, функция неприменима в случае, если заданное значение индекса index превышает длину исходного списка или если исходный список вообще был пустым. Но пока будем считать, что эта функция будет вызываться только для «правильных» индексов, находящихся в диапазоне от нуля (включительно) до длины исходного списка (исключительно). Скорость работы этой функции, а также потребности в дополнительной памяти сильно зависит от величины индекса. Если значение индекса близко к длине списка, то придется просмотреть практически весь список, при этом операция (+ +) будет еще и копировать все элементы списка, расположенные левее изменяемого значения (т.е. элементов с индексами, меньшими index). С этим приходится мириться, хотя данный «недостаток» функционального программирования и перекрывается преимуществом от того, что все структуры данных являются неизменными, поэтому, например, после «изменения» элемента списка наряду с новым списком доступен также и старый список.

Ситуация становится заметно хуже, если требуется сделать несколько замен в небольшой области длинного списка. Обобщим поставленную задачу следующим образом. Во-первых, будем считать, что изменение значений списка производит некоторая функция, и изменим интерфейс функции change соответствующим образом. Во-вторых, введем новую функцию modify, которая вместо одной пары из индекса и функции преобразования будет получать целый список таких пар. Пару из индекса и функции преобразования значения будем называть модификатором, и соответствующий тип получит идентификатор Modifier: type Modifier, а = (Int, а -> а).

change:: Modifier, а -> [а] -> [а].

change (index, f) list = pre ++ (f elem: post) where (pre, elemipost) = splitAt index list.

modify:: [Modifier a] -> [a] -> [a].

modify [] list = list.

modify ((n, f) :modifiers) list = modify modifiers $ change (n, f) list.

Здесь функция modify описана как рекурсивная функция, но ее удобно описать и как свертку списка модификаторов, используя для свертки функцию change с переставленными местами аргументами: modify modifiers list = foldl (flip change) list modifiers.

Теперь мы легко можем сделать несколько изменений в середине списка. Например, если мы имеем список [0.. 9] и хотим его пятый элемент удвоить, а шестой — увеличить на 2, то достаточно записать следующее выражение:

" modify [(5, (*2)), (6, (+2))] [0.9].

[0,1,2,3,4,10,8,7,8,9].

К сожалению, функция modify для каждого отдельного изменения списка вынуждена заново проходить и перестраивать значительную часть списка. В традиционных императивных языках программирования в подобных ситуациях используют указатели на отдельные элементы структуры, которые можно передвигать на соседние элементы такой структуры. В итоге удается локализовать позицию внутри структуры и не просматривать большое число элементов каждый раз заново. Для списков языка Haskell такое проделать не удастся, но можно в процессе поиска элемента с заданным номером сохранить путь до этого элемента. В роли такого пути может выступать список пройденных элементов.

Ситуацию с сохранением пути можно показать графически, если изображать элементы списка в виде прямоугольников, каждый из которых содержит значение элемента списка и ссылку на следующий элемент в списке. Например, список из пяти элементов [3,5,8,2,41 можно изобразить так, как показано на рис. 6.1.

Рис. 6.1. Графическое изображение списка.

Если просмотреть первые три элемента списка, то можно при просмотре сохранить их в отдельном списке. Полученную при этом ситуацию можно показать на рис. 6.2.

Рис. 6.2. Сохраненный путь при поиске элемента списка

Пару из списка пройденных и списка непройденных элементов будем называть позицией в списке. Соответствующий тип обозначим идентификатором Position: type Position, а = ([а], [а]).

Позицию можно сдвигать по списку вправо или влево. Для этого опишем две функции: stepLeft и stepRight, которые, получая некоторую позицию, выдают сдвинутую влево или вправо позицию: stepLeft, stepRight:: Position, а -> Position, а stepLeft ((x:path), list) = (path, x: list) stepRight (path, (x:list)) = (x:path, list).

Если дополнить эти функции операциями, которые задают некоторую начальную позицию в списке и, наоборот, извлекают список элементов, продвигая позицию последовательно к началу списка, то получим полный набор функций, позволяющий перемещаться по списку. Функция start будет создавать начальную позицию по заданному списку, а функция extract — продвигать позицию в начало списка и извлекать получившийся список:

start: [а] -> Position а.

start list = ([], list) extract:: Position a -> [a].

extract (path, list) = foldl (flip (:)) list path.

Теперь можно модифицировать функцию change так, чтобы она производила изменение элемента в текущей позиции, а не пыталась просматривать список, начиная с первого элемента. Дадим этому новому варианту функции change идентификатор replace:

replace:: (а -> а) -> Position, а -> Position, а replace f (path, e: list) = (path, f e: list).

Если потребуется сделать несколько модификаций элементов списка, находящихся на близких позициях, то теперь мы можем создать начальную позицию, сдвинуть ее на нужное количество элементов и затем заменять элементы, делая лишь небольшие локальные сдвиги. Например, если у нас имелся исходный список [ 0.. 9 ], и мы хотим элемент с индексом 2 удвоить, а элемент с индексом 7 утроить, то можно выполнить следующую последовательность действий: образовать начальную позицию, два раза сделать сдвиг вправо, удвоить текущий элемент, сдвинуть позицию еще на пять элементов вправо, утроить текущий элемент и, наконец, вернуться в начало и извлечь получившийся готовый список. Чтобы не записывать сдвиги вправо и влево несколько раз подряд, опишем еще одну вспомогательную функцию step, которая будет осуществлять сдвиг позиции на заданное число элементов. Если это число положительно, то будем производить сдвиг вправо, а если отрицательно — влево: step:: Int -> Position, а -> Position, а step n pos = foldl (flip ($)) pos actions.

where action = if n >= 0 then stepRight else stepLeft actions = replicate (abs n) action Вся последовательность действий по изменению элементов списка теперь может быть описана следующим выражением: extract $ replace (*3) $ step 5 $ replace (*2) $ step 2.

$ start [0.9].

Читать такую последовательность действий справа налево не очень удобно, поэтому мы заменим операцию применения функции ($) на такую же по смыслу операцию, но с переставленными аргументами:

($>):: а -> (а -> b) -> b.

х $> f = f х Теперь запись того же выражения можно сделать более наглядной: start [0.9] $> step 2 $> replace (*2) $>

step 5 $> replace (*3) $> extract.

Если задать это выражение интерпретатору GHC, то в результате его вычисления получится измененный список [0,1,4,3,4,5, 6,21,8, 9].

Наконец, мы готовы сделать последний шаг — представить новый вариант функции modify, которая будет получать список модификаторов элементов и список самих элементов, и будет проводить последовательные модификации, сдвигая позицию для изменения элементов списка на необходимое количество элементов влево или вправо. Этот новый вариант функции может оказаться значительно эффективнее нашего первоначального варианта, если список элементов велик, а все модификации в нем производятся с минимальными сдвигами позиции.

Наша новая функция modify будет действовать следующим образом. Сначала список абсолютных значений индексов в списке модификаторов превратим в список величин сдвигов. Будем считать, что положительное значение сдвига — это сдвиг по списку вправо, а отрицательное значение — сдвиг по списку влево на заданное число элементов. Далее образуем начальную позицию и будем производить сдвиги на заданное число элементов с последующей модификацией получившейся позиции. Наконец, извлечем получившийся модифицированный список из текущей позиции с помощью функции extract.

Превращением списка модификаторов с абсолютными значениями индексов в список модификаторов со значениями сдвигов будет заниматься функция convert:

convert:: [Modifier а] -> [Modifier а] convert acts = zip (diffs indices) actions where (indices, actions) = unzip acts diffs [] = [].

diffs list@(x:e) = xizipWith (-) e list Сдвигами позиции с модификациями текущего элемента будет заниматься функция modifyPos:

modifyPos:: [Modifier а] -> Position, а -> Position, а modifyPos actions list = foldl act list actions where act mList (n, action) =.

mList $> step n $> replace action Наконец, новый вариант функции modify получает свой окончательный вид.

modify:: [Modifier а] -> [а] -> [а].

modify actions list = list $> start $>

modifyPos (convert actions) $> extract Проверим, как работает этот новый вариант функции:

" modify [(2, (*2)), (7, (*3))] [0.9].

[0,1,4,3,4,5,6,21,8,9].

Проверьте, что новый вариант функции modify действительно может работать гораздо быстрее первоначального варианта для случая массового изменения близко расположенных элементов длинного списка.