Катаморфизм и обход деревьев в Хаскеле

Question

Я с нетерпением жду понимания катаморфизма, связанного с этим ТАКИМ вопросом:)

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

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

Я хотел бы узнать ваше мнение о foldTree ниже, о способе обхода дерева, по сравнению с этим другим SO вопросом и ответом, а также с обходом обхода дерева n-ary tree. (независимо от того, является ли он двоичным или нет, я думаю, что приведенный ниже катаморфизм может быть записан так, чтобы управлять 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 a@(TreeAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldTree a@(TreeAlgebra {branch = g}) (Branch l r) = g (foldTree a l) (foldTree a r)

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

Любое разъяснение от вас будет очень приветствоваться.

Answer 1

Не совсем уверен, что вы спрашиваете. Но да, вы кормите 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

Видишь, что мы там сделали? Мы просто заменили рекурсивных детей типом нашего выбора. Это так, что мы можем поместить суммы поддеревьев туда, когда мы складываемся.

Теперь для действительно волшебной вещи. Я собираюсь написать это на псевдохаскеле - написание на реальном Хаскеле возможно, но мы должны добавить некоторые аннотации, чтобы помочь проверке типов, что может быть немного запутанным. Мы берем "фиксированную точку" параметризованного типа данных, то есть строим тип данных 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 в конкретном узле нам нужно заменить узел с его дочерними rs. Это вычисление имеет тип 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 nodes) чтобы получить 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)

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

Answer 2

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

Самым известным примером является построение церкви Природных, где f = + 1 а также z = 0, 0 = z,1 = f z,2 = f (f z),3 = f (f (f z)), так далее...

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