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

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

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

Недавно я начал работать над реализацией некоторой функциональности F # в С#, и я пытаюсь воспроизвести ее как 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 в версии С# для рекурсии, но не в F #... Является ли seq {} неявным образом "concat"?

Ответы

Ответ 1

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

Ответ 2

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

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

(переведите это на С# любым способом, который вам нравится: -))

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

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, которая может быть методом расширения в С# со следующей подписью:

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

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

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

[EDIT: Но, конечно, вы также можете использовать наивную реализацию "Flatten", которая будет использовать "SelectMany", чтобы сделать синтаксис вашего кода итератора С# более приятным]

Ответ 3

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

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

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

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

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 ) );
}

Ответ 4

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

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).