什么语言功能可以允许从访问者到序列的转换？

我将使用C＃语法，因为我熟悉它，但它并不是特定于语言的。
什么语言功能可以允许从访问者到序列的转换？

比方说，我们想要提供一个API来检查 Tree并对每个 Node做些事情。

解决方案1：void Visit(Tree tree, Action<Node> action)
它需要一个tree，并在树中的每个节点上调用action。

解决方案2：IEnumerable<Node> ToEnumerable(Tree tree)
它转换tree到一个平面懒序列，所以我们可以走了过来，并在每个节点上调用action。

现在，让我们看看我们如何将一个API转换为另一个。

这是非常微不足道的对ToEnumerable顶部提供Visit：

void Visit(Tree tree, Action<Node> action) { 
    ToEnumerable(tree).ForEach(action); 
}

然而，有没有在这将允许对Visit顶部提供ToEnumerable任何语言概念/功能（如懒序列，所以列表不是事先创建的）？

来源

2012-07-13 Andrey Shchekin

不知道你在问什么...你想要一个类/模式，它会自动创建一个懒惰的IEnumerable'对象层次结构，给定一个适当的访问者方法？（如果是这样，我怀疑答案是“否”，除非对象还支持只遍历给定对象的“children”的* flat *枚举）。 – 2012-07-13 13:31:26

@KonradRudolph是的。尽管我不需要课堂/模式，更像是一种语言特征或概念。我有一种感觉可能与延续有关，但我对他们不够熟悉。 – 2012-07-13 13:35:33

我认为这是结构的属性，而不是任何语言功能。 Haskell的Foldable（http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html）中最纯粹的（如最抽象的）表示，特别参见foldMap 。 – 2012-07-13 14:17:40

不知道我是否理解正确，但在Python中，您可以在任何对象上创建可迭代接口。所以你只需要添加特殊的方法__iter__（这将在遍历树时产生节点）。然后visit程序正在迭代通过Tree对象并在每个节点上调用action。

来源

2012-07-13 13:27:06 JoshuaBoshi

这就是在'__iter__'之上实现'visit'。但是我有一个实现'visit'的对象，我怎么才能使用'visit'来定义'__iter__'？ – 2012-07-13 13:36:56

你可以指定'visit'方法接受任何迭代。如果您在Tree中指定了'__iter__'方法，那么将Tree传递为此迭代将会工作。对不起，如果我误解了你。 – JoshuaBoshi 2012-07-13 13:47:14

假设'树'没有'__iter__'。它只有'visit'。你不能改变'树'。你想使用'iter'来迭代'Tree'，使用它的'visit'。你会怎么做？ – 2012-07-13 13:56:24

如果你正在写的代码将访问每个节点（如树），有可能对每个分支的迭代器调用迭代器，并在叶节点进行yield return。这种方法很有用，而且非常简单，但有一个严重的缺点，即代码非常容易读取，但执行速度非常缓慢。本网站上的其他一些问题和答案将提供有关如何在迭代器中高效遍历树的见解。

如果“树”只是一个例子，并且您真正拥有的是暴露例程以在每个节点上调用某个代理的类（类似于List.ForEach()），但未公开IEnumerable，则可以使用前者产生一个List，然后你可以迭代。使用类似var myList = new List<someThing>(); myCollection.ForEach((x) => myList.Add(x));的东西，然后您可能会列举myList。

如果即使这还不够，因为添加到列表中的对象在枚举完成时可能无效，但在极少数情况下，可以使用多个线程来完成所需的操作。例如，如果您有两个已排序的集合，其ForEach方法会准备好每个项目以供使用，请执行指定的操作，然后清理每个项目，然后再继续下一个项目，并且您需要交叉处理来自两个独立集合，人们可以在单独的线程上迭代集合，并使用同步基元，这样每个线程都会根据需要等待另一个线程。

请注意，只有通过ForEach方法公开自己的集合才能在执行这种ForEach（如果此类限制不是必需的，它们可能会实现IEnumerable）期间限制访问。一个ForEach所调用的“item action”可能会在同一个线程的同一个集合上执行另一个ForEach，因为在前一个可以恢复之前，后一个ForEach必须完成。然而，一个ForEach正在运行，但是，尝试在第二个线程上调用ForEach可能会发生故障或等待第一个操作完成。如果第一个ForEach正在等待第二个动作，则会导致死锁。正因为如此，多线程将比简单构建List好的情况很少见。尽管如此，在少数情况下可能会有所帮助（例如上述“独立收藏”的“拉链”操作）。

来源

2012-07-13 14:58:44 supercat

感谢您花时间回答。我认为线程示例与我所询问的最接近，但它是一种更通用的模式的具体实现/方法，它本身不需要线程，只需要保存状态/恢复状态的能力。现在我认为这就是所谓的延续，但在完成我的理解之前，我还得多研究一下。再次感谢。 – 2012-07-14 02:20:33

@AndreyShchekin：有些对象允许在保存/恢复操作的任意组合之后保存状态并进行恢复;其他对象强制执行LIFO序列，这样，如果状态保存到X然后保存到Y，则恢复状态X将使Y无效（如果尚未通过其他方式使其失效）。继续是一种手段，通过这种手段，国家可以以任意顺序持有和采取行动。这样的机制可能比强制执行严格堆栈协议的机制更通用，但从实现和语义的角度来看，这些机制也可能更加复杂。 – supercat 2012-07-16 14:48:19

@AndreyShchekin：请注意，能够保存/恢复状态与持有状态有所不同。前者可用于两个任务之间的协同多任务处理，但任何时候操作在任务之间切换时，被挂起的任务必须保存其状态，被唤醒的任务必须恢复其状态。相反，如果每个堆栈都可以在自己的私有状态下运行，那么这两个任务可以同时运行而不会受到干扰。 – supercat 2012-07-16 14:54:44

我想现在我明白了这个想法。我在这里需要的概念被称为first-class continuations或者特别是call/cc。关于它的令人困惑的事情是，C＃已经在yield return中提供了这个概念的有限实现，但它不适用于我的场景。

所以，如果C＃提供的全面实施，该解决方案将类似于：

IEnumerable<Node> ToEnumerable(Tree tree) { 
    tree.Visit(node => magic yield return node); 
}

其中magic yield return而不是从node => ...拉姆达返回序列从ToEnumerable返回下一个元素。

但是，这个答案仍然不完整，因为我没有看到yield return和call/cc之间的确切关联。当我明白这一点时，我会更新答案。

来源

2012-07-14 13:25:33

如果您有兴趣继续进行变形（即折叠），我推荐以下系列博客文章：http://lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven/ – 2012-07-14 15:17:38

什么语言功能可以允许从访问者到序列的转换？

回答

相关问题