在 Haskell 中实现可折叠的 n 叉树并进行中序遍历

Question

我正在尝试在 Haskell 中实现 n 叉树数据结构的 Foldable 实例。我想定义foldr，使其按顺序遍历树。但是，我无法使其正常工作。

这是我的代码：

data TreeL a = NodeL a [TreeL a] deriving (Show, Eq)

instance Foldable TreeL where
  foldr f b (NodeL x []) = f x b
  foldr f b (NodeL x (t:ts)) = foldr f (foldr f b ts)

我有一个测试属性 prop_tree_foldable 来检查折叠是否正确且按顺序完成。 它生成一棵随机树并检查foldr (:) [] (fst <$> t) 的结果是否是已排序的数字列表。但是，我的实现未通过此测试。

我尝试了几种不同的方法，但我似乎无法获得正确的遍历顺序。有人可以帮助我了解我做错了什么以及如何解决它吗？

Answer 1

我不确定正确的解决方案是什么，因为我不知道“按顺序”对于该数据类型意味着什么。

但我可以肯定地告诉你，你只是生成节点中的元素列表。在递归情况下，您没有对

x

执行任何操作。事实上，你也扔掉了

t

。如果您不使用整个参数，您的解决方案就不可能是正确的。

就其价值而言，对于这种数据类型，用 foldr 来写

toList

更容易

远

。我强烈建议从那里开始。