未打标签的树中，"unfold" 的正确定义是什么？

Question

未打标签的树中，"unfold" 的正确定义是什么？

haskelldata-structuresfunctional-programmingunfold

9

我一直在思考如何实现以下类型的unfold相当于的函数：

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

由于列表的标准unfold返回值和下一个种子不是立即显而易见的。对于这种数据类型，这没有意义，因为在达到叶节点之前没有“值”。因此，只有返回新种子或停止并返回值才是真正有意义的。我正在使用以下定义：

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)

虽然这似乎有效，但我不确定这是否是正确的方法。所以问题是：正确的做法是什么？

- MaiaVictor

1

嗯...这似乎是你唯一可以做的明智之举。 - dfeuer

1

真的吗？我很确定我在这里做了一些愚蠢的事情，但如果是正确的，我可能会删除这个问题。 - MaiaVictor

这个问题并不简单，而且对其他人可能也有用。 - chi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gallais · Accepted Answer

如果你将数据类型视为函子的不动点，则可以看出你的定义是列表情况下合理的推广。

module Unfold where

在这里，我们首先定义了一个functor f的不动点：它是f的一层后跟一些更多的不动点：

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

为了让事情更加清晰，这里是与列表和树对应的函子的定义。它们的形状与数据类型基本相同，只是我们用一个额外的参数替换了递归调用。换句话说，它们描述了列表/树的一层长什么样，并且可以适用于可能的子结构r。

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

接着，列表和树分别是ListF和TreeF的不动点：

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

无论如何，希望您现在对这个不动点问题有了更好的直觉，我们可以看到有一种通用的方式来定义这些内容的展开函数。

给定一个原始种子以及一个接受种子并构建f的一个层次结构的函数，其中递归结构是新种子，我们可以构建整个结构：

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

该定义是针对列表上的常规unfold或者树形结构特定定义。换句话说：你的定义确实是正确的。