什麼語言功能可以允許從訪問者到序列的轉換？

我將使用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

什麼語言功能可以允許從訪問者到序列的轉換？

回答

相關問題