在python中有一个groupby函数。
它的类型可以用哈斯克尔表示，就像这样groupby :: a->b->[a]->[(b, [a])]因为它需要对数据进行排序，所以我们可以将其运行时间视为O(n*log(n)).
我可能不是唯一一个对此不满意的人，所以我找到了这个库 这种 groupby 的实现需要对输入序列进行两次传递。所以我认为它的运行时间是O(n)，但正如它在文档中所说，它并不是真的懒惰，因为如果您不将密钥传递给它，它就需要进行传递序列以从项目中收集所有唯一密钥。
所以我想，引用雷蒙德·赫廷格的话
一定有更好的办法！
所以我写了这个
from collections import defaultdict, deque
def groupby(sequence, key=lambda x: x):
buffers = defaultdict(deque)
kvs = ((key(item), item) for item in sequence)
seen_keys = set()
def subseq(k):
while True:
buffered = buffers[k]
if buffered:
yield buffered.popleft()
else:
next_key, value = next(kvs)
buffers[next_key].append(value)
while True:
try:
k, value = next(kvs)
except StopIteration:
for bk, group in buffers.items():
if group and bk not in seen_keys:
yield (bk, group)
raise StopIteration()
else:
buffers[k].append(value)
if k not in seen_keys:
seen_keys.add(k)
yield k, subseq(k)
如果你不熟悉python，这个想法非常简单。 创建可变key -> queue of elements字典 尝试获取序列的下一个元素及其键值。 如果序列不为空，则根据其键将此值添加到组队列中。如果我们还没有看到这个键产生一对(键，可迭代组)，后者将从缓冲区或序列中获取键。如果我们已经看到了这一点，则此键不再执行任何操作并循环。
如果序列结束，则意味着它的所有元素都已经放入缓冲区(并且可能已被使用)。如果缓冲区不为空，我们会迭代它们并生成重命名(键、可迭代)对。
我已经对它及其工作进行了单元测试。而且它真的很懒惰(这意味着在消费者没有要求它之前，它不会从序列中获取任何值)，并且它的运行时间应该O(n)。
我试图模拟这个函数，但没有找到。
有可能用哈斯克尔写这样的东西吗？如果是这样，请出示解决方案，如果没有，请解释原因。
如果我理解正确，您想要的类型是
(a -> k) -> [a] -> [(k, [a])]
也就是说，给定一个键函数和一个项目列表，按键对项目进行分组。
在Haskell中有一个库函数groupBy它做类似的事情。它假定您有一个排序列表，并将满足布尔条件的项目分组到子列表中。我们可以用它来做你想做的事：
import Data.List
import Data.Ord
groupByKey :: (a -> k) -> [a] -> [(k, [a])]
groupByKey keyF xs = map getResult groups
where
keyPairs = map (v -> (keyF v, v)) xs
groups = groupBy (v1 v2 -> fst v1 == fst v2)
$ sortBy (comparing fst) keyPairs
getResult xs = (fst $ head xs, map snd xs)
keyPairs是参数中每个元素的对(key, value)。groups首先使用sortBy将其按键顺序排序，然后将结果分组到共享相同键的子列表中。getResult将子列表转换为包含键(取自 head 元素)和原始值列表的子列表。 我们可以安全地使用headgroupBy因为它永远不会给出空的子列表。