На этом шаге мы рассмотрим функцию MAPCAR.

Рассмотрим вначале две функции.

Пример 1.

   (DEFUN SUMADD (LAMBDA (LST)
   % Функция, преобразующая список целых чисел в список, %
   % каждый  из  элементов  которого  на  единицу больше %
   % соответствующего элемента                           %
       ( (NULL LST) NIL )
       ( CONS (PLUS 1 (CAR LST)) (SUMADD (CDR LST)) )
   ))
   % ------------------------ %
   (DEFUN TANUSHA (LAMBDA (LST)
   % Функция, преобразующая список целых чисел  в список, %
   % каждый из  элементов которого представляет собой ос- %
   % таток от деления соответствующего элемента на 2      %
       ( (NULL LST) NIL )
       ( CONS (REMAINDER (CAR LST) 2) (TANUSHA (CDR LST)) )
   ))

Очевидно, что есть нечто общее в структуре данных функций.

Возникает естественный вопрос: возможно ли обобщение?

Ниже мы построим функцию MAPCAR для диалекта muLISP81, с помощью которой вторая интересующая нас проблема решается так:


   $ (MAPCAR REMAINDER (2 4 6))
   (0 0 0)

Обращение к функции MAPCAR выглядит следующим образом:


   (MAPCAR FN (X1 X2 ... XN))

Значение функции MAPCAR вычисляется путем применения функции FN к последовательным элементам Xi списка, являющегося вторым аргументом MAPCAR.

В качестве значения функционала возвращается список, построенный из результатов вызовов функционального аргумента MAPCAR.

Код функции для muLISP81 достаточно прост:

   (DEFUN MAPCAR (LAMBDA (FUN LST)
      (COND ( (NULL LST) NIL )
            ( CONS (FUN (CAR LST))
                   (MAPCAR FUN (CDR LST)) )
      )
   ))

Отметим здесь, что вычисление функционала MAPCAR может быть осуществлено параллельно и не зависит от порядка обработки элементов списка.

Пример 2.


   $ (MAPCAR ATOM (A B C))
   (T T T)
   $ (MAPCAR (LAMBDA (Y) (LIST (PRINT Y))) (A B C))
   A
   B
   C
   ((A) (B) (C))
   $ (PUTD PARA1 (LAMBDA (X) (LIST X 1)))
   PARA1
   $ (MAPCAR PARA1 X)
   ((A 1) (B 1) (C 1))
   $ (MAPCAR NUMBERP (1 2 МИМО 3))
   (T T NIL T)

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

   (DEFUN DEMO (LAMBDA (FUN LST)
      (PRIN1 "Результат действия MAPCAR: ")
      (MAPCAR FUN LST)
   ))
   % ------------------- %
   (DEFUN FACT (LAMBDA (X)
      (COND ( (ZEROP X) 1 )
            ( T (TIMES X (FACT (DIFFERENCE X 1))) )
      )
   ))
   % --------------------------- %
   (DEFUN MAPCAR (LAMBDA (FUN LST)
      (COND ( (NULL LST) NIL )
            (   T   (CONS (FUN (CAR LST))
                          (MAPCAR FUN (CDR LST))) )
      )
   ))

Тестовый пример:


   $ (DEMO FACT (2 3 4))
   (2 6 24)

Пример 4. Прямое произведение двух числовых множеств можно определить через два вложенных цикла, которые можно выразить с помощью композиции двух вложенных вызовов функционала MAPCAR:

   (DEFUN DECART (LAMBDA (X Y)
   % X и Y - списки %
      (MAPCAR (QUOTE (LAMBDA (X)
         (MAPCAR (QUOTE (LAMBDA (Y) (LIST X Y))) Y))) X)
   ))
   % --------------------------- %
   (DEFUN MAPCAR (LAMBDA (FUN LST)
       (COND ( (NULL LST) NIL )
             ( T  (CONS (FUN (CAR LST))
                        (MAPCAR FUN (CDR LST))) )
       )
   ))

Тестовый пример:


   $ (DECART (A B C) (1 2 3))
   (((A 1) (A 2) (A 3)) ((B 1) (B 2) (B 3)) ((C 1) (C 2)
   (C 3)))

Замечание 1. Заметим, что обращение к функции MAPCAR следующим образом:


   (MAPCAR FN (X1 X2 ... XN))

эквивалентно обращению к функции LIST:


   (LIST (FN X1) (FN X2) ... (FN XN))

Замечание 2. Функция (MAPCAR FN LIST1...LISTN) выполняет действия, предписанные функцией FN, над CAR-элементами списков LIST1,...,LISTN, затем - над CADR-элементами каждого списка, и т.д. до тех пор, пока каждый список не будет исчерпан. Функция MAPCAR возвращает список результатов. Например:


   $ (MAPCAR '*'(2 3 5 7) '(2 4 6 8))
   (4 12 30 56)

Код функции в системе muLISP85 имеет вид:

   (DEFUN MAPCAR (FUNC LST1 LST2)
      ( (OR (NULL LST1) (NULL LST2)) NIL )
      (CONS (FUNCALL FUNC (CAR LST1) (CAR LST2))
            (MAPCAR FUNC (CDR LST1) (CDR LST2)))
   )

На следующем шаге мы продолжим изучение отображающих функционалов, в частности, рассмотрим функцию MAPLIST.

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