Катаморфизм и обход деревьев в Haskell

Question

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

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

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

Я хотел бы узнать ваше мнение о Foldtree ниже, способ проходить дерево, по сравнению с этим другим вопросом и ответом, также имея дело с прохождением дерева N-ARY Tree Traversal. Отказ (независимо от того, чтобы быть двоичным или нет, я думаю, что катаморфизм ниже можно записать, чтобы управлять N-ARY Tree)

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

{-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)

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

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

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

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

Теперь для действительно волшебной вещи. Я собираюсь написать это в псевдохаскелле - написание его в настоящем 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 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)), и т.д...

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