使用 "Long zip with" 的惰性 Python 中的树级别

Question

在this关于广度优先遍历的博客post中，Gibbons谈到用“long zip with”函数实现BFT

lzw :: (a -> a -> a) -> [a] -> [a] -> [a]
lzw f x:xs y:ys = f x y : lzw f xs ys
lzw _ [] ys = ys
lzw _ xs [] = xs

那么比如说

data Tree a = EmpT | TN a (Tree a) (Tree a)
levels :: Tree a -> [[a]]
levels ET = []
levels (TN x tl tr) = [x] : lzw (++) (levels tl) (levels tr)

My question: My version of levels in Python is working, but my lazy version using generators is not. It's adding an extra [] level at the end. Why?

我认为这种使用生成器的做法和 Python 中的惰性，我认为问题在于我使用 yield、return、[=20 的方式有些不精确=]，等等

错误示例：

>>> my_tree = tree_from_int_segment(10)
>>> 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}

>>> tree_levels(my_tree)

[[5], [2, 8], [1, 4, 7, 9], [0, 3, 6]]

>>> list(tree_levels_lazy(my_tree))

[[5], [2, 8], [1, 4, 7, 9], [0, 3, 6], []]

这是我的代码。提前致谢！

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["val"]
    tl = t["left"]
    tr = t["right"]
    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["val"]
    tl = t["left"]
    tr = t["right"]
    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 {"val": x,
                "left": unfolder(seed_l),
                "right": unfolder(seed_r)}

    return unfolder(init_value)


def tree_from_int_segment(n):
    return unfold_tree(split_list_for_tree, list(range(n)))

Answer 1

由于生成器版本不连接子列表，因此不应生成空列表：

def tree_levels_lazy(t):
    if t is None:
        #yield []  <-- remove this
        return
    ...

使用 "Long zip with" 的惰性 Python 中的树级别

Tree levels in lazy Python using "Long zip with"

python

haskell

tree

itertools

breadth-first-search