Аналог группы python в haskell

Question

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

В случае, если вы не знакомы с питоном идея очень проста. Создать изменяемый словарь key -> queue of elements Попробуйте взять следующий элемент последовательности и его значение ключа. Если последовательность не пуста, добавьте это значение в очередь групп в соответствии с его ключом. Если мы не увидели, что этот ключ дает пару (ключевая, итерируемая группа), последняя будет принимать ключи либо из буфера, либо из последовательности. Если мы уже видели это, этот ключ больше ничего не делает и цикл.

Если последовательность завершена, это означает, что все ее элементы уже либо помещены в буферы (и, возможно, потреблены). Если буферы не пусты, мы перебираем их и получаем пары переименования (ключевые, итерируемые).

Я уже тестировал его и его работы. И это действительно лениво (это означает, что это не будет иметь никакого значения от последовательности, пока потребитель не попросит об этом), и это время работы должно быть O(n).

Я пробовал использовать haskell аналог этой функции и не нашел.

Можно ли написать такую ​​вещь в haskell? Если да, пожалуйста, покажите решение, если нет, то объясните, почему.

Answer 1

Если я понимаю правильно, тип вы хотите

(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 никогда не дает пустой подписок.