问题标签 [foldable]

我是 Haskell 的初学者，正在学习“Learn You a Haskell”。

关于. Tree_Foldable

来自 LYAH 的引述：“因此，如果我们只foldMap为某种类型实现，我们就 可以免费获得该类型foldrfoldl！” .

有人可以解释一下吗？我不明白我现在如何以及为什么foldr免费foldl获得...

在 Haskell 中，我们看到Foldable 和 Traversable 在 Haskell prelude 中落地。

这些都对序列进行操作。

我的问题是Haskell 的 Foldable 和 Traversable 是否相当于Clojure 中的一个序列？

假设：

• 我意识到Haskell 中 fmap的等价物是Clojure 中的m-fmap。

我正在尝试编写自己的 foldMap 函数作为学习 Haskell 的练习

目前它看起来像这样

但是在编译时会出现以下错误

我无法弄清楚编译器试图告诉我这个错误是什么，谁能告诉我我的 foldMap 出了什么问题？

我正在“ http://learnyouahaskell.com ”的帮助下学习 Haskell。我正在关注作为以下实例的 BST（二叉搜索树）的示例Foldable：

当我运行时，F.foldMap (\x -> [x]) testTree我得到一个代表折叠树的列表。我实现了自己的数据类型：

并运行此命令：F.foldMap (\x -> OnlySum x) testTree获取折叠为 this 的树OnlySum {value = 34}。

问题是：Foldable 如何知道传递给的函数的返回类型mempty以及mappend取决于f传递给的函数的定义foldMap？它是推断它还是 Haskell 有办法自动知道哪个是定义？

我有一个简单的功能（实际上用于欧拉项目的一些问题）。它将数字列表转换为十进制数。

我意识到这种类型[Int]并不理想。fromDigits应该能够接受其他输入，例如序列，甚至可能foldables......

我的第一个想法是用一种“带状态的折叠”替换上面的代码。上述函数的正确（= 最小）Haskell 类别是什么？

我有一棵树：

我想对它应用一个scan类似于列表的操作——除了返回一个列表，它应该返回一个带有行进路径的树。例如：

应减少为：

通过树累加总和。这有标准功能吗？

这是带有标记节点和边的循环有向图的类型。

为了处理图有循环的情况，可以“打结”并在有限空间中创建无限递归图。

通过将图形视为节点的集合，我们可以编写一个Foldable执行深度优先遍历的实例。*

然而，即使对于简单的树形图，这也会产生重复的元素：

当图形有循环时，效果更加显着——foldMap永远递归！循环中的项目是重复的，有些元素永远不会返回！

这个可以吗？一个实例可以Foldable多次返回它的一些元素，还是我违反了类的合同？实例可以在结构的一部分上无限循环吗？我一直在寻找关于这个问题的指导——我希望有一套“可折叠的法律”来解决这个问题——但我无法在网上找到任何关于这个问题的讨论。

摆脱这种情况的一种方法是“记住”在我遍历图表时已经访问过的元素。但是，这会给 的签名添加一个EqorOrd约束foldMap，这会阻止我的类型成为 的成员Foldable。

_{* 顺便说一下，我们不能为 编写一个Functor实例NodeGraph，因为它会破坏图中节点被唯一标记的不变性。（fmap (const "foo")例如，将每个节点重新标记为“foo”，尽管它们都有不同的边集！）我们可以（使用适当的newtype）编写一个Functor映射所有边标签的映射。}

我在玩类型对齐的序列，特别是我在弄乱折叠它们的想法。一个可折叠的类型对齐序列看起来像这样：

它很容易实现foldrTA，foldMapTA首先使用foldMapTA以天真的方式将序列转换为类型对齐列表（即，使用类型对齐列表类别），然后折叠该列表。不幸的是，这可能非常低效，因为长列表可能会附加到短列表之前。我一直在尝试找出一种方法来使用类似于用于Data.Foldable更有效地定义左右折叠的技巧，但是这些类型让我头晕目眩。Endo似乎不够通用，无法做到这一点，而且我在其他方向上采取的每一步都会导致我获得更多的类型变量，而我无法跟踪。

是否有一种简单的方法可以在 GHC 7.8 或更早版本上模拟燃烧的桥梁提案（也称为可折叠/可遍历提案， GHC 7.10的一部分）？

有些方面真的很难模仿。这包括类层次结构的变化。最有可能的是，该部分无法被模拟。

新功能和功能替换可以简单地从Data.Foldable朋友那里导入。然而，新类型签名的功能如length或null不可用。以下代码片段实现了假装燃烧桥梁的某些方面：

是否有一些包以更完整的方式做到这一点？

我们可以创建 Functor 实例并使用

但是，如果我想要 (Tree t -> a) 而不是 (t -> a) 那么我可以访问整个 (Node t) 而不仅仅是 t

与折叠相同

对这些函数有什么概括吗？