Назад

Парадигмы программирования

Практика

Список семестровых заданий («лабораторных работ») по Лиспу

  1. Списочные структуры. Реализовать функции LENGTH1, REVERSE1, APPEND1, LIST1, определенные следующим образом:
    • функция LENGTH1 возвращает длину списка:
      > (LENGTH1 '(A B C))
      3
    • функция LIST1 объединяет два аргумента в список:
      > (LIST1 'A 'B)
      (A B)
    • функция APPEND1 объединяет два списка:
      > (APPEND1 '(A B) '(C D))
      (A B C D)
    • функция REVERSE1 «переворачивает» список:
      > (REVERSE1 '(A B C))
      (C B A)

  2. Предикаты сравнения. Объяснить разницу между предикатами сравнения EQ, EQL, =, EQUAL, EQUALP. Привести примеры S-выражений A и B таких, что
    1. истинно (EQ A B);
    2. истинно (EQL A B), но ложно (EQ A B);
    3. истинно (= A B), но ложно (EQL A B);
    4. истинно (EQUAL A B), но ложно (EQL A B);
    5. истинно (EQUALP A B), но ложно (EQUAL A B);
    6. ложно (EQUALP A B).

  3. Ассоциативный список. Реализовать функцию ASSOC1, которая определяет, есть ли в данном списке точечных пар пара с первым элементом, равным данному атому, и возвращающую второй элемент этой пары, если такая пара есть, и NIL, если такой пары нет.
    Пример:
    > (ASSOC1 '((A . 1) (B . 2) (C . 3)) 'B)
    2
    > (ASSOC1 '((A . 1) (B . 2) (C . 3)) 'D)
    NIL
  4. Сортировка. Дан список из нескольких чисел. Реализовать функцию сортировки этого списка по возрастанию любым способом.
    Пример:
    > (SORT '(1 5 2 4 3))
    (1 2 3 4 5)
  5. Слияние. Реализовать функцию, «сливающую» два списка чисел, отсортированных по возрастанию, в один список, отсортированный по возрастанию.
    Пример:
    > (MERGE '(1 3 5) '(2 4))
    (1 2 3 4 5)
  6. Суперпозиция CAR и CDR. Реализовать функцию MAKE-CAR-CDR, которая принимает три аргумента:
    • S — произвольное S-выражение
    • X — произвольный атом
    • Q — произвольный атом
    и возвращает S-выражение из атомов CAR, CDR и Q, такое, что если бы значением атома Q было S, то результатом вычисления этого выражения был бы атом X. Проще говоря, функция должна показывать, как при помощи суперпозиции вызовов CAR и CDR «выделить» X из выражения S, обозначенного как Q.
    Пример:
    > (MAKE-CAR-CDR '(A X B) 'X 'Q)
    (CAR (CDR Q))
  7. Перестановки. Вывести все возможные перестановки элементов данного списка в произвольном порядке. В приведенном ниже примере перестановки выведены на экран, а NIL — результат функции. Ваша функция может работать иначе.
    Пример:
    > (PERMUT '(1 2 3))
    (1 2 3)
    (1 3 2)
    (2 1 3)
    (2 3 1)
    (3 1 2)
    (3 2 1)
    NIL
  8. Индивидуальные задания будут выданы на занятиях после сдачи всех предыдущих заданий.