Есть ли какой-то оператор Ord в списках в haskell?

Question

Я хотел бы сделать набор разностей между 2 целыми списками, которые позволяют повторения в haskell.

Таким образом, в случае наличия [1,2,1,4,3] [1,2,4], разница будет [1,3]

В настоящее время я могу сделать это с помощью обычного \\ оператора listA \\ listB.

Но проблема в том, что это слишком медленно. Поскольку целые числа находятся в группе ord, это можно сделать быстрее.

Я знаю модуль Data.Multiset, который будет делать это быстрее, но есть ли способ сделать это по спискам без модуля Data.Multiset?

Answer 1

Как целые числа в группе ордеров, это можно сделать быстрее.

Да, но для этого требуется построение отсортированного индекса. И это в значительной степени то, что делает Data.Multiset. Разумеется, вы могли бы написать операцию, которая делает это вручную, но к тому времени вы бы действительно переопределили Multiset.

Answer 2

Как я не мог использовать Data.MultiSet Мне нужно было реализовать собственное решение через списки, поэтому я отправлю решение.

Для того, чтобы получить разницу в набор из двух списков с repetitons, мы в первую очередь необходимо сгруппировать цифры вместе, чтобы получить количество повторений каждого номера:

tupleGroup [] _ = [] 
tupleGroup (hd:tl) (x, y) 
    | hd == x = (x, succ y) : tupleGroup tl (x, succ y) 
    | otherwise = (hd, 1) : tupleGroup tl (hd, 1) 

group' [] = [] 
group' (hd:tl) = tupleGroup tl (hd, 1) 

Для вызова функции помощника group 'нам сначала нужно отсортировать список, так как tupleGroup нужен отсортированный список.

Следующая функция является функцией разности, в которых мы поставляем сгруппированные списки:

difference [] [] = [] 
difference (hd:tl) [] = fst hd : difference tl [] 
difference [] (hd:tl) = [] 
difference (hd1:tl1) (hd2:tl2) 
    | x1 == x2 && y1 > y2 = x1 : difference tl1 tl2 
    | x1 == x2 = difference tl1 tl2 
    | x1 < x2 = x1 : difference tl1 (hd2:tl2) 
    | otherwise = difference (hd1:tl1) tl2 
    where 
    x1 = fst hd1 
    x2 = fst hd2 
    y1 = snd hd1 
    y2 = snd hd2 

функция возвращает список всех чисел, которые Отсчет повторений больше в первом списке, чем в второй.