Catamorphism i drzewa przejeżdżające w Haskell

Question

jestem niecierpliwy, oczekując zrozumienia catamorphism related to this SO question :)

mam praktykowane tylko początek poradnika Real World Haskell. Więc, może teraz spytam o zbyt wiele, jeśli tak było, po prostu powiedz mi pojęcia, których powinienem się nauczyć.

Poniżej zacytuję numer wikipedia code sample for catamorphism.

Chciałbym poznać twoją opinię na temat foldTree poniżej, sposób przemierzania drzewa, w porównaniu z tym innym pytaniem i odpowiedzią WR, również zajmującym się przemierzaniem drzewa n-ary tree traversal. (Niezależnie od binarnego lub nie, myślę, że poniższy katamorfizm można zapisać tak, by zarządzał n-drzewem)

Dodałem komentarz, co rozumiem, i cieszę się, że mógłbyś poprawić mnie i wyjaśnić pewne rzeczy .

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

w tym momencie mam wiele trudności, wydaje mi się domyślać, że liść morfizmem zostaną zastosowane do każdej Liścia Ale tak jak użyć tego kodu za prawdziwe, foldTree musi być karmione określona TreeAlgebra , a TreeAlgebra, która ma zdefiniowany liść morfizmu, aby coś zrobić?
ale w tym przypadku w kodzie foldTree oczekiwałbym {f = leaf} i nie przeciwnie

Wszelkie wyjaśnienia od ciebie byłyby naprawdę mile widziane.

Answer 1

Niezupełnie pewne, o co prosisz. Ale tak, karmisz TreeAlgebra do foldTree odpowiadającą obliczeniu, które chcesz wykonać na drzewie. Na przykład, aby suma wszystkich elementów w drzewie z Int s byłoby użyć tej algebry:

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

co oznacza, aby uzyskać sumę liściu, stosuje id (zrobić nic) do wartości w liściach . Aby uzyskać sumę oddziału, dodaj sumy sumy każdego z dzieci.

Fakt, że możemy powiedzieć (+) dla oddziału zamiast, powiedzmy, \x y -> sumTree x + sumTree y jest podstawową własnością katamorfizmu. Mówi ona, że ​​aby obliczyć jakąś funkcję f na pewnej rekurencyjnej strukturze danych, wystarczy mieć wartości f dla jej bezpośrednich potomków.

Haskell jest dość wyjątkowym językiem, ponieważ możemy sformalizować abstrakcyjnie ideę katamorfizmu. Zróbmy typ danych dla pojedynczego węzła w twoim drzewie, sparametryzowane na jego elementach potomnych:

data TreeNode a child 
    = Leaf a 
    | Branch child child 

Zobacz, co tam robiliśmy? Właśnie zastąpiliśmy rekursywne dzieci rodzajem naszego wyboru. Jest tak, abyśmy mogli składać sumy poddreków podczas składania.

Teraz za naprawdę magiczną rzecz. Zamierzam to napisać w pseudohaskell - napisanie tego w prawdziwym języku Haskella jest możliwe, ale musimy dodać kilka adnotacji, aby pomóc typecheckerowi, który może być trochę zagmatwany. Przyjmujemy "stały punkt" sparametryzowanego typu danych - czyli konstruujemy typ danych T taki, że T = TreeNode a T. Nazywają tego operatora Mu.

type Mu f = f (Mu f) 

Sprawdź dokładnie tutaj. Argument Mu nie jest typem, takim jak Int lub . Jest to typ konstruktora jak Maybe lub TreeNode Int - sam argument przyjmuje, że sam. (Możliwość abstrahowania nad konstruktorami typów jest jedną z rzeczy, która sprawia, że ​​system typu Haskella naprawdę wyróżnia się w swojej ekspresyjnej sile).

Tak więc typ Mu f jest zdefiniowany jako przyjmujący f i wypełniający jego parametr typu sam z Mu f. Zamierzam zdefiniować synonim zmniejszyć niektóre hałasu:

type IntNode = TreeNode Int 

Rozszerzanie Mu IntNode, otrzymujemy:

Mu IntNode = IntNode (Mu IntNode) 
      = Leaf Int | Branch (Mu IntNode) (Mu IntNode) 

Czy widzisz jak Mu IntNode jest równoważna swojej Tree Int? Właśnie rozerwaliśmy strukturę rekursywną, a następnie użyliśmy Mu, aby ponownie ją złożyć. Daje nam to przewagę, że możemy mówić o wszystkich typach Mu naraz. Daje nam to, czego potrzebujemy, aby zdefiniować katamorfizm.

Zdefiniujmy:

type IntTree = Mu IntNode 

powiedziałem zasadniczą właściwością catamorphism jest to, że aby obliczyć pewną funkcję f, wystarczy mieć wartości f dla jego bezpośrednich dzieci. Nazwijmy typ rzeczy, którą próbujemy obliczyć r, a struktura danych może być możliwą instancją tego). Aby obliczyć r na określonym węźle, potrzebujemy węzła z jego dziećmi zastąpionymi ich numerami r. To obliczenie ma typ node r -> r. Więc catamorphism mówi, że jeśli mamy jedną z tych obliczeń, to możemy obliczyć r dla całego rekurencyjnego struktury (pamiętaj rekursji oznaczamy wyraźnie tutaj z Mu):

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

Making ten beton na naszym przykładzie, to wygląda:

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

przekształcenie, czy możemy wziąć węzeł z r s dla swoich dzieci i obliczyć r, to możemy obliczyć r dla całego drzewa.

Aby to obliczyć, potrzebujemy node, aby być Functor - to znaczy, że musimy umieć odwzorować dowolną funkcję na dzieci węzła.

fmap :: (a -> b) -> node a -> node b 

Można to zrobić bezpośrednio dla 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 

Teraz wreszcie możemy podać definicję dla cata (the Functor node ograniczenie tylko mówi, że node posiada odpowiednią fmap):

cata :: (Functor node) => (node r -> r) -> Mu node -> r 
cata f t = f (fmap (cata f) t) 

użyłem nazwę parametru t dla mnemoników wartość "drzewa". Jest to abstrakcyjna, gęsta definicja, ale jest naprawdę bardzo prosta. Mówi: rekurencyjnie wykonuj cata f - obliczenia, które robimy na drzewie - na każdym z dzieci t (które same są Mu node s), aby uzyskać node r, a następnie przekazać ten wynik do f obliczyć wynik dla samej siebie t .

Wiązanie z powrotem do początku definiowanej algebry jest w istocie sposobem na zdefiniowanie funkcji node r -> r. Rzeczywiście, biorąc pod uwagę TreeAlgebra, możemy łatwo uzyskać krotny funkcję:

foldFunction :: TreeAlgebra a r -> (TreeNode a r -> r) 
foldFunction alg (Leaf a) = leaf alg a 
foldFunction alg (Branch l r) = branch alg l r 

Zatem catamorphism drzewa mogą być definiowane w kategoriach naszego generycznego jednego następująco:

type Tree a = Mu (TreeNode a) 

treeCata :: TreeAlgebra a r -> (Tree a -> r) 
treeCata alg = cata (foldFunction alg) 

jestem poza czasem . Wiem, że to naprawdę bardzo abstrakcyjne, ale mam nadzieję, że przynajmniej dał ci nowy punkt widzenia, aby pomóc ci w nauce. Powodzenia!

Answer 2

Myślę, że zadawałeś pytanie dotyczące {}. Jest wcześniejsze pytanie z dobrą dyskusją {}. Te są nazywane Haskell's record syntax. Innym pytaniem jest, dlaczego konstruować algebrę. Jest to typowy paradygmat funkcji, w którym generalizujesz dane jako funkcje.

Najbardziej znanym przykładem jest Church's construction of the Naturals, gdzie f = + 1 i z = 0, 0 = z, 1 = f z, 2 = f (f z), 3 = f (f (f z)), etc ...

Co widzisz jest zasadniczo taki sam pomysł jest nakładany na drzewo. Wykonaj przykład kościoła, a drzewo kliknie.