Удаление элемента списка в Scheme

Доброго времени суток, случайные и неслучайные читатели этого блога.

Сейчас довольно много пишу на Scheme, в связи с работой над проектом LazyCat. В проекте используется Scheme для GUI и для высокоуровневой логики. Подробнее о проекте на русском языке можно узнать здесь. В данной же заметке я хочу рассказать о проблеме удаления элемента из списка.

Если вы сталкивались с Lisp'ом в жизни (например, настраивая GNU Emacs), то должны знать, что список является едва ли не основным представлением как данных, так и собственно программы, их обрабатывающей. Даже название языка -- Lisp -- произошло от "List Processing", т.е. "обработка списков". Scheme, как диалект Lisp, не представляет исключение в этом плане. И работая с Scheme, вы постоянно работаете со списками.

Так вот, в LazyCat список управляемых хостов хранится, как Lisp-список. Пример:

 
'((#f host1 host2) ("ssh-hosts" host2 host4))

В данном примере есть две группы:

• группа #f, в которую помещяются "бездомные" хосты, которые не являются членами какой-либо группы (уж так повелось);
• и группа "ssh-hosts".

В каждой группе -- по два хоста. Первый элемент группы -- который можно получить через операцию car -- имя группы.

(car '("ssh-hosts" host2 host4)) => "ssh-hosts"

Оставшаяся часть списка -- получаемая через cdr -- это члены группы.

(cdr '("ssh-hosts" host2 host4)) => '(host2 host4)

При работе с этим списком требуется добавлять и удалять его элементы. С добавлением нового элемента в список проблем нет, а вот удаление элемента из списка представляет собой не вполне тривиальную задачу. По крайней мере, я не нашёл простого спосба сделать это. Что и привело к созданию собственного "велосипеда" для выполнения этой операции.

Итак, нужно удалить хост из группы. Если подумать, то можно найти предельно простое по идее, но не такое простое в реализации решение (как раз тот самый "велосипед"). Идея заключается в том, что хост можно "вырезать" из списка путём следующих действий:

1. Нужно взять часть списка, чей car -- элемент, который необходимо удалить. Эту часть можно найти путём простого перебора элементов.
2. После этого нужно получить cdr списка.
3. Склеить с помощью операции append две части списка -- часть списка до текущего car и часть списка, получаемая по cdr относительно текущей части с удаляемым элементом в car.

На практике же это превратилось в довольно громоздкую конструкцию:

 

(let ((new-cdr '())) 
  (let f ((group-members (cdr group)))

    ;; Are there elements in the given list?
    (if (not (null? group-members))

        (if (eq? (car group-members) host)

             ;; We found the host which should be removed from the list.
             ;; Cut out the car of the list and concatenate two lists
             (set-cdr! group (append new-cdr (cdr group-members)))

             ;; Host is not found. Check the next group member.
             (begin 
               ;; Add the current car to the new cdr of the group
               (new-cdr (append new-cdr (car group-members))) 
               ;; Try the next group member 
               (f (cdr group-members)))))))

Одна из неприятных вещей заключается в том, что по мере просматривания списка хостов мы должны формировать начало списка, для последующей склейки -- ведь получить cdr не составляет труда, а вот получить предыдущую часть списка... Я пока не знаю, как это сделать. Поэтому здесь я просто добавляю каждый проверенный хост к новому списку, который в будущем станет частью cdr группы.

В целом, этот код выглядит не слишком хорошо. Но, насколько помню, он свою задачу выполнял. Тем не менее, я был уверен, что есть более простые и элегантные способы работы со списками. И в конце-концов ответ был найден.

Благодаря использованию модуля (ice-9 common-list) вышеприведённый кусок кода был заменён на следующую строчку:

 

(set-cdr! group (remove-if (lambda (element) (eq? element host)) 
                           (cdr group)))

Функция remove-if применяет предикат (фукнцию, возвращающую #t (true) или #f (false)) переданный, как первый параметр, ко всем элементам списка (второй параметр функции). Если предикат возвращает #t -- то элемент удаляется из списка. По завершению remove-if возвращает список, из которого удалены требуемые элементы.

В представленном выше примере remove-if сравнивает два объекта -- элемент списка и хост. Если элемент списка и хост -- один и тот же объект, то он удаляется из списка. После этого происходит замена cdr группы новым списком хостов.

Пример использования remove-if взят из файла host-list.scm, являющегося частью LazyCat.

- Артём