Отображения и функционалы

Функционалы - общее понятие

Рассмотрим технику использования функционалов на упражнениях с числами и покажем, как от простых задач перейти к более сложным.

Для каждого числа из заданного списка получить следующее за ним число и все результаты собрать в списокЗдесь и далее, следуя CLISP, (COND NIL) = NIL, т.е. допускается отсутствие предиката со значение "истина".

(DEFUN next (xl)                
;; Следующие числа*)    
   (COND                        ; пока список не пуст         
      (x (CONS (1+  (CAR xl))   ; прибавляем 1 к его "голове"                
            (next (CDR xl))  ; и переходим к остальным,
 )   )  )  )        ; собирая результаты в список
  (next '(1 2 5))         ; = (2 3 6)

Построить список из <голов> элементов списка

(DEFUN 1st (xl)
                        ; "головы" элементов = CAR
  (COND                 ; пока список не пуст
    (xl (CONS (caar xl); выбираем CAR от его головы
      (1st (CDR xl))   ; и переходим к остальным,
) ) ) )                ; собирая результаты в список

(1st '((один два)(one two)(1 2)) )   ; = (один one 1)

Выяснить длины элементов списка

(DEFUN lens (xl)    ; Длины элементов
   (COND            ; Пока список не пуст  
     (xl (CONS (length (CAR xl))  
                    ; вычисляем длину его головы
      (lens (CDR xl)); и переходим к остальным,
) ) ) )             ; собирая результаты в список  
   
  (lens '((1 2) () (a b c d) (1(a b c d)3)) )     
                   ; = (2 0 4 3)

Внешние отличия в записи этих трех функций малосущественны, что позволяет ввести более общую функцию MAP-EL, в определении которой имена "CAR", "1+" и "LENGTH" могут быть заданы как значения параметра fn:

(DEFUN map-el(fn xl)
                 ; Поэлементное преобразование XL с помощью функции FN
   (COND         ; Пока XL не пуст
      (xl (CONS (FUNCALL fn (car xl)) 
             ; применяем FN как функцию к голове XL**)
         (map-el fn (CDR xl)) 
                  ; и переходим к остальным, 
) ) ) )            ; собирая результаты в список

Эффект функций NEXT, 1ST и LENS можно получить выражениями:

(map-el #'1+ xl)        ; Следующие числа:
(map-el #'CAR xl)       ; "головы" элементов = CAR
(map-el #'length xl)    ; Длины элементов

(map-el #'1+'(1 2 5))   ; = (2 3 6)
(map-el #'CAR'((один два)(one two)(1 2)) ) 
              ; = (один one 1)
(map-el #'length'((1 2)()(a b c d)(1(a b c d)3)) ) 
              ; = (2 0 4 3) соответственно.

Примечание. #’x – эквивалент ( FUNCTION x ), что является представлением функции в качестве аргумента.

Все три примера можно решить с помощью таких определяющих выражений:

(DEFUN next(xl)
	(map-el #'1+ xl)) ; Очередные числа:
(DEFUN 1st(xl)
	(map-el #'CAR xl)) ; "головы" элементов = CAR
(DEFUN lens(xl)
	(map-el #'length xl)) ; Длины элементов

Эти определения функций формально эквивалентны ранее приведенным - они сохраняют отношение между аргументами и результатами. Параметром функционала может быть любая вспомогательная функция.

Пусть дана вспомогательная функция sqw, возводящая числа в квадрат

(DEFUN sqw (x)(* x x)) ; Возведение числа в квадрат
(sqw 3)               ; = 9

Построить список квадратов чисел, используя функцию sqw:

(DEFUN sqware (xl)
                  ; Возведение списка чисел в квадрат
   (COND      ; Пока аргумент не пуст,
      (xl (CONS (sqw (CAR xl))
                  ; применяем sqw к его голове
         (sqware(CDR xl))
                  ; и переходим к остальным,
) ) ) )          ; собирая результаты в список

(sqware'(1 2 5 7))      ; = (1 4 25 49 )

Можно использовать map-el:

(DEFUN sqware (xl) (map-el #'sqw xl))

Ниже приведено определение функции SQWARE- без вспомогательной функции, выполняющее умножение непосредственно. Оно влечет за собой двойное вычисление (CAR xl), т.е. такая техника не вполне эффективна:

(DEFUN sqware- (xl)
   (COND
      (xl (cons (* (CAR xl) (car xl) )
               ; квадрат "головы" списка
               ; "голову" вычислять приходится дважды
         (sqware- (CDR xl))
) ) ) )

Пусть дана вспомогательная функция TUPLE, превращающая любое данное в пару:

(DEFUN tuple (x) (CONS x x))  
(tuple 3)  ; = (3 . 3)
(tuple 'a)  ; = (a . a)
(tuple '(Ха))
   ; = ((Ха) . (Ха)) = ((Ха) Ха)
   ; - это одно и то же!

Чтобы преобразовать элементы списка с помощью такой функции, пишем сразу:

(DEFUN duble (xl) (map-el #'tuple xl))
                        ; дублирование элементов 
(duble '(1(a)()))   ; = ((1 . 1)((a)a)(()))

Немногим сложнее организовать покомпонентную обработку двух списков.

Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений:

(DEFUN pairl (al vl) ; Ассоциативный список
   (COND             ; Пока al не пуст,  
     (al (CONS (CONS (CAR al) (CAR vl))  
                     ; пары из <голов>.  
         (pairl (CDR al) (CDR vl))  
                     ; Если vl исчерпается,
                     ; то CDR будет давать NIL  
) ) ) )     

 (pair '(один два two three) '(1 2 два три))
 ; = ((один . 1)(два . 2)(two . два)(three . три))

Определить функцию покомпонентной обработки двух списков с помощью заданной функции FN:

(DEFUN map-comp (fn al vl)  
        ; fn покомпонентно применить
        ; к соотвественным элементам al и vl  
  (COND     
    (al (CONS (FUNCALL fn (CAR al) (CAR vl))  
        ; Вызов данного fn как функции  
       (map-comp (CDR al) (CDR vl))
) ) ) )

Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:

(map-comp #'+'(1 2 3) '(4 6 9))
         ; = (5 8 12) Суммы
(map-comp #'*'(1 2 3) '(4 6 9))
         ; = (4 12 27) Произведения
(map-comp #'CONS'(1 2 3) '(4 6 9))
         ; = ((1 . 4) (2 . 6) (3 . 9)) Пары
(map-comp #'EQ'(4 2 3) '(4 6 9))
         ; = (T NIL NIL) Сравнения

Достаточно уяснить, что надо делать с элементами списка, остальное довершит функционал MAP-COMP, отображающий этот список в список результатов заданной функции.

Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.

(DEFUN mapf (fl el)  
   (COND  ; Пока первый аргумент не пуст,  
      (fl (CONS (FUNCALL (CAR fl) el)  
          ; применяем очередную функцию
          ; ко второму аргументу  
      (mapf (CDR fl) el)  
          ; и переходим к остальным функциям,
) ) ) )   ; собирая их результаты в общий
          ; список  

 (mapf '(length CAR CDR) '(a b c d))  
          ; = (4 a (b c d))

Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками.

Безымянные функции

Определения в примерах 4.4 и 4.5 не вполне удобны по следующим причинам:

С одной стороны, последнее утверждение противоречит пониманию смысла именования как техники, обеспечивающей неоднократность применения поименованного объекта. С другой стороны, придумывать подходящие, долго сохраняющие понятность и соответствие цели, имена - задача нетривиальная.

Учитывая это, было бы удобнее вспомогательные определения вкладывать непосредственно в определения целевых функций и обходиться при этом вообще без имен. Конструктор функций LAMBDA обеспечивает такой стиль построения определений. Этот конструктор любое выражение EXPR превращает в функцию с заданным списком аргументов (X1. .. XK) в форме так называемых LAMBDA-выражений:

(LAMBDA (x1 ... xK) expr)

Имени такая функций не имеет, поэтому может быть применена лишь непосредственно. DEFUN использует данный конструктор, но требует дать функциям имена.

Определение функций DUBLE и SQWARE из примеров 4.4 и 4.5 без использования имен и вспомогательных функций:

(DEFUN sqware (xl)
   (map-el #' (LAMBDA (x) (* x x)) xl))

(DEFUN duble (xl)
   (map-el #' (LAMBDA (x) (CONS x x)) xl))

Любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций.

Композиции функционалов, фильтры, редукции

Вызовы функционалов можно объединять в более сложные структуры таким же образом, как и вызовы обычных функций, а их композиции можно использовать в определениях новых функций. Композиции функционалов позволяют создавать и более мощные построения, достаточно ясные, но требующие некоторого внимания.

Декартово произведение хочется получить определением вида:

(DEFUN decart (x y)
   (map-el #' (lambda (i)
            (map-el #' (lambda (j) (list i j)) y)
      ) x) )

Но результат вызова

(decart '(a s d) '( e r t))

дает

(((A E) (A R) (A T)) ((S E) (S R) (S T)) ((D E) (D R) (D T)))

вместо ожидаемого

((A E) (A R) (A T) (S E) (S R) (S T) (D E) (D R) (D T))

Дело в том, что функционал MAP-EL, как и MAP-COMP (пример 4.7), собирает результаты отображающей функции в общий список с помощью операции CONS так, что каждый результат функции образует отдельный элемент.

А по смыслу задачи требуется, чтобы список был одноуровневым.

Посмотрим, что получится, если вместо CONS при сборе результатов воспользоваться функцией APPEND.

Пусть дан список списков. Нужно их все сцепить в один общий список.

(DEFUN list-ap (ll)
   (COND
      (ll (append (CAR ll)
         (list-ap (CDR ll))
) ) ) )

(list-ap '((1 2)(3 (4))))   ; = (1 2 3 (4))

Тогда по аналогии можно построить определение функционала MAP-AP:

(DEFUN map-ap (fn ll)
   (COND
      (ll (append (FUNCALL fn (CAR ll) )
         (map-ap fn (CDR ll) )
) ) ) )

(map-ap 'CDR '((1 2 3 4) (2 4 6 8) (3 6 9 12))) 
               ; = (2 3 4 4 6 8 6 9 12)

Следовательно, интересующая нас форма результата может быть получена:

(DEFUN decart(x y)
   (map-ap #'(LAMBDA(i)
         (map-el #'(LAMBDA(j)(list i j))
           y))x))
(decart '(a s d) '(e r t))
   ; = ((A E)(A R)(A T)(S E)(S R)(S T)(D E)(D R)(D T))

Сцепление результатов отображения с помощью APPEND обладает еще одним полезным свойством: при таком сцеплении исчезают вхождения пустых списков в результат. А в Лиспе пустой список используется как ложное значение, следовательно, такая схема отображения пригодна для организации фильтров. Фильтр отличается от обычного отображения тем, что окончательно собирает не все результаты, а лишь удовлетворяющие заданному предикату.

Построить список голов непустых списков можно следующим образом:

(DEFUN heads (xl) (map-ap
   #'(LAMBDA (x) (COND (x (CONS (CAR x) NIL)))) 
            ; временно голова размещается в список,
            ; чтобы потом списки сцепить
   xl
) )
(heads '((1 2) () (3 4) () (5 6)) ) 
            ; = (1 3 5)

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

Подсчитать сумму элементов заданного списка.

(DEFUN sum-el ( xl)
   (COND ((null xl) 0)
      (xl (+ (CAR xl)
         (sum-el (CDR xl) )
) ) ) )

(sum-el '(1 2 3 4) )   ; = 10

Перестроим такое определение, чтобы вместо "+" можно было использовать произвольную бинарную функцию:

(DEFUN red-el (fn xl)
   (COND ((null xl) 0)
      (xl (FUNCALL fn (CAR xl)
         (red-el fn (CDR xl) ) 
) ) ) )
(red-el '+ '(1 2 3 4) )   ; = 10

В какой-то мере MAP-AP ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.

Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.

Встроенные функционалы (Clisp)

Отображающий функционал можно написать самим, а можно и воспользоваться одним из встроенных. Согласно стандарту, в реализацию языка Clisp обычно включены функционалы: MAP, MAPCAR, MAPLIST, MAPCAN, MAPCON, MAPC, MAPL [6, 7]. Каждый из них покомпонентно обработает любой набор списков. Отличаются они схемами выбора аргументов для отображающей функции, характером воздействия на исходные данные и оформлением результатов, передаваемых объемлющим формулам.

Map

( map result-type function sequences ... )

Функция FUNCTION вызывается на всех первых элементах последовательностей, затем на всех вторых и т.д. Из полученных результатов FUNCTION формируется результирующая последовательность, строение которой задается параметром RESULT-TYPE с допустимыми значениями CONS, LIST, ARRAY, STRING, NIL.

Mapcar

( mapcar funct list ... )

Функция FUNCTION применяется к первым элементам списков, затем ко вторым и т.д. Другими словами, FUNCTION применяется к ";головам" методично сокращающихся списков, и результаты применения собираются в результирующий список.

(mapcar #'+ '(1 2 3) '(4 5 6)) 
            ; = (5 7 9)
(mapcar #'list '(1 2 3)'(4 5 6)) 
            ; = ((1 4)(2 5)(3 6))
(DEFUN evlis (args) (mapcar #'EVAL args))
            ; вычисление аргументов

(Без учета ассоциативного списка)

(DEFUN evlis (args AL) (mapcar #'(LAMBDA (x)
(EVAL x AL)) args))

Maplist

( maplist function list ... )

Функционал аналогичен MAPCAR, но FUNCTION применяется к "хвостам" списков LIST, начиная с полного списка.

(maplist #'list '(1 2 3)'(4 5 6))
      ; = (((1 2 3) (4 5 6)) ((2 3)
(5 6)) ((3) (6)))

Mapc и Mapl

Оба функционала работают как MAPCAR и MAPLIST, соответственно, за исключением того, что они в качестве формального результата выдают первый список (своеобразная аналогия с формальными аргументами).

(mapc #'list '(1 2 3)'(4 5 6)) ; = (1 2 3)
(mapl #'list '(1 2 3)'(4 5 6)) ; = (1 2 3)

Mapcan и Mapcon

И эти два функционала аналогичны MAPCAR и MAPLIST, но формирование результатов происходит не с помощью операции CONS, которая строит данные в новых блоках памяти, а с помощью деструктивной функции NCONC, которая при построении новых данных использует память исходных данных, из-за чего исходные данные могут быть искажены.

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

MAP-INTO отображает результат в конкретную последовательность.

Подведение итогов

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

Для самостоятельного решения

Можно предложить следующие задачи на применение функционалов:

1) Напишите определение функционала F-ALL, выясняющего, все ли элементы множества SET удовлетворяют заданному предикату PRED.

(DEFUN f-all (Pred Set ) . . . )

2) Напишите определение функционала F-EX, выясняющего, найдется ли в множестве SET элемент, удовлетворяющий заданному предикату PRED.

(DEFUN f-ex (Pred Set ) . . . )

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

4) Напишите универсальный фильтр, позволяющий из произвольного списка выделять при необходимости атомы, числа, строки или списки, начинающиеся с заданного атома, и т.д.

5) Пусть клетки доски типа шахматной пронумерованы по горизонтали символами, а по вертикали числами. И то, и другое перечислено в отдельных списках по порядку. Напишите функцию перечисления координат всех клеток доски, соответствующей размерам списков.

6) При анализе труднодоступных данных требуется всю потенциально полезную информацию выяснять сразу, <в одно касание>. Напишите модель такого стиля работы на примере покомпонентной обработки двух списков чисел. Роль полезной информации могут играть значения любых бинарных операций, таких как +, *, -, /, MAX, MIN и т.п.

7) Пусть программа представляет собой набор списков, содержащих имя команды и не более двух операндов. Имя расположено в списке первым. Напишите определение функционала, удобного для выдачи по мере необходимости перечня команд, или перечня первых операндов, или вторых операндов и т.п.

Подготовьте определения вспомогательных функций на все эти случаи.

8) Список содержит ежедневные сведения о количестве осадков, выпавших за весьма длительный период. Напишите функционал, позволяющий по этому списку оперативно выяснять различные сведения, наподобие:

9) Задача повышенной сложности (с решением).

Лексикон ***)

Условие задачи: Группа специалистов договорилась подготовить лексикон программирования для электронной публикации. Было решено, что надо добиться <правильности> определения понятий программирования, а именно не допускать цепочек понятий прямо или косвенно определяемых через себя. Кроме того, следует обеспечить полноту комплекта определений, т.е. всякое включенное в лексикон понятие должно иметь определение.

Напишите программу, помогающую по ходу разработки лексикона отслеживать его <правильность> и полноту.

Входные данные:

(( имя_понятия объяснение ) ... ) - 
	двухуровневый список, в котором
   имя_понятия - атом, обозначающий 
	определяемое понятие,
   объяснение - последовательность строк и/или атомов, 
   строки не требуют определения, 
	а атомы должны получить 
   определения в процессе разработки, но, возможно, 
   еще не все слова удалось объяснить.

Выходные данные:

Словарь правилен
или
Есть неправильные цепочки
имя_понятия1 ... имя_понятияN
   |___________________|______ 
   начала неправильных цепочек
и/или
Есть неопределенные понятия
имя_понятия1 ... имя понятияN
   |___________________|_______ 
   имена неопределенных понятий
(слова перечисляются в порядке включения в словарь.)

Пример ввода:

(( автокод язык_программирования 
	<используется для создания>
   операционная_система <и> транслятор) 
( язык_программирования <задается множеством правил 
	для написания> программ)
( операционная_система <комплекс> программа
   <управляющих решением задач на 
	имеющемся оборудовании>)
( транслятор <компилирующая> программа)
( программа <описание> алгоритм 
	<решения задачи на соответствующем языке>)
( алгоритм <точно определенное правило действий>)
)

Уточнения:

Пример теста:

(( а-к яп <используется для создания> ос <и> сп)
( яп <задается множеством правил для написания> пр)
( ос <комплекс> пр <управляющих решением 
	задач на имеющемся оборудовании>)
( сп <компилирующая> пр)
( пр <описание> алг <решения задачи на 
	соответствующем языке>)
( алг <точно определенное правило действий>)
)

    '(( а-к яп ос сп) ( яп пр) ( ос пр) ( сп пр) ( пр алг) ( алг ))

;;=== Лексикон****) - проверка корректности ==
;; Предполагается, что из теста уже 
;; отфильтрованы строки,
;; т.к. они не влияют на логику анализа корректности 

(DEFUN NAMES (VAC) (MAPCAR 'CAR VAC))
;; определяемые имена - список левых частей

(DEFUN WORDS (VAC) (COND
;; используемые имена - список правых частей
   ((NULL VAC) NIL)
  (T (UNION (CDAR VAC) (WORDS (CDR VAC))))
))
(DEFUN UNDEF (VAC) (SET-DIFFERENCE (WORDS VAC)
   (NAMES VAC)))
;; неопределенные имена - список висячих ссылок
(DEFUN CIRCLE (V)
;; проверка термина на явный цикл
   (COND ((NULL (CDR V)) NIL)

      ((MEMBER (CAR V) (CDR V)) (CAR V))
      (T NIL)
   ))

(DEFUN CIRC-V (VAC) (MAPCAR 'CIRCLE VAC))
;; список явных циклов с NIL-ами на нециклах

(DEFUN MASKA (ARG XXX) (COND (XXX NIL) (T ARG)))
;; ВЫБОР, ЕСЛИ NIL

(DEFUN DEL-CIR (AL XL) (DELETE NIL
   (MAPCAR 'MASKA AL XL)))
;; стирание непомеченных определений, т.е. циклов

(DEFUN SKOBKI (LL) (COND((NULL LL)NIL)
      ((NULL (CAR LL)) (SKOBKI (CDR LL)) )
      ((ATOM (CAR LL))(CONS(CAR LL)
         (SKOBKI(CDR LL))) )
     (T (UNION (CAR LL) (SKOBKI (CDR LL)) ))
   ))
;; раскрыть скобки на один уровень

(DEFUN ONESTP (VC)(SETQ VAC VC)
;; однократная постановка всего словаря

   (MAPCAR '(LAMBDA (X) (CONS (CAR X)
         (SKOBKI (SUBLIS VAC (CDR X)))
      )) VC ))

  (DEFUN CLEAN-S (LINE XL)
(COND ((NULL XL) LINE)
   (T (CLEAN-S (DELETE (CAR XL) LINE)(CDR XL) ))
))

(DEFUN CLEAN-U (VC XL) (SETQ WL XL)

;; стирание заданного списка слов => висячих ссылок

(MAPCAR '(LAMBDA (XX) (SETQ X XX)
         (CONS (CAR X)
            (CLEAN-S (CDR X) WL)
   )) VC ))

  (DEFUN CVR (VAC)(DELETE NIL (CVR-D
         (DEL-CIR VAC (CIRC-V VAC))
   (DELETE NIL(UNION (CIRC-V VAC) NIL)))))
;; список всех циклов полного словаря - без
;; висячих ссылок

(DEFUN CVR-D (VC CCL)
   (PROG (VAC CL CV DCV CLEANV)
(SETQ VAC (CLEAN-U VC CCL))
(SETQ CL CCL)

;; пополнение списка циклов со второго шага
LAB (COND ((WORDS VAC)
   (SETQ CV (CIRC-V VAC))
   (SETQ DCV (DELETE NIL CV))
   (SETQ CLEANV (CLEAN-U (DEL-CIR VAC CV) DCV))
     (SETQ VAC (ONESTP CLEANV))
     (SETQ CL (APPEND DCV CL))
(GO LAB)
   ))
(RETURN CL)
))

(DEFUN VAC-OK (VAC) (PROG (VC UL CL)
;; ПРОВЕРКА СЛОВАРЯ НА КОРРЕКТНОСТЬ
   (SETQ VC VAC)
   (SETQ UL (UNDEF VC))
   (SETQ CL (CVR (CLEAN-U VAC UL)))

(COND ((EQ UL CL) (RETURN(PRINT 'OK)) )
      ; = лишь если пусты <> корректность словаря
   ( CL (PRINT (LIST 'CIRCLES CL))) )

(COND (UL (RETURN (PRINT (LIST 'UNDEFINED UL))) )
   (T (RETURN (LIST 'CIRCLE CL))) )
))

*) Символ ";" - начало комментария.

**) На Lisp 1.5 это определение выглядит изящнее, не требует встроенной функции FUNCALL, при отладке примеров на Clisp-е [7]:

(DEFUN map-el (fn xl)
   (COND
      (xl (CONS  (fn (CAR xl) )
         ; применяем первый аргумент как функцию
         ; к первому элементу второго аргумента
      (map-el fn (CDR xl) )
) ) ) )

***) Эта задача была предложена участникам Открытой Всесибирской студенческой олимпиады в 2000 году и оказалась в числе никем не решенных. Многих смутило отсутствие численных ограничений на допустимые данные. При решении задач на Паскале и Си такие ограничения обычно подсказывают выбор структур данных, поэтому отсутствие ограничений было воспринято как риск. Немногочисленные попытки решить задачу привели к отбраковке на минимальных тестах, вызванной тем, что программы не допускали пустой словарь или словарь, выглядящий как перечень терминов без определений. (Впрочем, возможно, это ошибка разработчика тестов. Видимо, первыми должны располагаться тесты на наиболее типичные, естественные случаи.)

****) Решение этой задачи может быть сведено к задаче <Проверка ацикличности графа>.