функция groupBy, которая группирует несмежные элементы

Question

Функция groupBy группирует элементы списка, когда они равны согласно определенному пользователем предикату, и когда они находятся рядом в списке.Есть ли функция для группировки элементов без учета смежности?

Я имею дело с полиномами трех переменных.Вот пример такого многочлена, записанного в виде суммы одночленов:

p = (M (Monomial {coefficient = 1.0, powers = (1,0,0)}) :+: M (Monomial {coefficient = 1.0, powers = (0,1,0)})) :+: M (Monomial {coefficient = 1.0, powers = (1,0,0)})

Это означает, что p = 1.0 * x^1y^0z^0 + 1.0 * x^0y^1z^0 + 1.0 * x^1y^0z^0.Первое слагаемое и третье слагаемое суммируются: они имеют одинаковые powers, а затем мы можем добавить их и получить 2.0 * x^1y^0z^0.Моя цель - сделать это дополнение, чтобы упростить p.

У меня есть функция, которая преобразует такой p в список суммированных мономов:

>> toListOfMonomials p
[M (Monomial {coefficient = 1.0, powers = (1,0,0)}),M (Monomial {coefficient = 1.0, powers = (0,1,0)}),M (Monomial {coefficient = 1.0, powers = (1,0,0)})]

Я хочу сгруппировать мономы, которые имеют одинаковые powers.Если я сделаю

groupBy ((==) `on` getPowers)
        (toListOfMonomials p)

, то два M (Monomial {coefficient = 1.0, powers = (1,0,0)}) не будут сгруппированы, потому что они не смежны.

Решение состоит в сортировке списка по полномочиям перед использованием groupBy.Таким образом, два (или более) монома с одинаковым powers являются смежными в отсортированном списке.Чтобы определить порядок степеней (powers - это триплет целых чисел), я сначала определяю функцию сопряжения Кантора:

cantorPairing :: (Int, Int) -> Int
cantorPairing (k1,k2) = (k1+k2)*(k1+k2+1) + 2*k2

cantorPairing' :: (Int, Int, Int) -> Int
cantorPairing' (k1,k2,k3) = cantorPairing(cantorPairing(k1,k2),k3)

, затем я могу сравнить два powers, сравнивая их значения в Канторефункция сопряжения:

groupBy ((==) `on` getPowers)
        (sortBy (compare `on` (cantorPairing' . getPowers)) (toListOfMonomials p))

Это дает желаемый результат: с этим результатом я могу легко суммировать два монома, имеющие одинаковые powers.

Но это выглядит тяжелым, не так ли?Разве нет функции groupBy, которая группирует также несмежные элементы?Иначе есть ли более быстрый способ достижения желаемого результата?

Answer 1

Пока я не могу представить себе общую функцию groupBy, которая бы работала быстрее, чем O (n ^ 2) времени, но вы можете использовать что-то вроде этого

groupBy2 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy2 = go [] where
  go acc comp [] = acc
  go acc comp (h:t) =
    let (hs, nohs) = partition (comp h) t
    in go ((h:hs):acc) comp nohs

Она работает точно так же, как обычная groupBy, но он объединяет несмежные классы элементов.

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

import qualified Data.Map as M

groupOn :: (Ord b) => (a -> b) -> [a] -> [[a]]
groupOn f =
  let unpack = fmap snd . M.toList
      fld m a = case M.lookup (f a) m of
        Nothing -> M.insert (f a) [a] m
        Just as -> M.insert (f a) (a:as) m
  in unpack . foldl fld M.empty

Это более эффективный эквивалент

groupOn' f = groupBy2 ((==) `on` f)

(упорядочение по модулю)

И, кстати, триплеты и пары уже определили экземпляр Ord, вы можете сравнить их так же, как Int S