在不列出每个块的情况下解析可迭代对象

Question

假设我想实现 Python 可迭代的拆分，而不列出每个块，类似于 itertools.groupby，其块是惰性的。但我想在比键相等更复杂的条件下进行。所以更像是一个解析器。

例如，假设我想在一个可迭代的整数中使用奇数作为分隔符。喜欢more_itertools.split_at(lambda x: x % 2 == 1, xs)。（但是 more_itertools.split_at 列出了每个块。）

在解析器组合器语言中，这可能被称为 sepBy1(odd, many(even))。 Haskell 中有 Parsec、pipes-parse 和 pipes-group 库可以解决此类问题。例如，从 Pipes.Group 编写一个类似 itertools.groupby 的 groupsBy' 版本（参见 here）就足够了，也很有趣。

可能会有一些聪明的柔术 itertools.groupby，也许应用 itertools.pairwise，然后 itertools.groupby，然后再回到单一元素。

我想我可以自己将它写成一个生成器，但是在 Python（下面）中写 itertools.groupby 已经很复杂了。也不容易推广。

似乎应该有更普遍的东西，比如为任何类型的流编写解析器和组合器的相对轻松的方式。

# From https://docs.python.org/3/library/itertools.html#itertools.groupby
# groupby() is roughly equivalent to:
class groupby:
    # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
    # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = object()
    def __iter__(self):
        return self
    def __next__(self):
        self.id = object()
        while self.currkey == self.tgtkey:
            self.currvalue = next(self.it)    # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey, self.id))
    def _grouper(self, tgtkey, id):
        while self.id is id and self.currkey == tgtkey:
            yield self.currvalue
            try:
                self.currvalue = next(self.it)
            except StopIteration:
                return
            self.currkey = self.keyfunc(self.currvalue)

Answer 1

这里有几个简单的迭代器分离器，是我无聊写的。我不认为它们特别深刻，但也许它们会以某种方式提供帮助。

我没有花很多时间思考有用的界面、优化或实现多重交互 sub-features。如果需要，可以添加所有这些内容。

这些基本都是仿照itertools.groupby，界面可以说有点怪。这是 Python 实际上不是函数式编程语言的结果。 Python 的生成器（以及其他实现迭代器协议的对象）是有状态的，没有用于保存和恢复生成器状态的工具。所以函数做 return 一个迭代器，它连续生成迭代器，从原始迭代器产生值。但是 returned 迭代器共享底层迭代器，它是传递给原始调用的迭代器，这意味着当您推进外部迭代器时，当前内部迭代器中任何未使用的值都会被丢弃，恕不另行通知。

有（相当昂贵的）方法可以避免丢弃值，但由于最明显的方法 --listifying-- 从一开始就被排除在外，尽管很尴尬，我还是使用了 groupby 界面准确记录行为。可以用 itertools.tee 包装内部迭代器以使原始迭代器独立，但代价类似于（或可能略大于）列表化。它仍然需要在下一个 sub-iterator 开始之前完全生成每个 sub-iterator，但它不需要在开始使用值之前完全生成 sub-iterator。

为了简单起见（据我说:-)），我将这些函数实现为生成器而不是对象，就像 itertools 和 more_itertools 一样。外部生成器生成每个连续的子迭代器，然后在生成下一个子迭代器之前收集并丢弃其中的所有剩余值 [注 1]。我想大多数时候子迭代器会在外循环尝试刷新它之前完全耗尽，所以额外的调用会有点浪费，但它比你为 itertools.groupby.[=33 引用的代码简单=]

仍然有必要从子迭代器反馈原始迭代器已耗尽的事实，因为这不是您可以询问迭代器的事情。我使用 nonlocal 声明在外部和内部生成器之间共享状态。在某些方面，像 itertools.groupby 那样在对象中维护状态可能更灵活，甚至可能被认为更 Pythonic，但 nonlocal 对我有用。

我实现了 more_itertools.split_at（没有 maxsplits 和 keep_separator 选项）并且我认为等同于 Pipes.Groups.groupBy'，重命名为 split_between 以表明如果满足某些条件，它将在两个连续元素之间拆分。

请注意，split_between 总是在第一个子迭代器运行请求之前从提供的迭代器强制第一个值。其余值是延迟生成的。我尝试了几种方法来延迟第一个对象，但最终我选择了这个设计，因为它简单得多。结果是 split_at 不执行初始强制，总是 return 至少有一个子迭代器，即使提供的参数为空，而 split_between 则不然。我必须尝试这两种方法来解决一些实际问题，才能决定我更喜欢哪个界面；如果您有偏好，一定要表达出来（但不保证会改变）。

from collections import deque

def split_at(iterable, pred=lambda x:x is None):
    '''Produces an iterator which returns successive sub-iterations of 
       `iterable`, delimited by values for which `pred` returns
       truthiness. The default predicate returns True only for the
       value None.

       The sub-iterations share the underlying iterable, so they are not 
       independent of each other. Advancing the outer iterator will discard
       the rest of the current sub-iteration.

       The delimiting values are discarded.
    '''

    done = False
    iterable = iter(iterable)

    def subiter():
        nonlocal done
        for value in iterable:
            if pred(value): return
            yield value
        done = True

    while not done:
        yield (g := subiter())
        deque(g, maxlen=0)

def split_between(iterable, pred=lambda before,after:before + 1 != after):
    '''Produces an iterator which returns successive sub-iterations of 
       `iterable`, delimited at points where calling `pred` on two
       consecutive values produces truthiness. The default predicate
       returns True when the two values are not consecutive, making it
       possible to split a sequence of integers into contiguous ranges.

       The sub-iterations share the underlying iterable, so they are not 
       independent of each other. Advancing the outer iterator will discard
       the rest of the current sub-iteration.
    '''
    iterable = iter(iterable)

    try:
        before = next(iterable)
    except StopIteration:
        return

    done = False

    def subiter():
        nonlocal done, before
        for after in iterable:
            yield before
            prev, before = before, after
            if pred(prev, before):
                return

        yield before
        done = True

    while not done:
        yield (g := subiter())
        deque(g, maxlen=0)

备注

collections.deque(g, maxlen=0) 是目前丢弃迭代器剩余值的最有效方法，尽管它看起来有点神秘。感谢 more_itertools 指出该解决方案，以及用于计算生成器生成的对象数量的相关表达式：
```
cache[0][0] if (cache := deque(enumerate(it, 1), maxlen=1)) else 0
```
虽然我并不是要将上述怪事归咎于 more_itertools。（他们用 if 语句来做到这一点，而不是海象。）

在不列出每个块的情况下解析可迭代对象

Parsing an iterable without listifying each chunk

python

parsing

itertools

haskell-pipes

more-itertools

备注