Катаморфизм и пересечение деревьев в Хаскелле

Я нетерпелив, с нетерпением жду понимания катаморфизма связанного с этим вопросом SO:)

Я только практиковал начало учебника Real World Haskell. Итак, может быть, я сейчас попробую слишком много, если это так, просто скажите мне те понятия, которые я должен изучить.

Ниже я цитирую образец кода википедии для катаморфизма.

Я хотел бы узнать ваше мнение о foldTree ниже, способ пересечения дерева, по сравнению с этим другим вопросом и ответом SO, также касающийся пересечения дерева n-arry обход. (независимо от того, чтобы быть двоичным или нет, я думаю, что катаморфизм ниже может быть написан так, чтобы управлять n-арным деревом)

Я поставил комментарий, что я понимаю, и буду рад, если вы сможете исправить меня и прояснить некоторые вещи.

{-this is a binary tree definition-}
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

{-I dont understand the structure between{} 
however it defines two morphisms, leaf and branch 
leaf take an a and returns an r, branch takes two r and returns an r-} 
data TreeAlgebra a r = TreeAlgebra { leaf   :: a      -> r
                                   , branch :: r -> r -> r }

{- foldTree is a morphism that takes: a TreeAlgebra for Tree a with result r, a Tree a
and returns an r -} 
foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree [email protected](TreeAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldTree [email protected](TreeAlgebra {branch = g}) (Branch l r) = g (foldTree a l) (foldTree a r)

В этот момент у меня много трудностей, я, кажется, догадываюсь, что лист морфизма будет применяться к любому Листу Но чтобы использовать этот код для реального, foldTree нужно кормить определенной TreeAlgebra, TreeAlgebra, которая имеет определенный лист морфизма, чтобы что-то сделать?
но в этом случае в коде foldTree я ожидал бы {f = leaf}, а не наоборот

Любые разъяснения от вас были бы очень желанными.

Ответы

Ответ 1

Не совсем уверен, что вы просите. Но да, вы кормите TreeAlgebra до foldTree, соответствующего вычислению, которое вы хотите выполнить на дереве. Например, чтобы суммировать все элементы в дереве Int, вы использовали бы эту алгебру:

sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
                         , branch = (+) }

Что означает, чтобы получить сумму листа, примените id (ничего не делать) к значению в листе. Чтобы получить сумму ветки, добавьте суммы каждого из детей.

То, что мы можем сказать (+) для ветки вместо, скажем, \x y -> sumTree x + sumTree y, является существенным свойством катаморфизма. В нем говорится, что для вычисления некоторой функции f на некоторой рекурсивной структуре данных достаточно иметь значения f для ее непосредственных детей.

Haskell - довольно уникальный язык, в котором мы можем абстрактно абстрагировать идею катаморфизма. Позвольте создать тип данных для одного node в вашем дереве, параметризованного над его дочерними элементами:

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 для конкретного node, нам понадобится node, а его дети заменяются их r s. Это вычисление имеет тип node r -> r. Таким образом, катаморфизм говорит, что если у нас есть один из этих вычислений, то мы можем вычислить r для всей рекурсивной структуры (помните, что рекурсия явно обозначается здесь с помощью Mu):

cata :: (node r -> r) -> Mu node -> r

Сделав это конкретным для нашего примера, это выглядит так:

cata :: (IntNode r -> r) -> IntTree -> r

Повторяем, если мы можем взять node с r для своих дочерних элементов и вычислить r, тогда мы можем вычислить r для всего дерева.

Чтобы действительно вычислить это, нам нужно node быть Functor - то есть нам нужно иметь возможность сопоставить произвольную функцию над дочерними элементами node.

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 для мнемонического значения "tree". Это абстрактное, плотное определение, но это действительно очень просто. В нем говорится: рекурсивно выполнить cata f - вычисление, которое мы делаем над деревом - для каждого из T детей (которые сами являются Mu node s), чтобы получить node r, а затем передать этот результат в f вычислить результат для самого T.

Привязывая это к началу, алгебра, которую вы определяете, по существу является способом определения этой функции node r -> r. Действительно, при a 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)

У меня нет времени. Я знаю, что очень быстро стал очень абстрактным, но я надеюсь, что он по крайней мере дал вам новую точку зрения, чтобы помочь вам в обучении. Удачи!

Ответ 2

Думаю, вы задавали вопрос о {}. Существует более ранний вопрос с хорошим обсуждением {}. Они называются синтаксисом записи Haskell. Другой вопрос - зачем строить алгебру. Это типичная парадигма функции, в которой вы обобщаете данные как функции.

Самый известный пример Церковное строительство Naturals, где f = + 1 и z = 0, 0 = z 1 = f z 2 = f (f z) 3 = f (f (f z)) и т.д...

То, что вы видите, по существу та же самая идея применяется к дереву. Работайте над примером церкви, и дерево щелкнет.