Common Lisp/Функції планування

Функції планування

Функції планування, або MAP - функції (mapping function) являють собою важливий клас функцій в мові програмування Лісп. Їх навіть правильно буде називати функціоналами, оскільки в якості аргументів вони приймають інші функції. MAP - функціонали відображають список або послідовність у нову послідовність, або породжують побічний ефект, який є повязаним з цією послідовністю. Імена функцій планування починаються з MAP та їх виклик має вигляд: (MAPx fn i1 i2 ... iN), де fn – функція від N аргументів, i1, i2, ...,iN – списки. Часто MAP - функціонал застосовується до одного аргумента - списку, тобто fn є функцією одного аргумента: (MAPx fn <список>).

Повторення обчислення функції на елементах списка

(MAPCAR <функція> <список1> ... <списокN>)

Виконуються дії <функції> над CAR-елементами списків, потім над другими елементами списків і так далі поки елементи хоча б у одному списку не закінчаться. Для двох вхідних списків у Ліспі ця функція може бути визначєна наступним чином:

(DEFUN MAPCAR2 (func lst1 lst2)
  ((OR (NULL lst1) (NULL lst2)) NIL)

(CONS (FUNCALL func (CAR lst1) (CAR lst2))
  (MAPCAR2 func (CDR lst1) (CDR lst2))) )

Результатом функції є список, який побудовано з результатів виклику функціонального аргумента MAPCAR.

$ (MAPCAR '+ '(1 2 3) '(7 8 9) '(10 11 12))$ (MAPCAR 'cons '(1 2 3) '(a b c))

(18 21 24)((1 . A) (2 . B) (3 . C))

$ (MAPCAR 'atom '(1 2 3 4))$ (MAPCAR '(lambda (x) (list x (* x x))) '(1 2 3))

(T T T T)((1 1) (2 4) (3 9))

Повторення обчислення функції на хвостових частинах списка

(MAPLIST <функція> <список1> ... <списокN>)

Функція MAPLIST на відміну від функції MAPCAR діє не над елементами списків, а над їх хвостовими послідовностями. Тобто спочатку дії виконуються над вхідними списками, потім – над їх CDR – елементами, і так далі поки хоча б один зі списків не буде вичерпано. Для двох вхідних списків у Ліспі ця функція може бути визначєна наступним чином:

(DEFUN MAPLIST2 (func lst1 lst2)
((OR (NULL lst1) (NULL lst2)) NIL)
(CONS (FUNCALL func lst1 lst2) (MAPLIST2 func (CDR lst1) (CDR lst2))))

$ (MAPLIST 'CONS '(1 2 3) '(10 11 12))$ (MAPLIST 'REVERSE '(1 2 3 4))

(((1 2 3) 10 11 12) ((2 3) 11 12) ((3) 12))((4 3 2 1) (4 3 2) (4 3) (4))

Об’єднуючі функції

(MAPCAN <функція> <список1> ... <списокN>)

(MAPCON <функція> <список1> ... <списокN>)

Функції MAPCAN та MAPCON є відповідно аналогами функцій MAPCAR та MAPLIST, тільки вони не будують новий список з результатів використовуючи функцію LIST, а зв’язують результати (які обов’язково повинні бути списками), використовуючи функцію NCONC.

Об’єднуючі функції можна використовувати як фільтри. Під фільтром ми будемо розуміти функцію, яка залишає або видаляє елементи, які задовільняють певній умові. Наступний приклад показує, як можна зі списку вилучити всі невід’ємні числа.

$ (MAPCAN '(LAMBDA (n) ((MINUSP n)(LIST n))) '(2 -3 3 4 -4 -5 5))

(-3 -4 -5)

Зазначимо, що наступні дії еквівалентні:

(MAPCAN f ‘(x1 x2 ... xN))та(NCONC (f ‘x1) (f ‘x2) ... (f ‘xN))

(MAPCAN f x1 x2 ... xN)та(APPLY ‘NCONC (MAPCAR f x1 x2 ... xN))

(MAPCON f x1 x2 ... xN)та(APPLY ‘NCONC (MAPLIST f x1 x2 ... xN))

$ (MAPCON 'REVERSE '(1 2 3)) $ (APPLY 'NCONC (MAPLIST 'REVERSE '(1 2 3)))

(3 2 1 3 2 3) (3 2 1 3 2 3)

Обчислення функції із загубленням результату

(MAPC <функція> <список1> ... <списокN>)

(MAPL <функція> <список1> ... <списокN>)

Функції MAPC та MAPL є відповідно аналогами функцій MAPCAR та MAPLIST, тільки вони не збирають та не об’єднують результати. Результати, що отримуються просто не зберігаються. В якості результату повертається другий аргумент функції. Ці функції використовують для отримання побочного ефекту:

$ (MAPC '(LAMBDA (u v) (SET u v)) '(a b c) '(1 2 3))

(A B C)

Після цього значенням змінних a, b, c будуть відповідно присвоєні числа 1,2 та 3.

Функції планування можна об’єднувати у більш складні структури, їх композицію можна використовувати при визначенні інших функцій. Наприклад, декартів добуток двох множин можна просто отримати за допомогою композиції двох вкладених викликів функціонала MAPCAR (справа подано результат роботи функції):

(DEFUN decart (x y) $ (decart '(q w) '(2 3 4))

(MAPCAR (((Q 2) (Q 3) (Q 4)) ((W 2) (W 3) (W 4)))

'(LAMBDA (x1)

(MAPCAR '(LAMBDA (y1)Замінимо у другому рядку функцію

(LIST x1 y1))MAPCAR на MAPCAN, отримаємо:

y)) ((Q 2) (Q 3) (Q 4) (W 2) (W 3) (W 4))

x))

MAP - функціонали не підвищують обчислювальну потужність Ліспу, але є зручними засобами у програмуванні. Як ми побачили, в якості першого їх аргументу є функція. В залежності від арності цієї функції, після функціонального аргумента йде відповідна кількість аргументів - списків. Якщо списки різні по довжині, то кількість повторень визначається довжиною найбільш короткого списка.

Розглянемо приклад застосування функцій планування на прикладі задачі додавання двох матриць. Функція vectorsum знаходить вектор, який дорівнює сумі її двох аргументів - векторів. Функція ADDMATR знаходить суму двох матриць.

(DEFUN vectorsum (x y)
  (MAPCAR '+ x y))

(DEFUN addmatr (x y)
  (MAPCAR 'vectorsum x y))

$ (addmatr '((1 2 3)(4 5 6)(7 8 9)) '((1 1 1)(2 2 2)(3 3 3))) $ ((2 3 4) (6 7 8) (10 11 12))

Наступні предикати планування виконують тестові функції над елементами одного чи декількох списків поки не зустрінеться або критерій закінчення, або кінець одного зі списків. Наведені далі функції виконують дії предиката <тест> над car-об’єктами <списку1>, ..., <спискуN>, потім - над cadr-об’єктами кожного списку і так далі поки тест не поверне значення, відмінне від NIL, або не зустрінеться кінець списку.

(SOME <тест>, <список1>, <список2>, ..., <списокN>). Якщо тест повертає значення, відмінне від NIL, SOME повертає це значення. Якщо кінець списку досягнуто, SOME повертає NIL. Функцію SOME можна визначити наступним чином:

(DEFUN SOME (TST LST1 LST2)
  (LOOP
  ((OR (NULL LST1) (NULL LST2)) NIL)
  ((FUNCALL TST (POP LST1) (POP LST2))) ) )

$ (SOME 'EQL '(DOG CAT COW) '(COW CAT DOG)) T

$ (SOME 'PLUSP (LIST 0 -3 -4 -6)) NIL

(NOTANY <тест>, <список1>, <список2>, ..., <списокN>). Якщо тест повертає значення, відмінне від NIL, NOTANY повертає NIL. Якщо зустрінеться кінець списку, повертається Т. Функцію NOTANY можна визначити наступним чином:

(DEFUN NOTANY (TST LST1 LST2)

(NOT (SOME TST LST1 LST2)) )

$ (NOTANY 'EQL '(DOG CAT COW) '(COW CAT DOG))

NIL

$ (NOTANY 'ODDP (LIST 0 (+3 3) 7/2))

T

(EVERY <тест>, <список1>, <список2>, ..., <списокN>). Якщо тест видає NIL, EVERY повертає NIL. Якщо зустрінеться кінець списку, EVERY повертає Т. Функцію EVERY можна визначити наступним чином:

(DEFUN EVERY (TST LST1 LST2)

(LOOP

((OR (NULL LST1) (NULL LST2)) NIL)

((NOT (FUNCALL TST (POP LST1) (POP LST2))) T) )

$ (EVERY 'EQL '(DOG CAT COW) '(DOG CAT PIG))

NIL

$ (EVERY 'ODDP (LIST 3 5 7 11 13))

T

(NOTEVERY <тест>, <список1>, <список2>, ..., <списокN>). Якщо тест повертає NIL, NOTEVERY повертає Т. Якщо зустрінеться кінець спискy, NOTEVERY повертає NIL. Функцію NOTEVERY можна визначити наступним чином:

(DEFUN NOTEVERY (TST LST1 LST2)

(NOT (EVERY TST LST1 LST2)) )

$ (NOTEVERY 'EQL '(DOG CAT COW) '(DOG CAT PIG))

T

$ (NOTEVERY 'STRING< '(BILL JACK JOE) '(BUD JIM SUE))

NIL

(REDUCE <функція> <список> <початкове значення>) перетворює значення елементів <списку> до простого значення, використовуючи <функцію> - функцію двох аргументів. Перетворення відбувається у відповідності з початковим значенням зліва направо. По замовченню початковим значенням для операції + є 0, для * є 1.

$ (REDUCE 'CONS '(A B C D))$ (REDUCE '* '(2 3 5 7)) $ (REDUCE '+ NIL)

(((A . B) . C) . D)2100

$ (REDUCE '* '(2 3 5 7) -2)$ (REDUCE '* NIL)

-4201

Розглянемо задачу транспонування матриці, поданої у вигляді складного списку. Функція TRANS транспонує матрицю.

(DEFUN TRANS (matr)

((EVERY 'NULL matr) NIL)

(CONS (MAPCAR 'CAR matr) (TRANS (MAPCAR 'CDR matr))) )

Розглянемо роботу функції TRANS на прикладі по крокам:

(TRANS ‘((1 2 3)(4 5 6)(7 8 9)))

(CONS ‘(1 4 7) (TRANS ‘((2 3)(5 6)(8 9))))

(CONS ‘(1 4 7) (CONS ‘(2 5 8) (TRANS ‘((3)(6)(9)))))

(CONS ‘(1 4 7) (CONS ‘(2 5 8) (CONS ‘(3 6 9) (TRANS ‘( () () () )))))

(CONS ‘(1 4 7) (CONS ‘(2 5 8) (CONS ‘(3 6 9) NIL)))

(CONS ‘(1 4 7) (CONS ‘(2 5 8) ‘((3 6 9)) ))

(CONS ‘(1 4 7) ‘((2 5 8) (3 6 9)) )

((1 4 7)(2 5 8)(3 6 9))

Далі напишемо функцію MULT – множення двох матриць. Але спочатку напишемо декілька допоміжних функцій.

Функція SCALAR знаходить скалярний добуток двох векторів, представлених списками x та y.

(DEFUN SCALAR (x y)$ (SCALAR ‘(1 2 3) ‘(4 5 6))

(APPLY '+ (MAPCAR '* x y)) 32

Функція MULT2 будує список скалярних добутків вектора x на елементи списку y, які є векторами

(DEFUN MULT2 (x y)
  (MAPCAR 'SCALAR (MAKE-LIST (LENGTH x) x) y) )

$ (MULT2 ‘(1 2 3) ‘((1 2 3)(4 5 6)(7 8 9))) (14 32 50)

Функція MULT1 утворює список списків скалярних добутків усіх можливих елементів x та y.

(DEFUN MULT1 (x y)

(MAPCAR 'MULT2 x (MAKE-LIST (LENGTH y) y)) )

$ (MULT1 ‘((1 2 3)(4 5 6)(7 8 9)) ‘((1 2 3)(4 5 6)(7 8 9)))

((14 32 50) (32 77 122) (50 122 194))

(DEFUN MULT (x y)
(MULT1 x (TRANS y)))

$ (MULT ‘((1 2 3)(4 5 6)(7 8 9)) ‘((1 2 3)(4 5 6)(7 8 9)))

((30 36 42) (66 81 96) (102 126 150))

Завдання

1. Знайти кількість атомів у списку з підсписками.
2. Знайти глибину списку з підсписками.
3. Знайти найбільший (найменший) елемент у списку з підсписками.
4. Вважаючи що вхідний складний список є дерево гри (елементи якого мість лише числа), написати функцію міні-максного пошуку.
5. Лінеризувати список 6. За вхідною матрицею m*n утворити списки x₁x₂...x_n, де x_i – сума чисел i-ого стовпчика та y₁y₂...y_n, де y_i – сума чисел i-ого рядка.
6. Написати функцію rev обернення списку з підсписками.
7. Знайти суму чисел матриці.

Відповіді

1. $ (DEFUN catom (s)

((ATOM s) 1)

(APPLY '+ (MAPCAR 'catom s)) )

2. $ (DEFUN depth (s)

((ATOM s) 0)

(ADD1 (APPLY 'MAX (MAPCAR 'depth s))) )

3. $ (DEFUN biggest (s)

((ATOM s) s)

(APPLY 'MAX (MAPCAR 'biggest s)) )

4. $ (DEFUN big1 (s) (DEFUN sm1 (s)

((ATOM s) s)((ATOM s) s)

(APPLY 'MAX (MAPCAR 'sm1 s)) )(APPLY 'MIN (MAPCAR 'big1 s)) )

5. $ (DEFUN lin (s)

((ATOM s) (LIST s))

(MAPCAN 'lin s))

6. $ (DEFUN sum (matr)

((EVERY 'NULL matr) NIL)

(CONS (APPLY '+ (MAPCAR 'CAR matr)) (sum (MAPCAR 'CDR matr))) )

$ (DEFUN sumr (matr)

((EVERY 'NULL matr) NIL)

(CONS (APPLY '+ (CAR matr)) (sumr (CDR matr))) )

7. $ (DEFUN rev (lst)

((ATOM lst) lst)

(REVERSE (MAPCAR 'rev lst)) )

8. $ (DEFUN SUMatom (s)

((ATOM s) s)

(APPLY '+ (MAPCAR 'SUMatom s)) )