Билеты по курсу «Теория функционального программирования. Язык Haskell»

  1. λ-исчисление и комбинаторная логика. История, цели, применение.
  2. Формальная система λ-исчисления. Подстановка. Редукция.
  3. Формальная система комбинаторной логики. Базовый комбинатор. Полный комбинаторный базис.
  4. Нормальная форма λ-выражения. Редукция. Редекс. Свёртка. Аппликация. Абстракция.
  5. Семантика λ-исчисления. Редукционные стратегии. АРС, НРС, их сравнение. Отличия НРС и ЛРС.
  6. Семантика λ-исчисления. Моделирование булевой логики. Эта-редукция оператора IF.
  7. Семантика λ-исчисления. Моделирование натуральной арифметики. Нумералы Чёрча.
  8. Семантика λ-исчисления. Моделирование списков. Моделирование произвольных структур данных.
  9. Семантика λ-исчисления. Моделирование итеративных процессов. Комбинатор неподвижной точки. Парадоксальный комбинатор Карри.
  10. Неподвижная точка. Теорема о неподвижной точке. Комбинатор неподвижной точки. Парадоксальный комбинатор Карри.
  11. Тождество. Канцелятор. Дубликатор. Коннектор. Композитор. Пермутатор. Базисы KS, KWB, IBCS, KBCS.
  12. Представление комбинаторов в полном базисе. Проверка представления комбинаторов в базисе. Выражение комбинаторов на языке λ-исчисления.
  13. Обоснование полноты комбинаторного базиса. Построение трансформации. Трансформация λ-выражений в базис KS.
  14. Обоснование полноты комбинаторного базиса. Построение трансформации. Трансформация λ-выражений в базис KBCS без выражения BC в KS.
  15. Обоснование полноты комбинаторного базиса. Перевод между базисами.
  16. Редукция на графах. ЛРС.
  17. Базовые типы в языке Haskell. Функции, определенные над базовыми типами.
  18. Списки. Селекторы и конструкторы. Примеры.
  19. Синтаксис определения функций в Haskell. Частичная реализация. Сопоставление с шаблоном. Типизация данных и функций. Примеры.
  20. Хвостовая рекурсия. Накапливающий параметр. Примеры.
  21. Функции высших порядков. Композиция функций. Примеры.
  22. Классы типов. Параметрический полиморфизм данных. Примеры.
  23. Классы типов. Наследование и реализация. Примеры.
  24. Классы типов Functor, Monad. Стратегии вычислений. Операция связывания. Примеры.
  25. Ввод-вывод, монада IO. Действия.
  26. Списки в Haskell. Функции модуля Prelude для обработки списков. map, fold*.
  27. Остаточные вычисления. Хвостовая рекурсия. CPS. Оператор $ модуля Prelude.
  28. Остаточные вычисления. Control.Monad.Cont.
  29. Теорема Чёрча-Россера. Доказательство.*

* Данный вопрос является необязательным; за ответ на него на экзамене ставится +1 балл

Haskell: 2010/Quests (last edited 2010-12-25 23:15:33 by host67-184-155-90)