Catamorfismo e travessia de árvores em Haskell
Estou impaciente, ansioso para entender o catamorfismorelacionado a esta pergunta SO :)
Eu apenas pratiquei o início do tutorial Haskell do mundo real. Então, talvez eu vá pedir demais agora, se for o caso, apenas me diga os conceitos que devo aprender.
Abaixo, cito oamostra de código da wikipedia para catamorfismo.
Gostaria de saber sua opinião sobre o foldTree abaixo, uma maneira de percorrer uma árvore, em comparação com outras perguntas e respostas do SO, também lidando com a travessia de uma árvoretravessia de árvore n-ária. (independentemente de ser binário ou não, acho que o catamorfismo abaixo pode ser escrito para gerenciar a árvore n-ária)
Coloco em comentário o que entendo e fico feliz se você puder me corrigir e esclarecer algumas coisas.
{-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)
Neste ponto, estou tendo muitas dificuldades, parece que acho que a folha de morfismo será aplicada a qualquer folha. Mas, para usar esse código de maneira real, o foldTree precisa ser alimentado com um TreeAlgebra definido, um TreeAlgebra que possui uma folha de morfismo definida para fazer alguma coisa?
mas, neste caso, no código foldTree, eu esperaria {f = leaf} e não o contrário
Qualquer esclarecimento seu seria muito bem-vindo.