对于未标记的树，“展开”的正确定义是什么？ [英] What is the correct definition of `unfold` for an untagged tree?

问题描述

我一直在考虑如何实现相当于以下类型的展开：

I've been thinking in how to implement the equivalent of unfold for the following type:

data Tree a = Node (Tree a) (Tree a) | Leaf a | Nil

由于标准展开 for list返回值和下一个种子。对于这个数据类型，它没有意义，因为在到达叶节点之前没有值。这样，返回新的种子或停止一个价值才真正有意义。我使用这个定义：

It was not immediately obvious since the standard unfold for lists returns a value and the next seed. For this datatype, it doesn't make sense, since there is no "value" until you reach a leaf node. This way, it only really makes sense to return new seeds or stop with a value. I'm using this definition:

data Drive s a = Stop | Unit a | Branch s s deriving Show

unfold :: (t -> Drive t a) -> t -> Tree a
unfold fn x = case fn x of
    Branch a b -> Node (unfold fn a) (unfold fn b)
    Unit a     -> Leaf a
    Stop       -> Nil

main = print $ unfold go 5 where
    go 0 = Stop
    go 1 = Unit 1
    go n = Branch (n - 1) (n - 2)

虽然这似乎起作用，我不知道这是怎么应该是。所以这就是问题：正确的方法是什么？

While this seems to work, I'm not sure this is how it is supposed to be. So, that is the question: what is the correct way to do it?

推荐答案

如果您将数据类型视为固定点一个函子，那么你可以看到你的定义是清单案例的明智的泛化。

If you think of a datatype as the fixpoint of a functor then you can see that your definition is the sensible generalisation of the list case.

module Unfold where

这里我们从定义开始，一个函子的修正点 f 它是一层 f ，后跟一些更多的fixpoint：

Here we start by definition the fixpoint of a functor f: it's a layer of f followed by some more fixpoint:

newtype Fix f = InFix { outFix :: f (Fix f) }

为了使事情更清晰，对应于列表和树的函子的定义。它们具有与数据类型基本相同的形状，除了我们通过额外的参数替换递归调用。换句话说，它们描述了list / tree中的一层是什么样的，并且在可能的子结构 r 之间是通用的。

To make things slightly clearer, here are the definitions of the functors corresponding to lists and trees. They have basically the same shape as the datatypes except that we have replace the recursive calls by an extra parameter. In other words, they describe what one layer of list / tree looks like and are generic over the possible substructures r.

data ListF a r = LNil | LCons a r
data TreeF a r = TNil | TLeaf a | TBranch r r

列表和树分别是ListF和TreeF的固定点：

Lists and trees are then respectively the fixpoints of ListF and TreeF:

type List a = Fix (ListF a)
type Tree a = Fix (TreeF a)

无论如何，您现在可以对此fixpoint业务有更好的直觉，我们可以看到有一种通用的定义

Anyways, hopping you now have a better intuition about this fixpoint business, we can see that there is a generic way of defining an unfold function for these.

给定一个原始种子以及一个采用种子的功能，并构建一层 > f 其中递归结构是新的种子，我们可以构建一个整体结构：

Given an original seed as well as a function taking a seed and building one layer of f where the recursive structure are new seeds, we can build a whole structure:

unfoldFix :: Functor f => (s -> f s) -> s -> Fix f
unfoldFix node = go
  where go = InFix . fmap go . node

此定义专门针对通常的展开列表或您对树的定义。换句话说：你的定义确实是正确的。

This definition specialises to the usual unfold on list or your definition for trees. In other words: your definition was indeed the right one.

这篇关于对于未标记的树，“展开”的正确定义是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！