Mindscape Blog » Blog Archive » Recursive iterators in F#

Recursive iterators in F#

Tagged as F#

C#’s iterator feature makes it very easy to produce sequences without having to build your own data structure — particularly handy for lazy sequences. However one common niggle is that if the iterator obtains a sequence of things it wants to include in its returned sequence, it has to explicitly traverse that sequence yielding them one at a time. A place this often turns up is when the iterator calls itself recursively, for example when traversing a hierarchy. For example, consider an iterator that gets all the files in or below a specified directory:

public static IEnumerable<string> FilesBelow(string directory)
{
  foreach (var file in Directory.EnumerateFiles(directory))
  {
    yield return file;
  }
  foreach (var subdir in Directory.EnumerateDirectories(directory))
  {
    // yield return FilesBelow(subdir);  // won't compile
    foreach (var file in FilesBelow(subdir))
    {
      yield return file;
    }
  }
}

Note the extra foreach loop over the results of the recursive call.

F# has something similar to iterators, which it calls sequence expressions. A sequence expression is introduced by the term seq, and similar to C# it uses the term yield to produce values:

seq { for n in 1 .. 10 do yield n * n }  // yields 1, 4, 9 ... 81, 100

(You can use -> as a shorthand for do yield here, but I’ve spelled it out explicitly because of what’s coming next.)

Like a C# iterator, a F# sequence expression can call functions which return sequences and yield up the results. We can therefore rewrite our C# directory flattening function like this:

let rec filesBelow directory =
  seq {
    for f in Directory.EnumerateFiles(directory) do yield f
    for d in Directory.EnumerateDirectories(directory) do
      for f in (filesBelow d) do
        yield f
  }

Unlike C#, however, F# sequence expressions do have a special keyword for yielding an entire sequence. That keyword is yield!, pronounced yield-bang. yield! allows us to tighten up our recursive iterator nicely:

let rec filesBelow directory =
  seq {
    for f in Directory.EnumerateFiles(directory) do yield f
    for d in Directory.EnumerateDirectories(directory) do yield! (filesBelow d)
  }