对于未标记的树，“展开”的正确定义是什么？

Question

我一直在思考如何为以下类型实现 unfold 的等价物：

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

这不是很明显，因为列表的标准 unfold return 是一个值和下一个种子。对于这种数据类型，它没有意义，因为在到达叶节点之前没有 "value"。这样，只有 return 新种子或以一个值停止才真正有意义。我正在使用这个定义：

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)

虽然这似乎可行，但我不确定它是否应该如此。那么，问题来了：正确的做法是什么？

Answer 1

如果您将数据类型视为函子的固定点，那么您会发现您的定义是列表案例的合理概括。

module Unfold where

这里我们从定义函子的固定点开始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)

无论如何，希望您现在对这个固定点业务有更好的直觉，我们可以看到有一种通用方法可以为这些定义 unfold 函数。

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

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

此定义专用于列表中通常的 unfold 或您对树的定义。换句话说：你的定义确实是正确的。

对于未标记的树，“展开”的正确定义是什么？

What is the correct definition of `unfold` for an untagged tree?

haskell

data-structures

functional-programming

unfold