title: How do I build an iterator for walking a file tree recursively?
body: <p>I want to lazily consume the nodes of a file tree one by one while sorting the siblings on each level.</p>
  
  <p>In Python, I'd use a synchronous generator:</p>
  
  <pre class="lang-py prettyprint-override"><code>def traverse_dst(src_dir, dst_root, dst_step):
      """
      Recursively traverses the source directory and yields a sequence of (src, dst) pairs;
  
      """
      dirs, files = list_dir_groom(src_dir) # Getting immediate offspring.
  
      for d in dirs:
          step = list(dst_step)
          step.append(d.name)
          yield from traverse_dst(d, dst_root, step)
  
      for f in files:
          dst_path = dst_root.joinpath(step)
          yield f, dst_path
  </code></pre>
  
  <p>In Elixir, a (lazy) stream:</p>
  
  <pre><code>def traverse_flat_dst(src_dir, dst_root, dst_step \\ []) do
    {dirs, files} = list_dir_groom(src_dir) # Getting immediate offspring.
  
    traverse = fn d -&gt;
      step = dst_step ++ [Path.basename(d)]
      traverse_flat_dst(d, dst_root, step)
    end
  
    handle = fn f -&gt;
      dst_path =
        Path.join(
          dst_root,
          dst_step
        )
  
      {f, dst_path}
    end
  
    Stream.flat_map(dirs, traverse)
    |&gt; Stream.concat(Stream.map(files, handle))
  end
  </code></pre>
  
  <p>One can see some language features addressing recursion: <code>yield from</code> in Python, <code>flat_map</code> in Elixir; the latter looks like a classic functional approach.</p>
  
  <p>It looks like whatever is lazy in Rust, it's always an iterator. How am I supposed to do more or less the same in Rust?</p>
  
  <p>I'd like to preserve the structure of my recursive function with <code>dirs</code> and <code>files</code> as vectors of paths (they are optionally sorted and filtered).</p>
  
  <p>Getting <code>dirs</code> and <code>files</code> is already implemented to my liking:</p>
  
  <pre><code>fn folders(dir: &amp;Path, folder: bool) -&gt; Result&lt;Vec&lt;PathBuf&gt;, io::Error&gt; {
      Ok(fs::read_dir(dir)?
          .into_iter()
          .filter(|r| r.is_ok())
          .map(|r| r.unwrap().path())
          .filter(|r| if folder { r.is_dir() } else { !r.is_dir() })
          .collect())
  }
  
  fn list_dir_groom(dir: &amp;Path) -&gt; (Vec&lt;PathBuf&gt;, Vec&lt;PathBuf&gt;) {
      let mut dirs = folders(dir, true).unwrap();
      let mut files = folders(dir, false).unwrap();
      if flag("x") {
          dirs.sort_unstable();
          files.sort_unstable();
      } else {
          sort_path_slice(&amp;mut dirs);
          sort_path_slice(&amp;mut files);
      }
      if flag("r") {
          dirs.reverse();
          files.reverse();
      }
      (dirs, files)
  }
  </code></pre>
  
  <p><code>Vec&lt;PathBuf</code> can be iterated as is, and there is standard <a href="https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.flat_map" rel="nofollow noreferrer">flat_map</a> method. It should be possible to implement Elixir style, I just can't figure it out yet.</p>
  
  <p>This is what I already have. Really <em>working</em> (<code>traverse_flat_dst(&amp;SRC, [].to_vec());</code>), I mean:</p>
  
  <pre><code>fn traverse_flat_dst(src_dir: &amp;PathBuf, dst_step: Vec&lt;PathBuf&gt;) {
      let (dirs, files) = list_dir_groom(src_dir);
  
      for d in dirs.iter() {
          let mut step = dst_step.clone();
          step.push(PathBuf::from(d.file_name().unwrap()));
          println!("d: {:?}; step: {:?}", d, step);
          traverse_flat_dst(d, step);
      }
      for f in files.iter() {
          println!("f: {:?}", f);
      }
  }
  </code></pre>
  
  <p>What I want (<em>not</em> yet working!):</p>
  
  <pre><code>fn traverse_flat_dst_iter(src_dir: &amp;PathBuf, dst_step: Vec&lt;PathBuf&gt;) {
      let (dirs, files) = list_dir_groom(src_dir);
  
      let traverse = |d| {
          let mut step = dst_step.clone();
          step.push(PathBuf::from(d.file_name().unwrap()));
          traverse_flat_dst_iter(d, step);
  
      };
      // This is something that I just wish to be true!
      flat_map(dirs, traverse) + map(files)    
  }
  </code></pre>
  
  <p>I want this function to deliver one long flat iterator of files, in the spirit of the Elixir solution. I just can't yet cope with the necessary return types and other syntax. I really hope to be clear enough this time.</p>
  
  <p>What I managed to compile and run (meaningless, but the signature is what I actually want):</p>
  
  <pre><code>fn traverse_flat_dst_iter(
      src_dir: &amp;PathBuf,
      dst_step: Vec&lt;PathBuf&gt;,
  ) -&gt; impl Iterator&lt;Item = (PathBuf, PathBuf)&gt; {
      let (dirs, files) = list_dir_groom(src_dir);
  
      let _traverse = |d: &amp;PathBuf| {
          let mut step = dst_step.clone();
          step.push(PathBuf::from(d.file_name().unwrap()));
          traverse_flat_dst_iter(d, step)
      };
      files.into_iter().map(|f| (f, PathBuf::new()))
  }
  </code></pre>
  
  <p>What I'm still lacking:</p>
  
  <pre><code>fn traverse_flat_dst_iter(
      src_dir: &amp;PathBuf,
      dst_step: Vec&lt;PathBuf&gt;,
  ) -&gt; impl Iterator&lt;Item = (PathBuf, PathBuf)&gt; {
      let (dirs, files) = list_dir_groom(src_dir);
  
      let traverse = |d: &amp;PathBuf| {
          let mut step = dst_step.clone();
          step.push(PathBuf::from(d.file_name().unwrap()));
          traverse_flat_dst_iter(d, step)
      };
      // Here is a combination amounting to an iterator,
      // which delivers a (PathBuf, PathBuf) tuple on each step.
      // Flat mapping with traverse, of course (see Elixir solution).
      // Iterator must be as long as the number of files in the tree.
      // The lines below look very close, but every possible type is mismatched :(
      dirs.into_iter().flat_map(traverse)
          .chain(files.into_iter().map(|f| (f, PathBuf::new())))
  
  }
  </code></pre>