问题标签 [traversable]

尽管标题充满了行话，但我认为这个问题并不复杂。

人物介绍

这里有两个重要的 Functor 组合子在起作用。Flip等效于 haskell 函数flip，但对类型进行操作

并且Join等效于类型上的 W 组合子，它接受一个双函子并沿其两个参数生成一个函子

可遍历

现在Foldable可以创建以下实例：

也就是说，如果p在它的两个参数上都是可折叠的，那么它Join p是可折叠的。这是通过向左折叠然后向右折叠来完成的。

现在我想为 做一个类似的实例Traversable，但是我遇到了一个问题。sequence我可以很容易地写作

但是，我似乎需要能够使用join，所以我在编写时遇到了麻烦sequenceA。事实上，写一个sequenceA.

但是我很难想出一个反例。那是p可以在两个参数上遍历但在连接时不可遍历的。

到目前为止，我已经尝试了所有基础知识，但没有一个是反例。Join (,)是可遍历的

高阶元组，例如Join ((,,) a)很好。

Join Either也是可遍历的

我通过组合类型提出了更多示例，为了简单起见，我将省略这些示例，但不用说它们最终都是可遍历的。

有反例吗？这个实例可以写吗？

AFunList是 Twan van Laarhoven 在这篇博文中发明的一种数据类型。Bartosz Milewski 给出的一个小变化如下所示：

关于这个数据类型的一个有趣的事实是，如果我们稍微调整一下类型参数，我们有一个Profunctor：

服从dimap id id = id和dimap (f . g) (h . i) = dimap g h . dimap f i

该类Profunctor有几个有用的子类，它们代表带有附加设备的 profunctor 家族（在范畴理论意义上）。具体来说，我们可以谈论具有“强度”的profunctors：

法律由“双范畴中的强单子”的分类概念决定（这在Kazuyuki Asada的“箭头是强单子”中有详细解释）。

类似地，由于 profunctor 是“just” functor，我们可以查看 profunctor 是否是幺半群的：

具有由单曲面函子的定义给出的定律。

t1, t2,t3和i1,的一些有趣的选择分别是, i2,和。i3(,)EitherThese()Void

FunList问题是重组后的实例化了哪些此类？带有一些关于为什么它遵循法律的论据的实现会非常好，正确性的证明会非常好。

TODO：在此处专门列出每个类别的法律列表

我可以通过映射 ( , ) 或折叠 ( , ) 另一个可遍历的数据结构来构建作为类型类成员的数据结构Traversable（例如Listor ）。MapmapmapMfoldlfoldM

但是，我经常遇到需要使用类型类的成员Num（例如Integer）构建可遍历的数据结构的情况。

我通常的方法是使用递归操作来构建一个列表——例如：

此函数返回可被 2 整除且介于 2 和 n（含）之间的整数的绝对值。

使用上面的示例，是否有一种惯用的方法可以在不使用递归的情况下从不可遍历的列表中构建列表？

我正在尝试使用 haskell 类，我发现（至少某些）Traversable数据结构也是Applicative

当您查看 的定义时Traversable，您会发现它可以使用以下sequenceA函数定义：

由于list是Traversableand Applicative，我确实尝试在列表列表中使用 sequenceA ：

我得到了 2 个列表的笛卡尔积！

它甚至适用于更多的列表。

这是什么情况？

这个函数的行为背后的直觉是什么？

考虑 Haskell 中的这两个函数：

replace_snd替换对的第二个元素，如果没有对，则返回 Nothing：

inject_snd替换第二个元素，如果没有替换则返回 Nothing：

还要考虑它们的对称对应物replace_fst，inject_fst它们作用于一对的第一个元素：

我的问题是： 这四个函数中的哪一个可以使用诸如一元运算符之类的内置函数更紧凑地编写？如何？

例如，我意识到inject_sndis just (mapM . const)，因为Maybeis aMonad和((,) a)is a Traversable：

其他三个功能是否有类似的紧凑等价物？

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的向量。

Base 提供ZipList，它只是[]where <*>is basedzip而不是笛卡尔积的包装器。这不是默认设置，因为它与实例不一致Monad []，但有些人发现它更直观，并且这两种行为在不同的上下文中都很有用。

Edward Kmett 提供Distributive，即Traversable. Traversable 可以映射/推送/分发到任何 Applicative Functor；可以从任何 Functor 中提取/分解分布。（由于我没有解包的原因，distribute不需要外层是Applicative。）

长度索引列表是 ​​Distributive，并按照您的期望工作。具体来说，他们的 Applicative 实例基于zip，就像ZipList！这表明ZipList也可能是Distributive，这将是有用的。

文档Distributive说明了任何实例都必须为真的两件事：

• (->) x“对于某些人来说，它 [必须] 同构x。”
  • 列表与偏函数同构Int ->。
• “[它]需要有一种方法来持续压缩可能无限数量的自身副本。”
  • 这或多或少是raison d'être的存在理由ZipList。

这够好吗？今天下午我花了几个小时试图写作instance Distributive ZipList where distributive = ...，但无法让它发挥作用。对于大多数函子f ZipList a来说， 有一个明显的含义distribute f，尽管我担心这可能只是因为我没有考虑足够多的非遍历函子。

• Maybe很棘手；应该distribute Nothing是[]还是repeat Nothing？但是distribute是双重的sequenceA，Traversable Maybe实例说它应该是repeat Nothing。
• (->) e可能是交易破坏者。
  • 直觉distribute $ const (repeat x) = repeat (const x)上。
  • 我们可以将其扩展到任何保证返回无限列表的函数；它看起来有点像(\i -> (! i) <$> f) <$> [0..]。
  • 我们可以将其扩展到返回有限列表的函数；我们最终得到一个无限的偏函数列表。这对我来说并不明显，这是不可接受的。使用列表时，部分函数会一直出现。
  • 但这意味着distribute $ const [] ≅ repeat undefined，这有点愚蠢。
  • 该实例Applicative ZipList包含一个重要的设计决策：（length (a <*> b) == min (length a) (length b)而不是错误或其他）。我们根本没有利用它。我可以看到我们可能会的方式distribute = const []。

有没有人看到前进的道路？

distribute f = (\i -> (!! i) <$> f) <$> [0..]如果部分函数解释是“可接受的” ，我们能否以比

试图将我的思想围绕遍历 - 或者在这种情况下可能略有不同。

我将遍历理解为对可遍历结构执行应用操作（或效果）的操作。因此，例如从Data.Traversable，

wheremapM只是traversefor monads 的一种形式。所以这需要一个函数g，它返回一个从 1 到函数输入的列表，以及一个Maybe. 在 上遍历这个列表返回函数的结果Maybe Just是Just应用于列表中每个元素的构造函数，范围从 1 到3原始 中包含的Just。这一切都很好。

我想知道的是，如果我们稍微概括一下会怎样g。在遍历中，g获取a与 中包含的类型匹配的类型值Traversable，并返回结果类型的应用程序b：

相反，如果不是g仅返回f b，而是返回与f (Const m b)整个操作返回的类型相同的类型，该怎么办 -

我的具体上下文是这样的 - 我正在一个应用程序中工作，该应用程序由一系列Maybe具有异步效果的计算组成，这些操作本身异步返回Maybes。所以它看起来像

• 从一个开始Maybe m1
• traverse-like一个异步操作m1
  • 如果m1是Nothing，则计算短路，即traverse-like返回m2 == Nothing计算
  • 如果m1是Just x，执行可能返回async Nothing或的异步效果async Just x，sttraverse-like返回m2 == Nothing或Just async x
• traverse-like一个异步操作m2...

此操作的主要用途是将 a Maybe async Maybe（通过遍历a -> async Maybe操作获得）展平为 a Maybe async。

整个世界对我来说都是新的（来自命令式背景），所以如果我什至没有正确考虑这一点，我深表歉意 - 但我希望上面的例子至少能清楚地说明我想要完成的事情。它似乎比单纯的遍历更通用，类似于 how bindis more general than map- 但我不知道实际调用的操作是什么，或者它是否在这个特定用例之外有意义。如果在函数式编程、Haskell 等方面有更多经验的人能够阐明这种操作的本质，我将不胜感激。