Написание рекурсивного посетителя папки F # в C # - seq vs IEnumerable

Question

Я часто использую этот рекурсивный 'посетитель' в F #

let rec visitor dir filter= 
    seq { yield! Directory.GetFiles(dir, filter)
          for subdir in Directory.GetDirectories(dir) do yield! visitor subdir filter} 

Недавно я начал работать над реализацией некоторой функциональности F # в C #, и я пытаюсь воспроизвести это как IEnumerable, но у меня возникают трудности с дальнейшим развитием:

static IEnumerable<string> Visitor(string root, string filter)
{
    foreach (var file in Directory.GetFiles(root, filter))
        yield return file;
    foreach (var subdir in Directory.GetDirectories(root))
        foreach (var file in Visitor(subdir, filter))
            yield return file;
}

Что я не понимаю, так это то, почему для рекурсии я должен выполнить двойной foreach в версии C #, а не в F # ... Является ли seq {} неявным образом 'concat'?

Answer 1

yield! выполняет операцию «сглаживания», поэтому она интегрирует последовательность, которую вы передали, во внешнюю последовательность, неявно выполняя foreach для каждого элемента последовательности и yield для каждого.

Answer 2

Нет простого способа сделать это. Вы можете обойти это, определив тип C #, который может хранить либо одно значение, либо последовательность значений - используя нотацию F #, это будет:

type EnumerationResult<'a> = 
  | One of 'a
  | Seq of seq<'a>

(переведите это на C # так, как вам нравится: -))

Теперь вы можете написать что-то вроде:

static IEnumerable<EnumerationResult<string>> Visitor
       (string root, string filter) {
   foreach (var file in Directory.GetFiles(root, filter))
      yield return EnumerationResult.One(file);
      foreach (var subdir in Directory.GetDirectories(root))
           yield return EnumerationResult.Seq(Visitor(subdir, filter))
   }
}

Чтобы использовать его, вам нужно написать функцию, которая выравнивает EnumerationResult, который может быть методом расширения в C # со следующей сигнатурой:

IEnumerable<T> Flatten(this IEnumerable<EnumerationResult<T>> res);

Теперь, это часть, где это становится сложным - если бы вы реализовали это простым способом, он все равно содержал бы «forach» для перебора вложенных результатов «Seq». Однако я считаю, что вы могли бы написать оптимизированную версию, которая не имела бы квадратичной сложности.

Хорошо ... Я думаю, что это тема для поста в блоге, а не что-то, что могло бы быть полностью описано здесь :-), но, надеюсь, это показывает идею, которой вы можете следовать!

[РЕДАКТИРОВАТЬ: Но, конечно, вы также можете использовать простую реализацию "Flatten", которая будет использовать "SelectMany" только для того, чтобы сделать синтаксис вашего кода итератора C # лучше]

Answer 3

В C # я использую следующий код для такого рода функции:

public static IEnumerable<DirectoryInfo> TryGetDirectories(this DirectoryInfo dir) {
    return F.Swallow(() => dir.GetDirectories(), () => new DirectoryInfo[] { });
}
public static IEnumerable<DirectoryInfo> DescendantDirs(this DirectoryInfo dir) {
    return Enumerable.Repeat(dir, 1).Concat(
        from kid in dir.TryGetDirectories()
        where (kid.Attributes & FileAttributes.ReparsePoint) == 0
        from desc in kid.DescendantDirs()
        select desc);
}

Это устраняет ошибки ввода-вывода (которые неизбежно случаются, к сожалению) и позволяет избежать бесконечных циклов из-за символических ссылок (в частности, вы столкнетесь с поиском некоторых каталогов в Windows 7).

Answer 4

В конкретном случае получения всех файлов в определенном каталоге эта перегрузка Directory.GetFiles работает лучше всего:

static IEnumerable<string> Visitor( string root, string filter ) {
  return Directory.GetFiles( root, filter, SearchOption.AllDirectories );
}

В общем случае обхода дерева перечислимых объектов требуется вложенный цикл foreach или эквивалент (см. Также: Все об итераторах ).

---

Редактировать: Добавлен пример функции для сглаживания любого дерева в перечислении:

static IEnumerable<T> Flatten<T>( T item, Func<T, IEnumerable<T>> next ) {
  yield return item;
  foreach( T child in next( item ) )
    foreach( T flattenedChild in Flatten( child, next ) )
      yield return flattenedChild;
}

Это можно использовать для выбора всех вложенных файлов, как и раньше:

static IEnumerable<string> Visitor( string root, string filter ) {
  return Flatten( root, dir => Directory.GetDirectories( dir ) )
    .SelectMany( dir => Directory.GetFiles( dir, filter ) );
}