对于未标记的树,"展开"的正确定义是什么？

Question

我一直在考虑如何实现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)

虽然这似乎有效,但我不确定这是怎么回事.所以,这就是问题:做正确的方法是什么？

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的列表或树的定义.换句话说:你的定义确实是正确的.