Count在从Haskell转换过来的Python中延迟运行

Question

我试图写一个生成器函数(或实现等效的)，它在Python中接受一个可迭代的xs，并计算"运行"。(这是Bird在Thinking functional 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在产生as的先导集时失去了第一个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部分中作为before_and_after函数实现了与span类似的东西。它不使用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))