title: Tree levels in lazy Python using "Long zip with"
body: <p>In <a href="https://patternsinfp.wordpress.com/2015/03/05/breadth-first-traversal/" rel="nofollow noreferrer">this</a> blog post about breadth-first traversal, Gibbons talks about implementing BFT with &quot;long zip with&quot; function</p>
  <pre class="lang-hask prettyprint-override"><code>lzw :: (a -&gt; a -&gt; a) -&gt; [a] -&gt; [a] -&gt; [a]
  lzw f x:xs y:ys = f x y : lzw f xs ys
  lzw _ [] ys = ys
  lzw _ xs [] = xs
  </code></pre>
  <p>Then for instance</p>
  <pre class="lang-hask prettyprint-override"><code>data Tree a = EmpT | TN a (Tree a) (Tree a)
  levels :: Tree a -&gt; [[a]]
  levels ET = []
  levels (TN x tl tr) = [x] : lzw (++) (levels tl) (levels tr)
  </code></pre>
  <blockquote>
  <p><strong>My question:</strong> My version of <code>levels</code> in Python is working, but my lazy version using generators is not. It's adding an extra <code>[]</code> level at the end. Why?</p>
  </blockquote>
  <p>I consider this practice for using generators and laziness in Python, and I think the problem is some imprecision in how I'm using <code>yield</code>, <code>return</code>, <code>itertools.zip_longest</code>, etc.</p>
  <p>An example of what's going wrong:</p>
  <pre class="lang-py prettyprint-override"><code>&gt;&gt;&gt; my_tree = tree_from_int_segment(10)
  &gt;&gt;&gt; pprint(my_tree)
  
  {'left': {'left': {'left': {'left': None, 'right': None, 'val': 0},
                     'right': None,
                     'val': 1},
            'right': {'left': {'left': None, 'right': None, 'val': 3},
                      'right': None,
                      'val': 4},
            'val': 2},
   'right': {'left': {'left': {'left': None, 'right': None, 'val': 6},
                      'right': None,
                      'val': 7},
             'right': {'left': None, 'right': None, 'val': 9},
             'val': 8},
   'val': 5}
  
  &gt;&gt;&gt; tree_levels(my_tree)
  
  [[5], [2, 8], [1, 4, 7, 9], [0, 3, 6]]
  
  &gt;&gt;&gt; list(tree_levels_lazy(my_tree))
  
  [[5], [2, 8], [1, 4, 7, 9], [0, 3, 6], []]
  </code></pre>
  <p>Here's my code. Thanks in advance!</p>
  <pre class="lang-py prettyprint-override"><code>from itertools import islice
  from itertools import zip_longest
  
  
  def conditional_apply(g, x, y):
      if x is None:
          return y
      elif y is None:
          return x
      else:
          return g(x, y)
  
  
  def long_zip_with(f, xs, ys):
      zs = list(zip_longest(xs, ys))
      return [conditional_apply(f, x, y) for x, y in zs]
  
  
  def long_zip_with_lazy(f, xs, ys):
      zs = zip_longest(xs, ys)
      for x, y in zs:
          yield conditional_apply(f, x, y)
  
  
  def tree_levels(t):
      if t is None:
          return []
  
      a = t[&quot;val&quot;]
      tl = t[&quot;left&quot;]
      tr = t[&quot;right&quot;]
      return [[a]] + long_zip_with(list.__add__, tree_levels(tl), tree_levels(tr))
  
  
  def tree_levels_lazy(t):
      if t is None:
          yield []
          return
  
      a = t[&quot;val&quot;]
      tl = t[&quot;left&quot;]
      tr = t[&quot;right&quot;]
      first_level = [a]
  
      yield first_level
      for level in long_zip_with_lazy(list.__add__, tree_levels_lazy(tl), tree_levels_lazy(tr)):
          yield level
  
  # Rest is just code for building a tree to work with
  
  
  def split_at(k, xs):
      it = iter(xs)
      l = list(islice(it, k))
      r = list(it)
      return l, r
  
  
  def split_list_for_tree(xs):
      if not xs:
          return None
      n = len(xs)
      xsl_p, xsr = split_at(n//2 + 1, xs)
      x = xsl_p.pop()
      return x, xsl_p, xsr
  
  
  def unfold_tree(seed_to_sprout, init_value):
  
      def unfolder(seed):
          sprout = seed_to_sprout(seed)
          if sprout is None:
              return None
          x, seed_l, seed_r = sprout
          return {&quot;val&quot;: x,
                  &quot;left&quot;: unfolder(seed_l),
                  &quot;right&quot;: unfolder(seed_r)}
  
      return unfolder(init_value)
  
  
  def tree_from_int_segment(n):
      return unfold_tree(split_list_for_tree, list(range(n)))
  
  </code></pre>