问题标签 [traversable]

如何编写Traversable实例((->) a)？

我想我可以做到，如果我可以一般地打开Applicative Functor：

但是，唉，GHC 不会让我侥幸逃脱：

我是 php 的初学者并从 php.net 学习它。该页面上的注释（http://php.net/manual/en/class.traversable.php）说：

实现此接口的内部（内置）类可以在 foreach 构造中使用，不需要实现 IteratorAggregate 或 Iterator。

这张纸条说了什么？这是否意味着我们可以在没有任何类的情况下在 foreach 循环中使用IteratorAggregate或Iterator或者可能是我错了。谁能说出这张纸条是怎么说的？？

我是 php 新手并从 php.net 学习它。正如我们所知，当我们想要实现Traversable接口时，我们会使用用户定义的类来实现IteratorAggregate或Iterator接口，这些类在内部实现Traversable接口。但是在该页面（http://php.net/manual/en/class.traversable.php ）的第二个注释中让我感到困惑的一件事是：

在实现扩展 Traversable 的接口时，请确保在 implements 子句中的名称之前列出 IteratorAggregate 或 Iterator。

谁能告诉它说的是什么？

Hedgehog有一个HTraversable这样定义的类：

它与它们的Var类型一起用于参数化类型的值是具体的还是抽象的。t有 kind(* -> *) -> *并且是一个高阶函子，尽管他们实际上没有那个类f,g并且h有 kind * -> *。我已经看到在几个不同的库中定义了相同的东西。

有没有办法摆脱这种情况？我承认我什至不知道那会做什么，而且我对镜片或普通镜片也不是很舒服Traversable。

我正在尝试使用Tardis monad 在任何可遍历的容器上实现冒泡排序。

bubble和之间的主要区别bubbleTraversable是Finished标志的处理：bubble我们假设最右边的元素已经排序并更改标志，如果它左边的元素不是；bubbleTraversable我们反其道而行之。

尝试mf在bubbleTraversable程序中进行评估时，会在惰性引用中进入无限循环，如 ghc 输出所示<<loop>>。

问题可能是，它forM试图在单子链接发生之​​前连续评估元素（特别是因为forM是flip traverse用于列表）。有没有办法挽救这个实现？

The traverse and sequenceA function in Traversable class must satisfy the following 'naturality' laws:

for every 'applicative transformation' t. But what is it?

It doesn't seem to work for instance Traversable [] for t = tail:

Nor for t = join (++) (repeat the list twice):

So for what t they are satisfied?

（抱歉，上下文描述很长，但我找不到更简单的方法来解释我的问题）考虑以下类型：

显然，Tree可以定义为Functor如下的实例：

我想定义一个函数，Tree通过排列 的索引来遍历 的实例Array UnitDir (Tree a)（因此它是 6 个可能值的排列UnitDir）。

一个可能的实现是这个：

我的问题如下：是否有一个自然的 Haskell 构造来“遍历”树，同时重新索引孩子？

Functor不起作用，因为我用它来更改树的内容，而不是它的索引方案。看来我需要两个实例Functor，一个用于更改内容，另一个用于更改数组索引。

我认为这Traversable将是正确的选择，但所提供函数的签名都不匹配applyPermutation.

提前感谢您的帮助。

lens提供holesOf，这是这个假设函数的一个更通用和更强大的版本：

给定一个容器，holesList生成一个容器元素列表以及替换这些元素的函数。

的类型holesList，与 real 的类型一样holesOf，未能捕捉到生成的对数将等于容器元素数的事实。因此，一个更漂亮的类型将是

我们可以holes通过使用holesList来创建一个列表，然后遍历State以将元素重新插入。但这并不令人满意，原因有两个，其中一个会产生实际后果：

1. slurping 代码将有一个无法访问的错误调用来处理列表在遍历完成之前运行为空的情况。这很恶心，但对于使用该功能的人来说可能并不重要。

2. 向左无限延伸的容器，或在左侧触底的容器根本不起作用。向左延伸很远的容器处理起来效率很低。

我想知道是否有任何方法可以解决这些问题。Magma使用类似镜头的东西很可能捕获遍历的形状：

现在我们有

traverse Single使一棵树充满元素以及将它们构建到容器中所需的功能应用程序。如果我们替换树中的一个元素，我们可以runFT得到一个替换了该元素的容器。不幸的是，我被困住了：我不知道下一步会是什么样子。

模糊的想法：添加另一个类型参数可能有助于更改元素类型。该Magma类型做了类似的事情，并且至少可以追溯到 Zemyla 对 Van Laarhoven 的博客文章的评论关于FunList.

这个问题实际上是一个非常密切相关的问题的小格子；我认为现在拆分它没有多大意义。

创建 a 的基本方法之一Vector是使用unsafeFreeze. 顾名思义，unsafeFreeze确实是不安全的。特别是，没有什么可以阻止MVector传递的 tounsafeFreeze在冻结后被修改。这会导致两个不同的问题：

1. 它可以使“不可变”向量的值发生变化。这只是 Haskell 通常回避的那种离奇的动作。

2. 修改冻结的向量可能（至少可能）混淆垃圾收集器。没有文档保证垃圾收集器将扫描冻结的数组以确保其内容被清除。更一般地说，绝对禁止在冻结时突变向量，这样做的结果是完全未指定的。

包vector[1] 提供了两个有效的、看似安全的原语来创建不可变向量：create和createT：

忽略向量融合业务，基本实现看起来像

create很明显是安全的。它运行给定的ST s动作，它必须创建一个新MVector s的（类型runST确保它不能使用现有的，并且还确保fixST不能玩任何有趣的技巧），冻结它，并返回冻结的向量。

createTTraversable当实例合法时，显然是安全的。例如，对于列表，createT m运行一个生成MVectors 列表的操作，然后将它们全部冻结。那时的参数化s似乎足以create确保不会发生任何不好的事情。请注意，该操作可能会创建一个包含多个相同副本的列表MVector。这些将被冻结两次，但这不应该有任何伤害。合法的Traversable实例看起来都非常像装饰列表，所以它们的行为应该相似。现在我终于达到了我的第一个问题：

createT与非法Traversable实例一起使用时是否安全？

非法丢弃、复制或重新排列某些元素或更改装饰（违反身份法）不会造成任何明显的困难。参数化可以防止任何有趣的违反自然法则的行为，所以它已经过时了。我还没有找到一种方法来通过违反组成法或整体性来制造麻烦，但这并不能保证没有。

一种明显的泛化方法createT是允许用户传递他们自己的遍历函数：

请注意，我允许遍历将容器类型从 更改t为u。例如，这允许用户产生 aVector (MVector s a)但取回 a [Vector a]。当 时，这显然与非法实例t ~ u一样安全。更改“容器”类型的额外灵活性是否会降低安全性？编辑：我刚刚意识到我可以回答这个问题：不，没有区别。有关说明，请参见下面的 [2]。createTTraversable

当我们使用 时createT，我们可能实际上并不想要一个向量容器；也许我们想遍历那个容器来得到别的东西。我们可以写类似

额外的类型灵活性createTOf意味着我们不一定有 aTraversable在我们手上，也不一定能做到这一点。但是使用 的组合律Traversable，我们可以将这个遍历整合到创建函数中：

如果不是合法穿越，是否createTOfThen安全？trav

我确实说过我会谈论格子，对吧？下一个问题是我们可以在多大程度上（如果有的话）削弱遍历的多态性而不会造成麻烦。即使遍历只需要在 中是多态的，一切都会进行类型检查s，但这显然是不安全的，因为它可以将冻结与修改交错，但它喜欢。揭示最终结果包含Vector值似乎可能是无害的，但我们肯定不能让遍历知道它正在运行并且它正在处理值。但是我们可以让它知道其中一个事实吗？修复肯定会有用：ST s MVector s aApplicative

这将提供更有效的创建诸如向量的向量之类的东西，因为向量可以ST比在任意Applicative函子中更有效地遍历。它还可以减少对内联的依赖，因为我们会避免处理Applicative字典。

另一方面，我怀疑我们可以让遍历知道它正在处理MVector...只要我们不让它知道它们与哪个状态线程相关联。这足以将它们拆箱，并且（也许不幸的是）获得它们的尺寸。

编辑！如果允许遍历知道它正在产生Vectors（这似乎是最不可能出现问题的事情），那么createTOfThen可以按照以下方式实现createTOf：

将晶格放在第三方向，让我们继续进行 rank-2 遍历。该rank2classes包提供了自己的Traversable类，我将其称为R2.Traversable：

我们可以用它玩完全相同的游戏来生成s 的异构容器Vector：

以及允许遍历知道它正在工作的类似版本ST s。我想rank -2 版本的安全属性与相应的 rank-1 版本相同，但我不知道如何证明这一点。

只是为了好玩，我认为我的格子的顶部是下面的怪物。如果这些想法中的任何一个不安全，那么这个想法可能是：

[1] 我已经链接到 Stackage，因为 Hackage 今天停止了。如果我记得并且有时间，我稍后会修复链接。

[2] 证明来自Data.Functor.Sum. 给定一个不改变类型的createTOfSame，我们可以写

这实际上是全部的，尽管“遍历”是部分的：我们总是对我们肯定会找到的内容进行大小写匹配。

http://php.net/manual/en/iteratoraggregate.getiterator.php

返回值 - “实现 Iterator 或 Traversable 的对象的实例”

1）那么返回的总是一个对象的实例，对吗？（我假设是的，但我想确定）。

通过这个网址： http: //php.net/manual/en/class.iteratoraggregate.php

IteratorAggregate 扩展了 Traversable。有人还告诉我，Iterator 也扩展了 Traversable。Traversable 更多的是内部事物（假设是用 CI 编写的），并且无法从 PHP 级别访问。

我熟悉的Iterator，就是当前，key，next，rewind，有效的“东西”。那么 getIterator 返回的内容可以实现这个，如果不是这个，它将 100% 地实现源自 Traversable 的东西？那么 Iterator 不会源自 Traversable 吗？

我的意思是，这个措辞是否正确，或者有什么我不明白的地方？