MULISP7
.docCLRSCRN
Лабораторная работа N°7
Эта лабораторная работа посвящена изучению дополнительных
функций обработки списков в мю-Лиспе. Данные функции помогут Вам
лучше разобраться с представлением и обработкой списков.
Для каждой функции будут приведены название, описание,
формат вызова, примеры реализации и использования, а также кон-
трольный пример. Постарайтесь предсказать результаты выполнения
всех контрольных примеров и сравните их с реально полученными
результатами.
CONTINUE
NTHCDR [n,list] Function
Если n - ноль или положительное целое, (NTHCDR n list)
возвращает n-й cdr <списка>. NTHCDR возвращает NIL, если n - ни
0, ни положительное целое, или если <список> имеет n или меньше
элементов.
Пример:
(DEFUN NTHCDR (N LST)
((ZEROP N) LST)
((AND (INTEGERP N) (PLUSP N))
((ATOM LST) NIL)
(NTHCDR (SUB1 N) (CDR LST)) ) )
(NTHCDR 0 '(A B C D)) --> (A B C D)
(NTHCDR 1 '(A B C D)) --> (B C D)
(NTHCDR 2 '(A B C D)) --> (C D)
(NTHCDR 5 '(A B C D)) --> NIL
(NTHCDR 2 '(A B . C)) --> C
CONTINUE
Контрольный пример:
(NTHCDR '3 '(A B C.D E)) --> ?
CONTINUE
(NTHCDR '3 '(A B C.D E)) --> (E)
CONTINUE
NTH [n,list] Function
Если n - ноль или положительное целое, (NTH n list)
возвращает n-й элемент <списка>, где car <списка> - нулевой
элемент. NTH возвращает NIL, если n - ноль, ни положительное
целое, либо если <список> имеет n или меньше элементов.
Пример:
(DEFUN NTH (N LST)
((ATOM (NTHCDR N LST)) NIL)
(CAR (NTHCDR N LST)) )
(NTH 0 '(A B C D)) --> A
(NTH 3 '(A B C D)) --> D
(NTH 4 '(A B C D)) --> NIL
(NTH 2 '(A B . C)) --> NIL
Контрольный пример:
(SETQ X 3)
3
(NTH X '(A B C D)) --> ?
(NTH 'X '(A B C D)) --> ?
CONTINUE
(NTH X '(A B C D)) --> D
(NTH 'X '(A B C D)) --> NIL
CONTINUE
SUBLIST [list,n,m] Function
Если n и m - неотрицательные целые, и n<=m, (SUBLIST list n
m) копирует и выдает с n-го по m-й элементы <списка>, где
car-элемент <списка> есть нулевой элемент. Если m - не целое
число или больше или равно длины <списка>, m принимается как
величина на единицу меньше длины <списка>. Если n - не целое
число, отрицательное число или n>m, SUBLIST возвращает NIL.
Пример:
(DEFUN SUBLIST (LST N M)
((INTEGERP N)
((INTEGERP M)
(FIRST (ADD1 (-M N)) (NTHCDR N LST)) )
(NTHCDR N LST) ) )
(SUBLIST '(A B C D E F) 2 4) --> (C D E)
(SUBLIST '(A B C D E F) 2 2) --> (C)
(SUBLIST '(A B C D E F) 0 3) --> (A B C D)
(SUBLIST '(A B C D E F) 2) --> (C D E F)
Контрольный пример:
(SUBLIST '(A.(B.(C D))) 1 2) --> ?
CONTINUE
(SUBLIST '(A.(B.(C D))) 1 2) --> ( B.(C D) )
CONTINUE
COUNT [object,list,test] Function
COUNT-IF[test,list] Function
(COUNT object list test) возвращает количество эдементов в
<списке>, для которых признак при сравнении с
<обьектом> по <тесту> не равен NIL. Если <тест>-аргумент не задан
или равен NIL, COUNT использует EQL-тест.
(COUNT-IF test list) возвращает количество элементов в
<списке>, для которых признак проверки по <тесту> - не NIL.
Пример:
(DEFUN COUNT (OBJ LST TEST)
(count-aux (OBJ LST TEST 0) )
(DEFUN count-aux (OBJ LST TEST COUNTER)
((ATOM LST) COUNTER)
( ((NULL TEST)
(SETQ TEST 'EQL) ) )
((FUNCALL TEST OBJ (CAR LST))
(count-aux OBJ (CDR LST) TEST (ADD1 COUNTER)) )
(count-aux OBJ (CDR LST) TEST COUNTER) )
(COUNT 'DOG '(CAT DOG COW PIG DOG ANT)) --> 2
(COUNT-IF 'EVENP '(3 -6 8 7 0)) --> 3
CONTINUE
Контрольный пример:
(COUNT '"Крысюк" '( ("Губкин" "Опалева")
("Балтрашевич" "Первозванский")
("Первицккий" "Герасимова")
("Крысюк" "Крысюк" "Крысюк") )
'MEMBER ) --> ?
CONTINUE
(COUNT '"Крысюк" '( ("Губкин" "Опалева")
("Балтрашевич" "Первозванский")
("Первицккий" "Герасимова")
("Крысюк" "Крысюк" "Крысюк") )
'MEMBER ) --> 1
CONTINUE
FIND [object,list,test] Function
FIND-IF [test,list] Function
(FIND обьект список тест) выполняет линейный поиск в
<списке> того элемента, для которого признак проверки с
<обьектом> по <тесту> есть не NIL. Если тест-аргумент есть NIL
или не задан, FIND использует EQL-тест.
(FIND-IF тест список) исследует <список> для поиска
элемента, для которого признак проверки по <тесту> есть не NIL.
Для обеих функций, если элемент, удовлетворяющий тесту, найден,
данный элемент выдается, в противном случае возвращается NIL.
Пример:
(DEFUN FIND (OBJ LST TEST)
( (ATOM LST) NIL)
( ((NULL TEST)
(SETQ TEST 'EQL) ) )
( (FUNCALL TEST JBJ (CAR LST))
(CAR LST) )
(FIND OBJ (CDR LST) TEST) )
CONTINUE
(FIND 'EAT '(CORN WHEAT OATS RICE) 'FINDSTRING) --> WHEAT
(FIND-IF '(LAMBDA (X) (MINUSP (CDR X)))
'((X . 3) (Y . 0) (Z . -2/3))) --> (Z . -0.6666666)
Контрольный пример:
(FIND '"Крысюк" '( ("Губкин" "Опалева")
("Балтрашевич" "Первозванский")
("Первицккий" "Герасимова")
("Крысюк" "Крысюк" "Крысюк") )
'MEMBER ) --> ?
CONTINUE
(FIND '"Крысюк" '( ("Губкин" "Опалева")
("Балтрашевич" "Первозванский")
("Первицккий" "Герасимова")
("Крысюк" "Крысюк" "Крысюк") )
'MEMBER ) --> ("Крысюк" "Крысюк" "Крысюк")
CONTINUE
POSITION [object,list,test] Function
POSITION-IF [test,list] Function
(POSITION обьект список тест) выполняет линейный поиск в
<списке> того элемента, для которого признак сравнения с
<обьектом> по <тесту> есть не NIL. Если тест-аргумент - NIL или
не задан, POSITION использует EQL-тест.
(POSITION-IF тест список) ищет в <списке> элемент, для
которого признак проверки по тесту есть не NIL. Для обеих
функций, если элемент, удовлетворяющий тесту, найден,
возвращается порядковый номер данного элемента, начиная с 0. В
противном случае возвращается NIL.
Пример:
(DEFUN POSITION (OBJ LST TEST)
(position-aux OBJ LST TEST 0) )
(DEFUN position-aux (OBJ LST TEST INDEX)
((ATOM LST) NIL)
( ((NULL TEST)
(SETQ TEST 'EQL) ) )
(FUNCALL TEST OBJ (CAR LST)) INDEX)
(position-aux OBJ (CDR LST) TEST (ADD1 INDEX)
CONTINUE
(POSITION '(A B C) '((R S T) (C A B) (A B C))) --> NIL
(POSITION '(A B C) '((R S T) (C A B) (A B C)) 'EQUAL) --> 2
(POSITION-IF 'PLUSP '(-2.5 0 3.7 -5.3)) --> 2
Контрольный пример:
(POSITION '(A.(B.(C.(D)))) '( (A.(B.(C D)))
(A B C.D)
(A B C D) )
'EQUAL) --> ?
CONTINUE
(POSITION '(A.(B.(C.(D)))) '( (A.(B.(C D)))
(A B C.D)
(A B C D) )
'EQUAL) --> NIL
CONTINUE
NSUBSTITUTE [new,old,list,test] Function
NSUBSTITUTE-IF [new,test,list] Function
Модифицируя cons-ы высокого уровня <списка>, (NSUBSTITUTE
новый старый список тест) замещает на <новые> элементы те
<старые> элементы <списка>, для которых признак проверки по
<тесту> отличен от NIL.Если <тест>-аргумент есть NIL или не
задан, NSUBSTITUTE использует EQL-тест.
(NSUBSTITUTE-IF новый тест список) замещает на <новые>
элементы <списка>, для которых признак проверки по <тесту>
отличен от NIL.
Пример:
(DEFUN NSUBSTITUTE (NEW OLD LST TEST)
((ATOM LST) LST)
( ((NULL TEST)
(SETQ TEST 'EQL) ) )
((FUNCALL TEST OLD (CAR LST))
(RPLACA LST NEW)
(NSUBSTITUTE NEW OLD (CDR LST) TEST) )
(NSUBSTITUTE NEW OLD (CDR LST) TEST) )
CONTINUE
(NSUBSTITUTE 5 2 '(4 2 (3 . 2) 4)) --> (4 5 (3 . 2) 4)
(NSUBSTITUTE 'CANNIBALS 'NOUN '(NOUN LIKE TO EAT NOUN))
--> (CANNIBALS LIKE TO EAT CANNIBALS)
Контрольный пример:
(NSUBSTITUTE-IF '5 'ATOM '(3 (2.7) NIL) ) --> ?
CONTINUE
(NSUBSTITUTE-IF '5 'ATOM '(3 (2.7) NIL) ) --> (5 5 5)
CONTINUE
NSUBST [new,old,object,test] Function
NSUBST-IF [new,test,object] Function
Модифицируя cons-ы <обьекта>, (NSUBST новый старый обьект
тест) замещает на <новые> все подвыражения <обьекта>, для которых
признак проверки по <тесту> отличен от NIL. Если тест-аргумент
есть NIL или не задан, NSUBST использует EQL-тест.
(NSUBST-IF новый тест обьект) замещает на <новые> все
подвыражения <обьекта>, для которых признак проверки по <тесту>
отличен от NIL.
Пример:
(DEFUN NSUBST (NEW OLD OBJ TEST)
( ((NULL TEST)
(SETQ TEST 'EQL) ) )
((FUNCALL TEST OLD OBJ) NEW)
((ATOM OBJ) OBJ)
(RPLACA OBJ (NSUBST NEW OLD (CAR OBJ) TEST))
(RPLACA OBJ (NSUBST NEW OLD (CDR OBJ) TEST)) )
CONTINUE
(NSUBST 5 2 '(4 2 (3 . 5 ) 4) ) --> (4 5 (3.5) 4)
Контрольный пример:
(NSUBST '(2.5) 4 '(4 2 (3.5 ) 4) ) --> ?
CONTINUE
(NSUBST '(2.5) 4 '(4 2 (3.5 ) 4) ) --> ((2.5) 2 (3.5) (2.5))
CONTINUE
NBUTLAST [list,n] Function
Если <n> - ноль или положительное целое, то (NBUTLAST список
n) возвращает список, состоящий из всех, кроме последних <n>
элементов <списка>, путем замещения cdr-элемента n-того cons-а,
взятого из конца <списка>, на NIL. Отсутствие n отождествляется с
1.
Пример:
(DEFUN NBUTLAST (LST N)
((AND (INTEGERP N) (>=N 0))
(NREVERSE (NTHCDR N (NREVERSE LST))) )
(NBUTLAST LST 1) )
(NBUTLAST '(A B C D)) --> (A B C)
(NBUTLAST '(A B C D) 2) --> (A B)
(SETQ FOO '(A B C)) --> (A B C)
(NBUTLAST FOO) --> (A B)
FOO --> (A B)
(NBUTLAST FOO 2) --> NIL
FOO --> (A B)
CONTINUE
Контрольный пример:
(SETQ STUDENTS '(IVAN ALEX.NATALY) )
(NBUTLAST STUDENTS 1) --> ?
CONTINUE
(SETQ STUDENTS '(IVAN ALEX.NATALY) )
(NBUTLAST STUDENTS 1) --> (IVAN)
CONTINUE
NCONC [list1,list2,...,listN] Function
(NCONC список1,...,списокN) выдает список, состоящий из
элементов списков <список1>,...,<списокN> в том же порядке, путем
модификации последних cdr-элементов <списка1>,...,<спискаN>.
Отметим, что NCONC и APPEND,заданные с одинаковыми
аргументами, выдадут эквивалентные списки.
Если значением FOO является список, то (NCONC FOO FOO)
создаст циркулярный список, и если будет сделана попытка выдать
на экран дисплея значение FOO, то этот процесс будет длиться
бесконечно.
Пример:
(DEFUN NCONC (LST1 LST2)
((ATOM LST1) LST2)
(RPLACD (LAST LST1) LST2)
LST1 )
(SETQ FOO '(D E F)) --> (D E F)
(NCONC '(A B C) FOO '(G H I)) --> (A B C D E F G H I)
FOO --> (D E F G H I)
CONTINUE
Контрольный пример:
(SETQ ALFA '(A B C) )
(NCONC ALFA '(D E) (NBUTLAST (REVERSE ALFA) 1) ) --> ?
CONTINUE
(SETQ ALFA '(A B C) )
(NCONC ALFA '(D E) (NBUTLAST (REVERSE ALFA) 1) ) -->
(A B C D E C B)
CONTINUE
TCONC [dotted-pair,object] Function
(TCONC точечная-пара обьект) добавляет <обьект> в конец
списка, car-элемент указывает на <точечную-пару>, список
модифицируется. TCONC возвращает <точечную-пару> и
модифицированный cdr-элемент, указывающий на новый конец списка.
TCONC добавляет элементы в конец списка, используя RPLACD
для модификации списка. Его первым аргументом яаляется точечная
пара, car-элемент которой указывает на начало списка, а
cdr-элемент - на конец (т.е. на последний cons ) списка. Вторым
аргументом является элемент, который был добавлен в конец списка.
Как показано на примере, когда TCONC вызывается в 1-й раз, ее 1-м
аргументом будет атом NIL или список (NIL).
Пример:
(DEFUN TCONC (PAIR OBJ)
(SETQ OBJ (LIST OBJ))
((ATOM PAIR)
((CONS OBJ OBJ) )
((ATOM (CDR PAIR))
(RPLACA PAIR OBJ)
(RPLACD PAIR OBJ) )
(RPLACD (CDR PAIR) OBJ)
(RPLACD PAIR OBJ) )
CONTINUE
(SETQ FOO NIL) --> NIL ;set FOO to NIL
(SETQ FOO (TCONC FOO 'A)) --> ((A) A)
(TCONC FOO 'B) --> ((A B) B)
(TCONC FOO 'C) --> ((A B C) C)
(CAR FOO) --> (A B C)
(SETQ FOO (CONS NIL)) --> (NIL)
(TCONC FOO 'A) --> ((A) A)
(TCONC FOO 'B) --> ((A B) B)
(TCONC FOO 'C) --> ((A B C) C)
(CAR FOO) --> (A B C)
Контрольный пример:
(TCONC '(B.C D) '(E F)) --> ?
CONTINUE
(TCONC '(B.C D) '(E F)) --> (B . C (E F))
CONTINUE
LCONC [dotted-paip] Function
(LCONC точечная-пара список) добавляет <список> в конец
списка, на который указывает car-элемент <точечной пары>, путем
модификации списка. LCONC возвращает точечную пару, чей
cdr-элемент модифицируется и указывает на новый конец списка.
LCONC добавляет новые списки в хвостовой конец списка, используя
RPLACD для модификации списка. Его 1-м аргументом является cons,
car-элемент которого указывает на начало списка, а cdr-элемент -
на конец (т.е. на последний cons) списка. Вторым аргументом LCONC
является элемент, который был добавлен в конец списка. Как
показано на примерах, при первоначальном вызове LCONC первым ее
аргументом будет атом NIL или список (NIL).
Пример:
(DEFUN LCONC (PAIR LST)
((ATOM LST) PAIR)
((ATOM PAIR)
(CONS LST (LAST LST)) )
((ATOM (CDR PAIR))
(RPLACA PAIR LST)
(RPLACD PAIR (LAST LST)) )
(RPLACD (CDR PAIR) LST)
(RPLACD PAIR (LAST LST)) )
CONTINUE
(SETQ FOO NIL) --> NIL ;set FOO to NIL
(SETQ FOO (LCONC FOO '(A B))) --> ((A B) B)
(LCONC FOO '(C D)) --> ((A B C D) D)
(LCONC FOO '(E F)) --> ((A B C D E F) F)
(CAR FOO) --> (A B C D E F )
(SETQ FOO (CONS NIL)) --> (NIL) ; set FOO to (NIL)
(LCONC FOO '(A B)) --> ((A B) B)
(LCONC FOO '(C D)) --> ((A B C D) D)
(LCONC FOO '(E F)) --> ((A B C D E F) F)
(CAR FOO) --> (A B C D E F)
Контрольный пример:
(LCONC '(A.B C) '(D E)) --> ?
CONTINUE
(LCONC '(A.B C) '(D E)) --> (A.B E)
CONTINUE
SPLIT [list] Function
(SPLIT список) разбивает <список> на два списка путем замены
cdr-элемента cons-а верхнего уровня, стоящего посередине
<списка>, на NIL. SPLIT возвращает хвост <списка>, начиная с
места разбиения.
Если <список> имеет четное количество элементов, его голова и
хвост при разбиении будут иметь одинаковое количество элементов.
Если <список> имеет нечетное количество элементов, голова будет
иметь на один элемент больше, чем хвост.
Пример:
(DEFUN SPLIT (LST)
((ATOM LST) LST)
(split-aux LST (CDR LST)) )
(DEFUN split-aux (HEAD TAIL)
((ATOM TAIL)
(PROG1 (CDR HEAD) (RPLACD HEAD NIL)) )
(POP TAIL)
((ATOM TAIL)
(PROG1 (CDR HEAD) (RPLACD HEAD NIL)) )
(split-aux (CDR HEAD) (CDR TAIL)) )
CONTINUE
(SETQ NAMES '(TOM SUE JOE PAT SAM)) --> (TOM SUE JOE PAT SAM)
(SPLIT NAMES) --> (PAT SAM)
NAMES --> (TOM SUE JOE)
Контрольный пример:
(SETQ ALFA '(A.(B.(C D))) )
(SPLIT ALFA) --> ?
CONTINUE
(SETQ ALFA '(A.(B.(C D))) )
(SPLIT ALFA) --> ((B. (C. (D E))))
CLRSCRN
^Z