首页 文章

类似的python groupby在haskell

提问于
浏览 次
2

在python中有groupby函数 .

它的类型可以用像这样的haskell表示 groupby :: a->b->[a]->[(b, [a])] 因为需要对数据进行排序，我们可以将它的运行时间视为 O(n*log(n)) .

我可能不是唯一一个对此不满意的人，所以我发现这个library这个groupby的实现需要两次传递输入序列 . 所以我认为它的运行时间是 O(n) ，但正如它在文档中所说的那样，它不会传递密钥，它需要通过序列传递以从项目中收集所有唯一键 .

所以我想，引用Raymond Hetttinger

必须有更好的方法！

所以我写了这个

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) .

我试过haskell模拟这个功能，并没有找到任何 .

是否可以在haskell中写这样的东西？如果是，请显示解决方案，如果没有，请解释原因 .

python haskell iterator lazy-sequences

1 回答

  • 0

    如果我理解正确，你想要的类型

    (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元素中获取）和原始值列表的对 . 我们可以安全地使用 head ，因为 groupBy 永远不会给出一个空的子列表 .

    回复于

相关问题