Не совсем уверен, что вы спрашиваете. Но да, вы подаете TreeAlgebra в foldTree, соответствующее вычислению, которое вы хотите выполнить на дереве. Например, для суммирования всех элементов в дереве Int s вы должны использовать эту алгебру:
sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
, branch = (+) }
Что означает, чтобы получить сумму листа, примените id (ничего не делать) к значению в листе. Чтобы получить сумму ветви, сложите суммы каждого из детей.
Тот факт, что мы можем сказать (+) для ветви вместо, скажем, \x y -> sumTree x + sumTree y, является существенным свойством катаморфизма. В нем говорится, что для вычисления некоторой функции f на некоторой рекурсивной структуре данных достаточно иметь значения f для ее непосредственных потомков.
Haskell - довольно уникальный язык, в котором мы можем абстрактно формализовать идею катаморфизма. Давайте создадим тип данных для одного узла в вашем дереве, параметризованного по его дочерним элементам:
data TreeNode a child
= Leaf a
| Branch child child
Видишь, что мы там сделали? Мы просто заменили рекурсивных детей типом нашего выбора. Это сделано для того, чтобы мы могли поместить суммы поддеревьев во время свертывания.
Теперь по-настоящему волшебная вещь. Я собираюсь написать это на псевдохаскеле - написание на реальном Хаскеле возможно, но мы должны добавить некоторые аннотации, чтобы помочь проверке типов, что может быть немного запутанным. Мы берем «фиксированную точку» параметризованного типа данных, то есть создаем тип данных 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 s. Это вычисление имеет тип node r -> r. Таким образом, катаморфизм говорит, что если у нас есть одно из этих вычислений, то мы можем вычислить r для всей рекурсивной структуры (помните, что рекурсия здесь обозначается явно Mu):
cata :: (node r -> r) -> Mu node -> r
Делая этот бетон для нашего примера, это выглядит так:
cata :: (IntNode r -> r) -> IntTree -> r
Если мы можем взять узел с r s для его потомков и вычислить 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 s), чтобы получить 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)
У меня нет времени. Я знаю, что это стало действительно абстрактным и очень быстрым, но я надеюсь, что это, по крайней мере, дало вам новую точку зрения, чтобы помочь вашему обучению. Удачи!