Haskell中的ca态和树种

Question

我不耐烦，期待理解血统 与这个问题有关 :)

我只练习了现实世界的Haskell教程的开始。因此，也许我现在要问太多了，如果是这种情况，请告诉我我应该学到的概念。

下面，我引用了 维基百科代码样本.

我想知道您对下面的Foldtree的看法，与其他如此的问题和回答相比，遍历树的一种方式 n- ary树遍历. 。 （我认为下面的ca态性无关，无论是二进制，我都可以写成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)

在这一点上，我遇到了很多困难，我似乎猜想将形态叶子应用于任何叶子，但要将此代码用于真实，fordtree需要被喂食一个定义的treealgebra，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

看看我们在那里做了什么？我们只是用我们选择的类型代替了递归儿童。这样一来，我们就可以在折叠时将子树的总和放在那里。

现在是真正神奇的事情。我将在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 一次类型。这为我们提供了定义语态性所需的内容。

让我们定义：

type IntTree = Mu IntNode

我说血统的基本特性是计算一些功能 f, ，足以拥有的值 f 为了直接的孩子。让我们称我们要计算的东西的类型 r, 和数据结构 node (IntNode 可能是对此的实例化。因此要计算 r 在一个特定的节点上，我们需要及其孩子的节点替换为他们的孩子 rs。该计算具有类型 node r -> r. 。因此，一种ca态性说，如果我们有这些计算之一，那么我们可以计算 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

因此，可以根据我们的通用范围来定义树的ca态性，如下所示：

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))， ETC...

您所看到的本质上是应用于树上的相同想法。工作教堂的例子，树将点击。