WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Функції планування - Реферат

Функції планування - Реферат


Реферат на тему:
Функції планування
Функції планування, або MAP - функції (mapping function) являють собою важливий клас функцій в мові програмування Лісп. Їх навіть правильно буде називати функціоналами, оскільки в якості аргументів вони приймають інші функції. MAP - функціонали відображають список або послідовність у нову послідовність, або породжують побічний ефект, який є повязаним з цією послідовністю. Імена функцій планування починаються з MAP та їх виклик має вигляд: (MAPx fn i1 i2 ... iN), де fn - функція від N аргументів, i1, i2, ...,iN - списки. Часто MAP - функціонал застосовується до одного аргумента - списку, тобто fn є функцією одного аргумента: (MAPx fn ).
1. Повторення обчислення функції на елементах списка
(MAPCAR ... )
Виконуються дії над 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))
2. Повторення обчислення функції на хвостових частинах списка
(MAPLIST ... )
Функція 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))
3. Об'єднуючі функції
(MAPCAN ... )
(MAPCON ... )
Функції 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)
4. Обчислення функції із загубленням результату
(MAPC ... )
(MAPL ... )
Функції 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) (DEFUN addmatr (x y)
(MAPCAR '+ 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))
Наступні предикати планування виконують тестові функції над елементами одного чи декількох списків поки не зустрінеться або
Loading...

 
 

Цікаве