asyan.org
добавить свой файл
1
Вопросы к зачету по курсу "Функциональное программирование". Зима 2011.

1. Что такое хвостовая рекурсия (tail recursion)? Что такое накапливающие параметры (аккумуляторы)? Пример их использования.

2. Смысл конструкции let или where. Пример использования.

3. Что имеется в виду, когда говорят, что в Haskell'е используется двумерный синтаксис? Опишите его правила. (В частности:

- как компилятор определяет, является ли очередная строчка продолжением оператора или началом нового оператора;

- как компилятор определяет, в каком месте кончаются блочные конструкции типа let).
4. (Задача из д.з.) Реализовать функцию reverse (обращение списка. Например, reverse [1, 2, 3] = [3, 2, 1]). Функция должна работать за линейное время.

5. Что делает функция map? Приведите ее определение (код) и пример использования.
6. Как в Haskell'e определить тип, параметризованый другим типом? Определите тип Tree (дерево), который для любого типа определяет дерево, содержащее значения этого типа.
7. Что такое лямбда выражение? Приведите пример его использования.

8*. Что такое замыкание (closure)?
9. Нелокальные переменные в определении функции. В какой момент они получают значения? Приведите какой-нибудь пример, когда это имеет значение.

10. Что такое карриннг (currying)? Что имеется в виду, когда говориться что все функции в Haskell имеют один параметр? Покажите, пожалуйста, это на примере какой-нибудь функции, у которой вроде бы два параметра - а на самом деле один.

11. Что такое section в Haskell'е? Приведите пример использования section.

12. Определите оператор . (суперпозицию функций). Приведите пример его использования.

13. Что делают функции foldr и foldl ? Чем они отличаются? Приведите определение (код) одной из этих функций (любой) и пример ее использования.
14. Как можно определить функцию, аналогичную foldr, для деревьев?
15. (Задача с занятий). С помощью катаморфизма для деревьев описать функцию, вычисляющую высоту данного дерева.
16. Перечислите конструкции, которые можно использовать в list comprehension (подсказка: их 3 шт.). Приведите примеры их использования.
17. (Задача из д.з.) Пусть мы представляем матрицы с помощью списков из списков. Описать функцию, которая для данного n возвращает такой список для матрицы n на n, у которой на главной и побочной диагоналях стоят 1, а все остальные элементы - нули.
Например, для n = 4 надо вернуть:
[[1, 0, 0, 1],

[0, 1, 1, 0],

[0, 1, 1, 0]

[1, 0, 0, 1]]
18. (Задача из д.з.) С помощью list comprehension решите задачу: «Для данного n создать список из всех троек (i, j, k) таких что 5*j + 3*j + 2*k == n. Желательно при этом не перебирать лишние варианты.»
19. Определите сортировку списка на основе алгоритма quicksort с помощью list comprehension.

20*. Что означает, что в Haskell'е реализован 'ленивый порядок вычислений' (lazy evaluation). Покажите на каком-нибудь примере, чем порядок вычислений при lazy evaluation отличается от обычного.
21. Что означает, что в Haskell умеет работать с бесконечными структурами данных? Приведите какой-нибудь пример, того, как на Haskell можно описать 'бесконечную структуру'.

22*. Какой прием программирования на Haskell'е называется 'завязывание узлов' (tying the knots)? Приведите пример.

23. Привести решение одной (любой из этих задач):
Используя "завязывание в узел", опишите бесконечный список из чисел, состоящих только из цифр 3,7,9. Числа должны идти в порядке возрастания.
или
Описать бесконечный список простых чисел, используя алгоритм «решето Эратосфена»
24. Какие конструкции и понятия из обычного (не функционального) программирования можно, в каком-то смысле, назвать аналогами ленивого выполнения в Haskell'е? Желательно привести какие-нибудь два примера.
25*. Какие конструкции и понятия из обычного (не функционального) программирования можно, в каком-то смысле, назвать аналогами ленивых списков в Haskell'е (и, в частности, бесконечных списков)?
26. Какие типы имеют функции length, zip, map, foldr ?

27. Приведите какой-нибудь пример описания класса в Haskell и какой-нибудь пример того, как объявить instance класса.
28. Пусть для какого-то типа (data) в Haskell я хочу определить свой оператор <. Что для этого надо сделать? Приведите пример.
29. Что в Haskelle означает слово deriving? Приведите пример его использования.

30*. Опишите (словами, не формально) как работает автоматический вывод типа функции (алгоритм Хиндли-Милнера) на примере какой-нибудь функции.
31. (Задача из д.з.) Пусть строчка содержит только символы ‘[‘, ‘]‘, ‘(‘ и ‘)‘. Опишите функцию, которая для данной строчки проверяет, что в ней находится правильная скобочная последовательность, и возвращает True или False. Например, для строки “[()[]]” надо вернуть True, а для строки ”([)]” – False. (Напоминание: строка в Хаскеле – это просто список символов).

32. Опишите функцию, которая составляет список из всех элементов дерева. Почему определение таких функций с помощью оператора ++ неэффективно? Определите функцию, так чтобы она работала за линейное время. Как можно записать эту функцию коротко, используя частичную параметризацию и композицию функций?
33. Опишите функцию nabory n k , которая возвращает список из всех наборов из k целых чисел, таких что каждое число не меньше 1 и не больше n.

34*. Что такое прием 'представление множеств с помощью функций'? Приведите какой-нибудь пример.
35. Опишите функцию alldif n k , которая возвращает список из всех наборов из k целых чисел, таких что каждое число не меньше 1 и не больше n и все числа разные.
36*. Что такое failure continuation? Приведите пример его использования
37*. Что такое continuation passing style? Приведите пример его использования.
38. Как написать функцию find (поиска по условию), так, чтобы она корректно сообщала о том, что ничего не найдено? Как в Haskell'e определен тип Maybe? Приведите решение с использованием Maybe и еще какой-нибудь вариант решения.

39. Что делает функция >>= для списков? Приведите какой-нибудь пример ее использования.
40. Используя только функцию >>= описать функцию, вычисляющую декартово произведение двух списков.
41. Приведите пример использования конструкции do для записи последовательности вычислений, любое из которых может завершиться неудачно, и которые надо выполнять до первой неудачи. (Задача про три поиска из д.з. или ваш собственный пример)

42. Определить функцию find так, чтобы она возвращала, кроме найденного элемента, еще и 'хвост' из еще не просмотренных элементов. Описать функцию, которая позволяет удобно комбинировать несколько вызовов таких функций. Приведите пример ее использования.
43*. Что такое монады в Haskell? (Можно не формально, как вы это понимаете). Приведите какие-нибудь два примера монад.
44. Для типа Expr, который мы разбирали на занятии, опишите функцию символьного дифференцирования diff.
45. Определите тип Expr с поддержкой конструкции let и определите для него функцию, вычисляющую значение выражения.
46. Как в чистом лямбда исчислении можно моделировать целые числа (числа Черча)? Приведите пример определения какой-нибудь арифметической операции (задача из д.з. про получение следующего числа или ваш собственный пример). Как по числу Черча получить соответствующее ему целое число?
47. Что такое бета-редукция? Какие сложные случаи надо учитывать при строгом определении бета-редукции?

48*. Что такое нормальная форма? Верно ли, что у любого лямбда выражения существует нормальная форма? Что такое нормальный и аппликативный порядки применения редукций? Каким замечательным свойством обладает нормальный порядок?
49* Что такое конфлюентность? Докажите, что из кофлюентности следует единственность нормальной формы. (тема будет на последнем занятии)
50* Что такое Y комбинатор? (тема будет на последнем занятии)
51* Изоморфизм Карри-Ховарда (тема будет на последнем занятии)

Замечания:

• Там где написано – 'приведите определение функции … (map, foldr и т.д.)’ – имеется в виду, что надо написать текст этой функции на Haskell.

• Обратите, пожалуйста, внимание - во время зачета никакими материалами пользоваться нельзя. На столе могут быть только чистые листы бумаги. Если у кого-то будут обнаружены какие-то распечатки, шпаргалки и т.д., то в этот день зачет для человека будет окончен :(

• Мелкие ошибки в синтаксисе не имеют значения, важно, чтобы смысл ответа был правильным. Если вы забыли имя какой-то встроенной функции, или какую-то особенность синтаксиса и т.д., вы можете во время зачета спросить это у меня.

• Для получения зачета достаточно решить все задачи (ответить на все вопросы), кроме двух. Те люди, которые решали задачи на дом, имеют право не отвечать еще на несколько вопросов/задач. Если человек решил 24 задачи, то он может не решать 3 задачи, если 32 – 4 задачи, если 40 – 4 задачи + еще можно пользоваться любыми материалами, если 48 – 5 задач + можно пользоваться любыми матриалами

• Задачи, помеченные * - это те, которые могут отвечать, люди, набравшие > 56 задач. Для остальных * ничего не значит. Те, кто решил 56 задач, могут сами выбрать любые 3 вопроса, помеченные * и рассказать мне про них. Я, может быть, дам задачу по какому-нибудь из этих вопросов. Те, кто решил >= 64 задачи, могут сами выбрать один любой вопрос и рассказать его, и тоже я, может быть, дам задачу.