Материалы
Мы прошли:
- всяческие диапазоны
- "list comprehensions"
- уточнение понятия ленивости
и посмотрели на реализацию быстрой сортировки:
Это очень близко соответствует второй главе прекрасного учебника Learn You A Haskell for great good (LYAH)
Про природу ленивости и самую суть функционального программирования
Пусть у нас есть две функции:
И мы хотим посчитать значение выражения incr (ones 3).
Хаскель смотрит на то, какие у нас есть правила, и ищет места, куда их можно приложить. Из описанных сейчас правил к этому выражению применимо только одно: ones n = 1 : ones (n - 1). Соответственно, хаскель просто выполняет замену, описанную этим правилом: incr (ones 3) ---[ n = 3 ]---> incr (1 : ones (3 - 1)).
Теперь у хаскеля есть много мест, которые подходят под известные ему правила. Он может в этом выражении найти incr (x:xs) или ones n или посчитать 3 - 1. То, какое решение принимает язык программирования и определяет его класс: традиционные языки (вроде питона) в этом месте решат первм делом вычислить самое левое самое вложенное выражение (аргумент той функции, которая ему нужна), то есть 3 - 1, а ленивые языки в этом месте выбирают самое левое самое внешнее выражение, то есть incr (x:xs). (Порядок слева-направо в выражениях определяется по левому краю выражения. Глубина вложенности по количеству незакрытых скобок перед ним).
То есть: incr (1 : ones (3 - 1)) ---[ x = 1; xs = ones (3 - 1) ]---> (1 + 1) : incr (ones (3 - 1)).
Здесь самое левое выражение 1 + 1: (1 + 1) : incr (ones (3 - 1)) ---> 2 : incr (ones (3 - 1)).
На самом деле, : исполняться не будет, и хаскель бы тут остановился, но где-то снаружи от нас есть функция, которая хочет выводить символы на экран, и она рано или поздно съест 2: и оставит нас с incr (ones (3 - 1)).
Теперь единственный подходящий шаблон 3 - 1: incr (ones (3 - 1)) ---> incr (ones 2).
А это уже очень знакомый нам случай:
incr (ones 2) ---[ n = 2 ]---> incr (1 : ones (1 - 1)).
incr (1 : ones (2 - 1)) ---[ x = 1; xs = ones (2 - 1) ]---> (1 + 1) : incr (ones (2 - 1)).
(1 + 1) : incr (ones (2 - 1)) ---> 2 : incr (ones (2 - 1))
- вытянули 2 на экран
incr (ones (2 - 1)) ---> incr (ones 1).
incr (ones 1) ---[ n = 1 ]---> incr (1 : ones (1 - 1)).
incr (1 : ones (1 - 1)) ---[ x = 1; xs = ones (1 - 1) ]---> (1 + 1) : incr (ones (1 - 1)).
(1 + 1) : incr (ones (1 - 1)) ---> 2 : incr (ones (1 - 1))
- вытянули 2 на экран
incr (ones (1 - 1)) ---> incr (ones 0).
Теперь единственный подходящий шаблон: ones 0 = [].
incr (ones 0) ---> incr [] ---> []
В итоге мы получили на экране список из [2,2,2].
Суть функционального программирования состоит в том, что _весь_ ход выполнения программы раскладывается именно вот так на преобразования таких выражений.