Я нашел такой удивительный пример кода на Хаскеле, что мне захотелось о нем написать здесь. Вот эти две-три строчки кода:
В Xаскеле есть то, что называется typeclass.
По сути это интерфейс, который может реализовать ваш datatype, и это позволит
использовать его в различных новых функциях.
Пример typeclass - это Eq, для принадлежности к которому нужно определить функцию (==).
Другой - Ord, для которого нужно определить оператор сравнения.
Это, например, требование для элементов списка-аргумента функции sort:
Итак, код выше - дефолтная реализация функции foldr для typeclass'а Foldable через функцию foldMap.
Иными словами, чтобы принадлежать классу Foldable, можно просто реализовать foldMap. Foldable - класс
типов, для которых определена свертка - просто применение бинарного оператора для получения одного результата.
Пример левой свертки на Python:
Разумно полагать, что реализации foldr (правой свертки) хватает для принадлежности к классу Foldable.
Однако как реализация странной функции foldMap позволяет реализовать foldr, а значит, принадлежать к этому классу?
На самом деле, реализовать можно только одну из этих функций, а реализация по умолчанию второй позволит определить принадлежность к классу.
Взглянем на сигнатуру функции foldMap (как я сказал, foldMap имеет дефолтную реализацию через foldr):
В `foldMap :: Monoid m => (a -> m) -> t a -> m` Monoid m означает что тип m принадлежит классу Monoid.
Далее определяется функция с сигнатурой `(a -> m) -> t a -> m`, что означает, что функция foldMap принимает
как аргумент функцию из типа а в тип m (a -> m) и Foldable, содержащий тип a, а возвращает объект типа m класса Monoid.
Иными словами, реализация этой функции должна,
имея способ преобразовать элементы Foldable в моноид - некую функцию f :: (a -> m), как-то свести весь Foldable к одному элементу.
Для простоты можно думать о Foldable как о списке или коллекции объектов, так как список, очевидно, является Foldable,
(хотя не все реализации Foldable содержат множество элементов, см. Maybe). Из курса общей алгебры мы знаем, что моноид - алгебраическая структура
со следующими правилами: замкнутость, ассоциативность, наличие нейтрального элемента. Примерно так и определен класс Monoid в Xаскеле:
mempty - нейтральный элемент, mappend - внутренний закон композиции моноида.
Примеры моноидов в Xаскеле: Sum a - буквально числа со сложением, [a] (списки) - тоже моноид с оператором конкатенации ++.
Таким образом мы можем просто скомпозировать все элементы нашего Foldable под действием функции (a -> m).
Возьмем двоичное дерево (каждая вершина либо пустая, либо имеет двух сыновей того же типа):
Вот пример реализации foldMap:
Мы рекурсивно применяем foldMap к левому и правому поддереву и композируем моноиды (функция f принимает вершину и возвращает моноид)
из левого поддерева, текущей вершины и правого поддерева. База рекурсии - пустая вершина, для которой возвращается нейтральный элемента моноида.
Таким образом, все дерево было скомпозировано в один элемент моноида.
Теперь мы готовы к тому, чтобы разобрать то, что меня так поразило - реализацию функции foldr.
Вот она еще раз:
Вся суть скрывается в функции Endo. Endo - тип класса Monoid.
Название объясняется тем, что Endo - моноид эндоморфизмов
(проще говоря, функций типа (a -> a), собственно, так же,
как и эндоморфизм является отображением из множества в (подмножество) себя).
Довольно просто понять,
что эндоморфизмы с оператором композиции функций является моноидом (замкнутость, ассоциативность тривиально доказываются, нейтральный - id, или f(x) = x).
На самом деле, Endo такая же функция, как и любая другая, только она принимает на вход функцию и возвращает объекты типа эндоморфизм,
который можно композировать с другими эндоморфизмами по закону этого моноида.
Такие функции называются конструкторами типов. В данном случае конструктор типа единственный и называется так же, как и сам тип.
Можно считать, что Endo - такая обертка вокруг функции (a -> a), которая сопровождается операцией композиции mappend и прочими функциями моноида.
На данном этапе нужно вспомнить одну из важнейших
концепций Хаскеля - currying (названо в честь того самого Хаскелла Карри). На самом деле, все функции в Хаскеле принимают один аргумент.
Функции типа (a -> a -> a) (как функция, которой мы делаем свертку, например)
сначала принимают в себя единственный аргумент и возвращают функцию, которая принимает "следующий",
отсюда такая, казалось бы, странная нотация.
Поэтому мы можем делать такое:
(функция + (да, это функция) применяется к 3 и возвращает функцию (a -> a),
которая прибавляет 3, а map применяет ее ко всем элементам списка).
Итак, вернемся к реализации foldr. Endo можно скомпозировать (. - это композиция) c бинарной функцией,
которой нам нужно сворачивать.
В результате действительно получается функция Endo, примененная к результату f в foldr. Какой же результат f?
Из-за currying f после применения к объекту типа a возвращает другую функцию (a -> a), из которой и конструируется наш эндоморфизм.
Таким образом, foldMap получает в себя `Endo . f` и из каждого элемента Foldable получает эндоморфизм. После этого foldMap композирует по закону моноида Endo все функции, то есть
получает одну-единственную функцию - композицию всех функцию типа (a -> a).
`appEndo` просто "извлекает" функцию из конструктора типа Endo. Потом эта функция-композиция всех функций применяется к начальному элементу z, что на выходе дает элемент типа a.
Почему это верная реализация правой свертки? Продемонстрируем на примере.
Допустим, есть список nums = [2, 4, 5] и бинарная функция (+). Мы делаем foldr (+) 0 nums.
Предположим, что этот foldr использует реализацию по умолчанию, тогда (+) применяется к 2 и получается (2+);
(2+) композируется с (4+), полученным таким же образом и скомпозированным с (5+). Такая функция, которая сначала прибавляет 5, потом 4, потом 2,
применяется к нулевому элементу и получается (2 + (4 + (5 + 0))), что явно выглядит как правая свертка.