能否将树泛化为允许任何可遍历的子树？

Question

Data.Tree 使用列表来表示以特定节点为根的子树。是否可以有两种树类型，例如一种使用列表，另一种使用向量？我希望能够编写不关心子树如何具体表示的函数，只关心子树是可遍历的，以及利用特定子树类型的函数，例如快速索引到向量中。

似乎类型族是完成这项工作的正确工具，尽管我以前从未使用过它们，而且我不知道如何真正定义正确的族。

如果重要的话，我没有使用容器库树实例，而是使用类型

data Tree a b = Node a b [Tree a b] deriving (Show, Foldable, Generic)

和

data MassivTree a b = V a b (Array B Ix1 (MassivTree a b))

其中后者使用来自 massiv.

的向量

Answer 1

您可以使用类型类 - 实际上您需要的类型类可能已经存在。

考虑一下：

data Tree t a = Tree a (t (Tree t a))

参数 t 是更高种类的类型，代表 as 的容器。

现在定义一组树操作，像这样限制在 Traversable 上：

:: (Foldable t) => Tree t a -> b

您现在可以创建和操作使用任何 Foldable 的树。您需要为您想要的操作集选择正确的类型类 - Functor 可能就足够了，或者如果您正在对 monadic 操作执行任何操作，您可能需要 Traversable。您可以根据每个函数的作用选择类型类。

您现在可以像这样定义 Tree 类型：

type ListTree a = Tree [] a
type MassivTree r ix a = Tree (Array r ix) a

您还可以定义特定于实例的函数，以访问所有功能：

:: ListTree a -> b
-- or
:: Tree [] a -> b

Haskelling 快乐！

Can trees be generalized to allow any traversable sub-tree?