为什么以下用于创建 Tree 的可折叠实例的 haskell 代码会导致无限递归

Question

我正在尝试编写我创建的以下树类的可折叠实例：

data Tree a b = Tree b a [Tree a b]

但是我想对定义中的类型"a"进行操作，因此我制作了一个包装器数据类型来翻转树中的类型：

data FlipTree a b = FlipTree (Tree b a)

现在为了写出实际的定义，我想出了以下内容：

instance Foldable (FlipTree a) where
  foldr f x (FlipTree (Tree _ s [])) = (f s x)
  foldr f x (FlipTree (Tree _ s children)) =
              let updated_x = (f s x)
                  tqs = (map (n -> FlipTree n) children) in
              foldl (foldr f) updated_x tqs

但这会导致调用折叠器时无限递归。我花了两天时间，一直无法弄清楚我做错了什么？

这是指向代码文件的粘贴链接。我尽可能地隔离了代码。这是另一个 file1，读取它以使用以下命令运行代码：

Runghc Code.hs 30000000.0 20000.0

Answer 1

不是答案（无限循环的问题前提似乎不正确），而是风格建议——太长了，无法评论。

首先，你可能想让它成为一种newtype（没有理由多一层懒惰）。

newtype FlipTree a b = FlipTree (Tree b a)

其次，对于一个更容易理解的解决方案，IMO倾向于实现foldMap而不是foldr;它使语义更清晰。有多种方法可以折叠这种结构，最合理的似乎是

  foldMap f (FlipTree (Tree _ s [])) = f s
  foldMap f (FlipTree (Tree _ s children))
             = f s <> foldMap (foldMap f . FlipTree) children

其中，外部foldMap折叠在子列表上，再次使用 foldMap for FlipTree s 作为折叠映射。现在，如果你想手动将其转换为foldr等效项，你基本上只需要通过参数进行线程处理。

  foldr f x (FlipTree (Tree _ s children))
             = f s . flip (foldr $ flip (foldr f) . FlipTree) children $ x

现在，该实例可能实际上并没有提供所需的行为，因此请告诉我们您希望它如何表现！

Answer 2

事实证明，定义是 100% 正确的。不需要的行为是由代码的其余部分引起的。但无论如何，感谢堆栈溢出社区一直在那里。