Haskell中的Catamorphism和树遍历

Question

我很不耐烦,期待理解与这个SO问题有关的 catamorphism :)

我只练习了Real World Haskell教程的开头.所以,也许我现在要问的方式太多了,如果是这样的话,那就告诉我应该学习的概念.

下面,我引用了维基百科代码样本的catamorphism.

我想知道你对下面的foldTree的看法,这是一种遍历树的方法,与其他SO问题和答案相比,还涉及遍历Tree n-ary树遍历.(独立于二进制或不二进制,我认为下面的catamorphism可以编写,以便管理n-ary树)

我评论了我的理解,如果你能纠正我,并且澄清一些事情,我会很高兴.

{-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是catamorphism的基本属性.它说,要f在某些递归数据结构上计算某些函数,它就足以f获得其直接子元素的值.

Haskell是一种非常独特的语言,因为我们可以抽象地形式化catamorphism的概念.让我们为树中的单个节点创建一个数据类型,并对其子节点进行参数化:

data TreeNode a child
    = Leaf a
    | Branch child child

看看我们在那里做了什么？我们刚刚用我们选择的类型替换了递归子项.这样我们可以在折叠时将子树的总和放在那里.

现在为真正神奇的事情.我将在pseudohaskell中编写这个 - 在真正的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类型.这给了我们定义一个catamorphism所需要的东西.

我们来定义:

type IntTree = Mu IntNode

我说,catamorphism的基本属性是,为了计算一些函数f,它就足以得到f它的直接子元素的值.让我们调用我们试图计算的东西的类型r,以及数据结构node(IntNode可能是这种情况的实例化).因此,要r在特定节点上进行计算,我们需要将其子节点替换为rs 的节点.这个计算有类型node r -> r.所以一个catamorphism说如果我们有这些计算之一,那么我们可以计算r整个递归结构(记住递归在这里明确表示Mu):

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

以我们的例子为例,这看起来像:

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

重申一下,如果我们可以r为其子节点创建带有s 的节点并计算一个节点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 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)

我没时间了.我知道真的非常抽象,但我希望它至少能给你一个新的观点来帮助你学习.祝好运!