问题标签 [traversable]

我有一个玫瑰树结构，我想Traversable为它写一个实例。所以我从以下开始：

我做了它的深度优先变体：

然后我尝试了广度优先的变体：

我意识到这个的广度和深度优先变体Traversable应该是相同的。是这样吗？我不相信我实际上在任何地方都读过这篇文章，但遍历与元素的顺序无关？

如果是这样，这有点奇怪，因为Traversable可以直接实现 for Tree，这意味着Foldable需要实现 for Tree，但显然有多种方式Foldable可以实现。

我正在查看 Scala 2.12 Collection Library 源代码并注意到以下内容：

Monad Opsimplicit上课的原因是什么？的Traversable子特征TraversableOnce将所有单子方法定义为不作为 imlpicit 类（TraversableLike尽管如此）。

如何使用它同时继承和Traversable的事实？FoldableFunctor

t作为可遍历类型意味着t也是函子类型和可折叠类型。

我看到这t是一个函子类型的事实，即fmap，用于traverse.

t可折叠类型是否在某处使用？

使用折叠式traverse的事实吗？t

使用哪个事实sequenceA：t作为函子类型，t作为可折叠类型，或两者兼而有之？

我们可以定义一个类，它是only 的子类，并且Functor具有以相同方式定义的函数吗？traversesequenceA

谢谢。

假设我有这种Tree类型：

编写一个函数来计算特定类型内事物的最大深度很容易：

但是要计算任意Traversable. 我已经知道这Functor还不够，因为您无法通过 获得有关它们内部事物“位置”的信息fmap，而且我也已经知道这Foldable还不够，因为foldr两者foldMap都只提供尽可能多的信息列表的结构。Traversable不过，可能是因为它比Functor和更通用Foldable。

但是，在做了一些实验之后，我认为Traversable两者都没有办法。到目前为止，这是我的逻辑。考虑这两棵树：

现在，traverse (\() -> thingy) fooTree是：

在大量使用应用法则和一些简化之后，它变成：

同样，traverse (\() -> thingy) barTree是：

在大量使用应用法则和一些简化之后，它变成：

现在看起来它们具有相同的“形状”（唯一的区别是开头的 lambda，甚至它们的类型都相同），但它们来自具有不同深度的树traverse (\() -> thingy) fooTree。traverse (\() -> thingy) barTree这使我相信不可能找到 的深度traverse，但我不是 100% 确定它，我不知道如何严格解释它。

我说得对吗，这是不可能的？如果是这样，那么如何才能真正严格地解释这一点？如果没有，那么你将如何实现它？

自然法规定：

现在对于法律的 RHS，如果 f 具有 type Applicative a => x -> a y，则 t 必须是 type (Applicative a, Applicative b) => a y -> b y，因为函数组合。

对于 LHS，遍历 f 的类型为(Applicative a, Traversable c) => c x -> a (c y)。但是由于 traverse f 是由 t 组成的。遍历 f，t 必须是 (cx -> a (cy)) -> b y 类型。

现在，对于 LHS，t 的类型为 a (cy) -> by，但在 RHS 中，它的类型为 ay -> b y。从类型的角度来看，法律听起来如何？

编辑：修复了 LHS 中的类型 t

我正在尝试通过 Haskell 类型系统对 kdb/q“原子和列表”进行建模。

在 kdb/q 中，所有数据都是从原子构建的。原子是特定数据类型的不可约值。Int、boolean 和 char 是原子的示例。列表是从原子构建的有序集合。由于 q 是一种向量语言，大多数内置操作都是原子的，因此它会递归到参数结构中，直到它到达原子。

例如：

(1;2;3) 是整数 1、2、3 的简单列表

(1.0;2;(3;4;5)) 是 1.0(float)、2(int) 和简单 int 列表 (3;4;5) 的一般列表

neg 是一个对一个数字求反的函数。例如：

否定 1 产生 -1

负 -1.0 产生 1f

否定 (1.0;2;(3;4;5)) 产生 (-1f;-2;(-3;-4;-5))。

这就是启发我尝试在 Haskell 类型中建模这种行为的原因。数据类型应由原子类型和列表组成。

以下是我目前所拥有的简化版本。我还进一步尝试使其成为可折叠和可遍历的实例。

这就是我所拥有的并且它可以编译，但我并不特别喜欢 concatL 函数，它没有根据类型涵盖所有模式。一旦我开始向 Q 添加一个新的值构造函数 QDict [(Q Atom, Q a)]，情况就会变得更糟。

我是否正确地对原始数据建模？我是否应该尝试使其可遍历？但是，如果我需要将数据类型与 Maybe 或 Either 一起使用来建模错误，我认为 Traversable 是必要的。

任何建议表示赞赏。

编辑：编辑 q 代码格式

如果我想拥有类似的东西，我应该使用什么

基本上我有一个函数列表，所有函数都接受一个值a并返回b。我想将它们全部应用于一个a并获得结果[b]。

我应该使用哪一个？

谢谢

我记得在某处读过这样的类型不可能Traversable：

我记得的一点解释是，foldMap = foldMapDefault为了保持，Traversable实例必须不止一次地访问它的元素，这是合法实例无法做到的。但是，我不记得为什么合法的实例不能这样做。考虑这个：

乍一看还不错。这样做有什么违法的？

三天后我有一个 Haskell 考试，所以我想我应该练习一下，然后回顾过去的考试，其中一个具有以下 Tree 数据类型：

一开始似乎没有什么挑战性，但后来我意识到我必须为这棵树编写一个 Traversable 实例。处理叶子很容易：

但是，我开始遇到 Node.js 的问题。

自然，这些不起作用，我无法理解第二个 <*> 之后应该发生的事情。我尝试使用漏洞，但 ghci 给我的消息并没有太大帮助（我知道问题出在类型上，但我不知道应该如何解决它）。

这是我尝试编译它时收到的错误消息：

有人可以给我一些指示或解决此问题的可能吗？

sequenceA是一个众所周知的函数：

我想知道我们是否可以为 Arrows 写下类似的东西。不幸的是，我没有设法实现以下内容：

据我了解，Applicative泛化Arrow，因此，我们应该能够写下来。我这样做是为了列表：

然而，正如人们注意到的那样，我们并没有摆脱列表中的a b图层，而是将结果包装到一个新列表中。那么，我们如何才能真正摆脱a b层呢？我应该注意到，在这个问题下的评论中，duplode指出：

...在(.)、和之间id，没有任何东西可以将两层合二为一。arrfirsta r

如果他们是对的，我们需ArrowApply要这样做吗？坦率地说，我写下来了，仍然无法摆脱里面的箭头t：

可以调整这个片段以缺少a ()图层吗？

所以，我的问题是：

1. sequenceArr :: (Traversable t, Arrow a) => t (a b c) -> a b (t c)- 我们可以写下来吗？如果是这样，怎么做？
2. 有什么方法可以摆脱a b层（Arrow a）。如果是这样，为什么当我们写下来时它们不起作用join（Arrow如果它们实际上没有）？
3. 我们需要ArrowApply这个吗？如果是这样，怎么做？是否可以调整我的变体以获得此结果：sequenceArr :: (Traversable t, ArrowApply a) => t (a b c) -> a b (t c)？