Count 在 Python 中延迟运行 translate from Haskell

Question

我正在尝试编写一个生成器函数（或实现等效函数），它在 Python 中采用可迭代的 xs 并计算“运行”。（这是 Bird 在 Thinking Functionally with Haskell 中的一个问题，我想使用 Python 的惰性特征将其翻译成 Python。）所以

list(iter(count_runs(['a', 'a', 'b', 'c', 'a', 'd', 'd'])))
# => [(2, 'a'), (1, 'b'), (1, c'), (1, 'a'), (2, 'd')]

在Haskell中是

countRuns :: [a] -> [(Int, a)]
countRuns [] = []
countRuns x:xs = (1 + length us, x):countRuns vs
               where us, vs = span (==x) xs

在Python中，我想写一些类似

的东西

from itertools import takewhile, dropwhile

def count_runs(xs):
  # get first element x of xs, if it exists
  us, vs = (takewhile(lambda y: y==x, xs), 
            dropwhile(lambda y: y==x, xs))
  yield (1 + len(list(us)), x)
  yield from count_runs(vs)

但问题是 vs 已经是一个迭代器，所以如果我在下一次递归中调用 takewhile 和 dropwhile 我会运行遇到麻烦. （当我在下一次递归中调用 list(takewhile(..., xs)) 时，它也会去掉 dropwhile(..., xs) 的第一个元素，因为它们都在查看同一个迭代器。

如何解决这个问题，获取第二行第一个元素的正确方法是什么？

Answer 1

span 和 takewhile 之间的显着差异是 takewhile 消耗第一个非 x 值以确定何时停止产生值。结果，您将丢失输入中的所有单例项；特别是，takewhile 在生成领先的 a 集合时失去了第一个 b。迭代器协议无法查看迭代器的下一个元素，也无法放回它消耗的元素。

相反，您将需要两个独立的迭代器：一个用于 takewhile 以生成所需的前缀，另一个用于删除该前缀以进行递归调用.

def count_runs(xs):
    try:
        x = next(xs)
    except StopIteration:
        return

    t1, t2 = tee(xs)

    us = list(takewhile(lambda y: y == x, t1))
    yield (1 + len(us), x)
    yield from count_runs(dropwhile(lambda y: y == x, t2))

（请注意，itertools 文档在其 recipe section 中将类似于 span 的内容实现为 before_and_after 函数。它不使用 tee ，但我建议您参考实际实施以了解详细信息）。

def before_and_after(xs):
    ...

def count_runs(xs):
    try:
        x = next(xs)
    except StopIteration:
        return

    first, second = before_and_after(lambda y: y == x, xs)
    yield (1 + len(list(first)), x)
    yield from count_runs(second)

)

但是，itertools.groupby 已经为您完成了大部分工作。

def count_runs(xs):
    yield from ((len(list(v)), k) for k, v in groupby(xs))

Count 在 Python 中延迟运行 translate from Haskell

Count runs lazily in Python translate from Haskell

python

haskell

generator

code-translation

lazy-sequences