есть ли объединение и пересечение реализации Haskell Prelude?

Question

Есть ли в стандартных функциях Prelude, которые реализуют объединение и пересечение множеств?

union      :: (Eq a) => [a] -> [a] -> [a]
intersect  :: (Eq a) => [a] -> [a] -> [a]

Если нет, то может кто-нибудь сказать, эффективна ли моя реализация (используйте лень и функцию прелюдии)

unionSet :: (Eq a) => [a] -> [a] -> [a]
unionSet as bs = foldl (\xs y -> if elem y xs then xs else xs ++ [y]) as bs

intersectSet :: (Eq a) => [a] -> [a] -> [a]
intersectSet as bs = let ns = [ a | a <- as, elem a bs] in [ b | b <- bs, elem b ns]

Answer 1

Базовая библиотека предоставляет список версий, как указывает camccann.Если вы хотите что-то более эффективное, рассмотрите Data.Set , который обеспечивает:

union :: Ord a => Set a -> Set a -> Set a

intersection :: Ord a => Set a -> Set a -> Set a

со сложностью O (n + m) .

Answer 2

Функции union и intersect имеются в списках стандартных библиотек, расположенных в Data.List, но не в самом Prelude.

Что касается эффективности, я собираюсь сказать «нет» всем вышеперечисленным, как вашей, так и стандартной библиотеке.На самом деле, ни один способ не может быть эффективным в списке операций с ограничением Eq.Тем не менее, вы все равно можете найти реализацию в Data.List информативной - см. Ссылки выше, которые я указал непосредственно на соответствующий источник.

Редактировать - ВкратцеВ дополнении ради потомков, обязательно посмотрите ответ Дона о том, что вы на самом деле хотите использовать для этой цели, а не более узкий вопрос "существуют ли эти функции вообще".

Answer 3

Вы часто найдете реализации того, что вам нужно, ища подписи. Просто оставьте свою подпись в Hoogle ( haskell.org/hoogle/…).