Не совсем уверен, о чем вы спрашиваете. Но да, вы передаете TreeAlgebra в foldTree, соответствующее вычислению, которое вы хотите выполнить на дереве. Например, чтобы суммировать все элементы в дереве Ints, вы должны использовать эту алгебру:
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
Видите, что мы там делали? Мы просто заменили рекурсивные дочерние элементы выбранным нами типом. Это сделано для того, чтобы при сворачивании мы могли положить туда суммы поддеревьев.
Теперь по-настоящему волшебное дело. Я собираюсь написать это на псевдохаскеле - написать это на реальном Haskell возможно, но мы должны добавить некоторые аннотации, чтобы помочь контролеру типов, что может сбивать с толку. Мы берем «фиксированную точку» параметризованного типа данных, то есть конструируем такой тип данных 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
Повторюсь, если мы можем взять узел с rs для его дочерних элементов и вычислить 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)
У меня нет времени. Я знаю, что это стало действительно абстрактным, очень быстро, но я надеюсь, что это, по крайней мере, дало вам новую точку зрения, которая поможет вам в обучении. Удачи!
person
luqui
schedule
14.12.2010
