Материалы

Мы прошли:

• всяческие диапазоны
• "list comprehensions"
• уточнение понятия ленивости

и посмотрели на реализацию быстрой сортировки:

   1 qsort [] = []
   2 qsort (pivot:rest) =
   3   qsort [smaller | smaller <- rest, smaller < pivot]
   4   ++
   5   [pivot]
   6   ++
   7   qsort [greater | greater <- rest, greater >= pivot]

Это очень близко соответствует второй главе прекрасного учебника Learn You A Haskell for great good (LYAH)

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

Пусть у нас есть две функции:

   1 ones 0 = []
   2 ones n = 1 : ones (n - 1)
   3 
   4 incr [] = []
   5 incr (x:xs) = (x + 1) : incr xs

И мы хотим посчитать значение выражения 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].

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