Не совсем уверен, что вы просите. Но да, вы кормите TreeAlgebra до foldTree, соответствующих вычислениям, которые вы хотите выполнить на дереве. Например, чтобы просуммировать все элементы в дереве Int с вы могли бы использовать эту алгебру:
sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
, branch = (+) }
значит, чтобы получить сумму листа, применять id (ничего не делать) до значения в листе , Чтобы получить сумму филиала, добавьте суммы каждого из детей.
Тот факт, что мы можем сказать (+) для ответвления вместо, скажем, \x y -> sumTree x + sumTree y, является основным свойством катаморфизма. В нем говорится, что для вычисления некоторой функции f для некоторой рекурсивной структуры данных достаточно иметь значения для ее непосредственных детей.
Haskell - довольно уникальный язык, позволяющий абстрактно абстрагировать идею катаморфизма. Давайте создадим тип данных для одного узла в вашем дереве, параметризованный над его дочерними элементами:
data TreeNode a child
= Leaf a
| Branch child child
Посмотрите, что мы там делали? Мы просто заменили рекурсивных детей типом нашего выбора. Это так, что мы можем поместить суммы поддеревьев там, когда мы складываемся.
Теперь для действительно волшебной штуки. Я собираюсь написать это в псевдохаскелле - писать его в реальном Haskell возможно, но мы должны добавить некоторые аннотации, чтобы помочь typechecker, который может быть довольно запутанным. Мы берем «фиксированную точку» параметризованного типа данных, т. Е. Создаем тип данных T, такой как T = TreeNode a T. Они называют этого оператора Mu.
type Mu f = f (Mu f)
Обращайте внимание здесь. Аргументом к Mu не является тип, например Int или Foo -> Bar. Это тип конструктор как Maybe или TreeNode Int - аргумент Mu сам принимает аргумент. (Возможность абстрагирования над конструкторами типов является одной из вещей, которая делает систему типа Haskell действительно выделяющейся в ее выразительной силе).
Таким образом, тип Mu f определяется как взятие f и заполнение его параметром типа Mu f. Я собираюсь определить синоним, чтобы уменьшить часть шума:
type IntNode = TreeNode Int
Расширение Mu IntNode, мы получаем:
Mu IntNode = IntNode (Mu IntNode)
= Leaf Int | Branch (Mu IntNode) (Mu IntNode)
Вы видите, как Mu IntNode эквивалентно вашей Tree Int? Мы просто разорвали рекурсивную структуру, а затем использовали Mu, чтобы снова собрать ее обратно. Это дает нам преимущество, что мы можем говорить обо всех типах Mu сразу. Это дает нам то, что нам нужно определить для катаморфизма.
Давайте определим:
type IntTree = Mu IntNode
Я сказал, что существенное свойство катаморфизма является то, что для вычисления некоторой функции f, достаточно иметь значение f для своих непосредственных детей. Давайте назовем тип вещи, которую мы пытаемся вычислить r, и структура данных node (IntNode была бы возможной инстанцировкой этого). Поэтому, чтобы вычислить r на конкретном узле, нам нужен узел со своими детьми, замененными их r. Этот расчет имеет тип node r -> r. Так катаморфизм говорит, что если у нас есть один из этих расчетов, то мы можем вычислить r для всей рекурсивной структуры (помните рекурсии обозначаются здесь явно с Mu):
cata :: (node r -> r) -> Mu node -> r
Созданием этого бетона для нашего примера, это выглядит следующим образом:
cata :: (IntNode r -> r) -> IntTree -> r
Подтвердив, если мы можем взять узел с r с для своих детей и вычислить r, то мы можем вычислить r для всего дерева ,
Для того, чтобы действительно вычислить это, нам нужно node быть Functor. То есть нам нужно иметь возможность сопоставлять произвольную функцию по дочерним элементам узла.
fmap :: (a -> b) -> node a -> node b
Это можно сделать прямо на IntNode.
fmap f (Leaf x) = Leaf x -- has no children, so stays the same
fmap f (Branch l r) = Branch (f l) (f r) -- apply function to each child
Теперь наконец, мы можем дать определение для cata (Functor node ограничения просто говорит, что node имеет подходящую fmap):
cata :: (Functor node) => (node r -> r) -> Mu node -> r
cata f t = f (fmap (cata f) t)
Я использовал имя параметра t для мнемоники значение «дерева». Это абстрактное, плотное определение, но это действительно очень просто. В нем говорится: рекурсивно выполнить cata f - расчет, который мы делаем над деревом - на каждом из t детей (которые сами являются Mu node), чтобы получить node r, а затем передать этот результат f для вычисления результата для t ,
Привязывая это к началу, алгебра, которую вы определяете, по существу является способом определения функции node r -> r. Действительно, учитывая TreeAlgebra, мы можем легко получить фолд функцию:
foldFunction :: TreeAlgebra a r -> (TreeNode a r -> r)
foldFunction alg (Leaf a) = leaf alg a
foldFunction alg (Branch l r) = branch alg l r
Таким образом, дерево катаморфизм может быть определена в терминах нашего общего одного следующим образом:
type Tree a = Mu (TreeNode a)
treeCata :: TreeAlgebra a r -> (Tree a -> r)
treeCata alg = cata (foldFunction alg)
Я вне времени , Я знаю, что очень быстро стал очень абстрактным, но я надеюсь, что он по крайней мере дал вам новую точку зрения, чтобы помочь вам в обучении. Удачи!
Несвязанное примечание: метка «catamporphisms» имеет орфографическую ошибку; он имеет дополнительный «p». По-видимому, я недостаточно крут, чтобы редактировать это, но это создало бы новый тег. (Иисус плакал.) –
@ Деррик Тюрк: с этим тегом всего три вопроса. Было бы не слишком сложно их отталкивать. – fuz
@FUZxxl: Кажется, вам нужна репутация 1500 для создания новых тегов, и в то время «катаморфизм» еще не существовал. – ephemient