Шаг 11.
Элементарные конструкторы для работы со списками (продолжение)

    На этом шаге мы продолжим изучение элементарных конструкторов.

    В диалектах muLISP85 и muLISP87 определено около 20 функций-конструкторов: ACONS, LIST*, APPEND, COPY-LIST, COPY-TREE, FIRSTN, BUTLAST, REMOVE, REMOVE-IF, SUBSTITUTE, SUBSTITUTE-IF, SUBST, SUBST-IF, MAKE-LIST и др.

Таблица 1. Элементарные конструкторы в muLISP85
Функция
Назначение
(CONS OBJECT1 OBJECT2)
Возвращает точечную пару, у которой CAR-элемент указывает на OBJECT1, а CDR-элемент - на OBJECT2.
(LIST OBJECT1 ... OBJECTN)
Создает и возвращает список, состоящий из элементов с OBJECT1 по OBJECTN.
(LIST* OBJECT1 ... OBJECTN)
Связывает в пару обьекты OBJECT1,...,OBJECTN и возвращает результирующий обьект.
(APPEND LIST1 LIST2 ... LISTN)
Создает и возвращает список, состоящий из элементов списков, начиная со списка LIST1 и по список LISTN.
(COPY-LIST LIST)
Копирует точечные пары верхнего уровня списка LIST и возвращает список, эквивалентный в смысле EQUAL, списку LIST.
(COPY-TREE OBJECT)
Копирует все точечные пары объекта OBJECT и возвращает обьект, эквивалентный OBJECT.
(FIRST N LIST)
Копирует и возвращает первые N элементов списка.
(BUTLAST LIST N)
Копирует и возвращает все, кроме N последних элементов списка LIST.
(REVERSE LIST)
Создает и возвращает список, состоящий из элементов списка LIST, но в обратном порядке.
(SUBSTITUTE NEW OLD LIST TEST)
Возвращает копию высокого уровня списка LIST.
(MAKE-LIST N OBJECT LIST)
Ссоздает и выдает список из N элементов.
REMOVE
Удаляет элементы из списка.
SUBST
Заменяет элементы в списке.

    1. Функция (CONS OBJECT1 OBJECT2) возвращает точечную пару, у которой CAR-элемент указывает на OBJECT1, а CDR-элемент - на OBJECT2. Если значение системной переменной *FREE-LIST* есть точечная пара, то функция CONS модифицирует и возвращает эту точечную пару и изменяет *FREE-LIST* на (CDR *FREE-LIST*).

    Корректная интерпретация функции (СONS OBJECT1 OBJECT2) зависит от того, как рассматривается OBJECT2.

    Если OBJECT2 - список, то функция CONS создает список, первым элементом которого является OBJECT1, а остатком - OBJECT2.

    Если OBJECT2 - атом или бинарное дерево, то функция CONS создает дерево, у которого левая ветвь (CAR-ветвь) есть OBJECT1, а правая ветвь (CDR-ветвь) - OBJECT2. Например:


   $ (CONS 'A '(B C D))
   (A B C D)
   $ (CONS 'A 'B)
   (A . B)
В начало таблицы

    2. Функция (LIST OBJECT1 ... OBJECTN) создает и возвращает список, состоящий из элементов с OBJECT1 по OBJECTN. Если функция вызвана без аргументов, то функция LIST возвращает признак NIL. Функция LIST может работать с любым количеством аргументов. Например:


   $ (LIST 'A 'B 'C 'D)     $ (LIST)
   (A B C D)                NIL
   $ (LIST 'A '(B C) 'D)
   (A (B C) D)
Приведем код функции:

   (DEFUN LIST LST
      ( (NULL LST) NIL )
      ( CONS (CAR LST) (APPLY 'LIST (CDR LST)) )
   )
В начало таблицы

    3. Функция (LIST* OBJECT1 ... OBJECTN) связывает в пару обьекты OBJECT1,...,OBJECTN и возвращает результирующий обьект. Например:


   $ (LIST* 'A 'B 'C 'D)
   (A B C . D)
   $ (LIST* 'A 'B '(C D))
   (A B C D)
Если функция вызывается с единственным аргументом, то LIST* возвращает этот аргумент. Например:

   $ (LIST* 'DOG)
   DOG
Приведем код функции:

   (DEFUN LIST* LST
      ( (NULL LST) NIL )
      ( (NULL (CDR LST)) (CAR LST) )
      ( CONS (CAR LST) (APPLY 'LIST*  (CDR LST)) )
   )
В начало таблицы

    4. Функция (APPEND LIST1 LIST2 ... LISTN) создает и возвращает список, состоящий из элементов списков, начиная со списка LIST1 и по список LISTN. Функция APPEND копирует точечные пары высшего уровня каждого из своих аргументов, кроме последнего.

    Если функция вызывается с единственным аргументом, то APPEND возвращает этот аргумент без его копирования. Следовательно, для копирования списка лучше использовать функцию COPY-LIST, чем функцию APPEND.

    Отметим, что если функции APPEND и NCONC имеют одинаковые аргументы, то они возвращают, как правило, одинаковые списки. Однако, функция APPEND использует точечные пары для копирования всех, кроме последнего, аргументов, тогда как функция NCONC фактически модифицирует все аргументы, кроме последнего. Например:


   $ (SETQ FOO '(D E F))
   (D E F)
   $ (APPEND '(A B C) FOO '(G H I))
   (A B C D E F G H I)
   $ FOO
   (D E F)
Приведем код функции:

   (DEFUN APPEND (LST1 LST2)
      ( (ATOM LST1) LST2 )
      ( CONS (CAR LST1) (APPEND (CDR LST1) LST2) )
   )
В начало таблицы

    5. Функция (COPY-LIST LIST) копирует точечные пары верхнего уровня списка LIST и возвращает список, эквивалентный в смысле EQUAL, списку LIST. Например:


   $ (COPY-LIST '(A B (C . D) E))
   (A B (C . D) E)
   $ (COPY-LIST '(A B C . D))
   (A B C . D)
Приведем код функции:

   (DEFUN COPY-LIST (LST)
      ( (ATOM LST) LST )
      ( CONS (CAR LST) (COPY-LIST (CDR LST)) )
   )
В начало таблицы

    6. Функция (COPY-TREE OBJECT) копирует все точечные пары объекта OBJECT и возвращает обьект, эквивалентный OBJECT. Например:


   $ (COPY-TREE '(A B (C . D) E))
   (A B (C . D) E)
   $ (COPY-TREE '(A B C . D))
   (A B C . D)
Приведем код функции:

   (DEFUN COPY-TREE (OBJ)
      ( (ATOM OBJ) OBJ )
      ( CONS (COPY-TREE (CAR OBJ)) (COPY-TREE (CDR OBJ)) )
   )
В начало таблицы

    7. Если N - положительное целое, то функция (FIRST N LIST) копирует и возвращает первые N элементов списка. Функция FIRSTN возвращает NIL, если N - неположительное целое.

    Если список LIST имеет N или более элементов, то функция FIRSTN копирует и возвращает элементы списка LIST. Например:


   $ (FIRSTN 0 '(SUE JOE ANN BOB))
   NIL
   $ (FIRSTN 2 '(SUE JOE ANN BOB))
   (SUE JOE)
   $ (FIRSTN 4 '(SUE JOE ANN BOB))
   (SUE JOE ANN BOB)
   $ (FIRSTN 5 '(SUE JOE ANN BOB))
   (SUE JOE ANN BOB)
   $ (FIRSTN 2 '(A B . C))
   (A B)
   $ (FIRSTN 3 '(A B . C))
   (A B)
Код функции имеет вид:

   (DEFUN FIRSTN (N LST)
      ( (AND (INTEGERP N) (PLUSP N))
          ( (ATOM LST) NIL )
          ( CONS (CAR LST) (FIRSTN (SUB1 N) (CDR LST))) )
   )
В начало таблицы

    8. Если N - нуль или положительное целое, то функция (BUTLAST LIST N) копирует и возвращает все, кроме N последних элементов списка LIST. Например:


   $ (BUTLAST '(A B C D) 2)
   (A B)

    Если N пропущено или либо равно нулю, либо не является положительным целым, то функция BUTLAST копирует и возвращает все, кроме последнего, элементы списка LIST. Например:


   $ (BUTLAST '(A B C D))
   (A B C)
Приведем код функции:

   (DEFUN BUTLAST (LST N)
      ( (AND (INTEGERP N) (>=N 0))
          (FIRST (-(LENGTH LST) N) LST) )
      (BUTLAST LST 1)
   )
В начало таблицы

    9. Функция (REVERSE LIST) создает и возвращает список, состоящий из элементов списка LIST, но в обратном порядке.

    Функция (REVERSE LIST OBJECT) выдает элементы списка LIST в обратном порядке, присоединенные к OBJECT. Например:


   $ (REVERSE '(A B C D E))        $ (REVERSE '(A B C) 'D)
   (E D C B A)                     (C B A . D)
   $ (REVERSE '(A B C) '(D E F))
   (C B A D E F)

    Результат является таким же, как и при работе функции (APPEND (REVERSE LIST) OBJECT), но вызов REVERSE в качестве второго аргумента более эффективен.

    Приведем код функции:


   (DEFUN REVERSE (LST OBJ)
      ( (ATOM LST) OBJ )
      ( REVERSE (CDR LST) (CONS (CAR LST) OBJ)))
   )
В начало таблицы

    10. Функция (SUBSTITUTE NEW OLD LIST TEST) возвращает копию высокого уровня списка LIST, замещая на элементы NEW те элементы OLD списка LIST, для которых признак проверки по тесту TEST есть не NIL. Если тест-аргумент есть NIL или не задан, SUBSTITUTE использует EQL-тест.

    Функция (SUBSTITUTE-IF NEW TEST LIST) возвращает копию высокого уровня списка LIST, замещая на элементы NEW все элементы списка LIST, для которых признак проверки по тесту TEST есть не NIL. Например:


   $ (SUBSTITUTE 5 2 '(4 2 (3 . 2) 4))
   (4 5 (3 . 2) 4)
   $ (SUBSTITUTE 'CANNIBALS 'NOUN '(NOUN LIKE TO EAT NOUN))
   (CANNIBALS LIKE TO EAT CANNIBALS)
В начало таблицы

    11. Функция (MAKE-LIST N OBJECT LIST) создает и выдает список из N элементов, каждый из которых принимает значение OBJECT, присоединенного к списку LIST. Отсутствие N отождествляется с 0, отутствие OBJECT и LIST - с NIL. Например:


   $ (MAKE-LIST 4)             $ (MAKE-LIST 3 5 '(2 3))
   (NIL NIL NIL NIL)           (5 5 5 2 3)
   $ (MAKE-LIST 3 '(A B C))
   ((A B C) (A B C) (A B C))
Приведем код функции:

   (DEFUN MAKE-LIST (N OBJ LST)
      ( (AND (INTEGERP N) (PLUS N))
            (CONS OBJ (MAKE-LIST (SUB1 N) OBJ LST)) )
           LST )
В начало таблицы

    12. Опишем теперь конструкторы REMOVE и SUBST. Первая функция служит для удаления элементов из списка, а вторая - для замены элементов. Функции REMOVE и SUBST реализуются в условном варианте. Это означает, что добавляется еще один аргумент, являющийся предикатом, истинность которого проверяется перед применением функции на элементах изменяемого списка. Если результат проверки - истина, то функция выполняется, в противном случае - нет.

    Функция (REMOVE ELEMENT LIST TEST) возвращает копию списка LIST со всеми элементами, кроме тех, которые при проверке по тесту TEST имеют признак, не равный NIL и удаляются ((TEST ELEMENT) не равен NIL).

    Если TEST есть NIL или не задан, функция REMOVE использует EQL-тест.

    Функция (REMOVE-IF TEST LIST) возвращает копию списка LIST со всеми элементами, кроме тех, которые имеют при проверке по тесту признак не NIL ((TEST ELEMENT) не возвращает NIL) и удаляются. Например:


   $ (REMOVE '(2 5) '((5 2) (2 5) (2 3)) 'EQUAL)
   ((5 2) (2 3))
   $ (REMOVE-IF 'MINUSP '(-2 0 7 -0.1 3))
   (0 7 3)

    Функция (SUBST NEW OLD OBJECT TEST) возвращает копию обьекта OBJECT, замещая на NEW все OLD подвыражения обьекта OBJECT, для которых признак проверки по тесту TEST есть не NIL. Если TEST есть NIL или не задан, SUBST использует EQL-тест. Например:


   $ (SUBST 5 2 '(4 2 (3 . 2) 4))
   (4 5 (3 . 5) 4)


    Замечание. Теория L списочных структур имеет нелогические символы CAR, CDR, CONS, ATOM и следующие аксиомы [1, с.213]:

   (CAR (CONS X Y))  =  X;
   (CDR (CONS X Y))  =  Y;
   (NOT (ATOM X))    => (CONS (CAR X) (CDR X)) = X;
   (NOT (ATOM (CONS X Y)))

В начало таблицы

   


(1) Математическая логика в программировании: Сб.статей 1980-1988 гг.: Пер.с англ. - М.: Мир, 1991. - 408 с.


    На следующем шаге мы разберем функции ввода-вывода.




Предыдущий шаг Содержание Следующий шаг