Какая языковая функция позволяет перейти от посетителя к последовательности?

Question

Я буду использовать синтаксис C#, так как я знаком с ним, но он не является специфичным для языка.

---

Предположим, мы хотим предоставить API для перехода через Tree и сделать что-нибудь с каждым Node.

Решение 1: void Visit(Tree tree, Action<Node> action)
Он принимает tree и вызовы action на каждом узле дерева.

Решение 2: IEnumerable<Node> ToEnumerable(Tree tree)
Он преобразует tree к плоской ленивым последовательности таким образом, мы можем пойти и позвонить action на каждом узле.

---

Теперь давайте посмотрим, как мы можем конвертировать один API в другой.

Это довольно тривиально, чтобы обеспечить Visit на вершине ToEnumerable:

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

Однако, есть понятие/особенность на любом языке, что позволит обеспечить ToEnumerable на вершине Visit (как ленивая последовательность, так список не создается заранее)?

Answer 1

Не уверен, что я правильно вас понимаю, но в Python вы можете создать итеративный интерфейс для любого объекта. Итак, вы просто добавите специальный метод __iter__ (который даст узлы при обходе дерева). Процедура visit состоит в том, чтобы выполнить итерацию через объект Tree и вызвать action на каждом узле.

Answer 2

Если вы пишете код, который будет посещать каждый узел (как с деревом), возможно, есть итераторы итератора для каждой ветви и выполнить yield return на листовых узлах. Этот подход будет работать, и он очень прост, но имеет серьезный недостаток, что очень легко получить код, который будет очень читабельным, но выполняется очень медленно. Некоторые другие вопросы и ответы на этом сайте помогут понять, как эффективно перемещаться по деревьям внутри итератора.

Если «дерево» было всего лишь примером, и у вас действительно есть класс, который предоставляет процедуру для вызова некоторого делегата на каждом узле (аналогично List.ForEach()), но не выставляет IEnumerable, вы можете быть в состоянии чтобы использовать первый, чтобы создать List, который вы могли бы затем повторить. Используйте что-то вроде var myList = new List<someThing>(); myCollection.ForEach((x) => myList.Add(x));, и тогда вы сможете перечислить myList.

Если этого недостаточно, поскольку объекты, которые были добавлены в список, могут быть недействительны по истечении времени, указанного в списке, в редких случаях возможно использовать несколько потоков для выполнения необходимого. Например, если у вас есть две сортированные коллекции, метод ForEach подготавливает каждый элемент к использованию, выполняет ли указанное действие и затем очищает каждый элемент перед тем, как перейти к следующему, и если вам нужно чередоваться с действиями по элементам из двух независимых коллекций, можно было бы выполнять итерацию коллекций в отдельных потоках и использовать примитивы синхронизации, чтобы каждый поток подождал по мере необходимости для другого.

Обратите внимание, что коллекции, которые только выставляют себя с помощью метода ForEach склонны ограничивать доступ во время выполнения такой ForEach (если такое ограничение не было необходимости, они, вероятно, реализовать IEnumerable). Возможно, что «действие предмета», вызванное одним ForEach, выполнить еще один ForEach в том же сборнике в том же потоке, поскольку последний ForEach должен был завершиться до того, как предыдущий мог возобновиться. Однако, хотя один ForEach работает, попытка вызвать ForEach во втором потоке, вероятно, либо сработает, либо дождитесь завершения первой операции. Если первый ForEach ожидал какого-либо действия вторым, это приведет к взаимоблокировке. Из-за этого сценарии, в которых многопоточность будут работать лучше, чем просто создание List, редки. Тем не менее, есть несколько случаев, когда это может быть полезно (например, вышеупомянутая операция «застежка-молния» в независимых коллекциях).

Answer 3

Думаю, теперь я понимаю идею. Концепция, которая мне нужна здесь, называется 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. Я уточню ответ, когда пойму это.