В Haskell у нас есть генераторы списков, такие как:
[x+y | x<-[1,2,3], y<-[1,2,3]]
с которыми мы получаем
[2,3,4,3,4,5,4,5,6]
Возможно ли иметь генератор множеств, который автоматически не добавляет элемент, если он уже находится в списке?
В нашем примере мы получим:
[2,3,4,5,6]
Если да, то как? Если он еще не реализован, как вы его реализуете?
Haskell может это сделать, но не совсем из коробки.
Основная основа заключается в том, что понимание списка также может быть записано как монадическая цепочка привязки, в монаде списка:
Prelude> [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,3,4,5,4,5,6]
Prelude> [1,2,3] >>= \x -> [1,2,3] >>= \y -> return (x+y)
[2,3,4,3,4,5,4,5,6]
... или, с более читаемыми do -syntax (который является синтаксическим сахаром для монадического связывания)
Prelude> do x<-[1,2,3]; y<-[1,2,3]; return (x+y)
[2,3,4,3,4,5,4,5,6]
На самом деле существует языковое расширение, которое также превращает все перечни в синтаксический сахар для такой монадической цепочки. Пример в монаде (ака-писатель):
Prelude> :set -XMonadComprehensions
Prelude> [x+y | x <- ("Hello", 4), y <- ("World", 5)] :: (String, Int)
("HelloWorld",9)
Итак, все, что нам нужно, это установленная монада. Это достаточно разумно, однако Data.Set.Set не является монадой на Hask (категория всех типов Haskell), но только только подкатегория, которая удовлетворяет ограничению Ord (которое необходимо для поиска/избежания дубликатов). Однако в случае наборов существует хак, который позволяет скрыть это ограничение от фактического экземпляра монады; он используется в пакете set-monad. И вуаля:
Prelude Data.Set.Monad> [x+y | x<-fromList[1,2,3], y<-fromList[1,2,3]]
fromList [2,3,4,5,6]
Взлом, который нужен, instance Monad Set стоит дорого. Он работает следующим образом:
{-# LANGUAGE GADTs, RankNTypes #-}
import qualified Data.Set as DS
data Set r where
Prim :: (Ord r => DS.Set r) -> Set r
Return :: a -> Set a
Bind :: Set a -> (a -> Set b) -> Set b
...
Это означает: значение типа Data.Set.Monad.Set Int не содержит конкретного набора целых чисел. Скорее, он содержит абстрактное синтаксическое выражение для вычисления, которое дает результат как результат. Это не очень удобно для производительности, в частности это означает, что значения не будут использоваться совместно. Поэтому не используйте это для больших наборов.
Там лучший вариант: используйте его непосредственно в качестве монады в соответствующей категории (с которой только начинаются упорядочиваемые типы). Это, к сожалению, требует еще большего изгибания языка, но это возможно; Я привел пример в библиотеке с constrained-categories.
Если ваши значения можно поместить в Data.Set.Set (т.е. они находятся в классе Ord), вы можете просто применить Data.Set.toList. Data.Set.fromList Data.Set.toList. Data.Set.fromList в список:
Prelude> import Data.Set
Prelude Data.Set> Data.Set.toList . Data.Set.fromList $ [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,5,6]
Сложностью этого будет O(n log n).
Если тип подчиняется (Eq a, Hashable a), вы можете использовать Data.HashSet почти таким же образом. Средняя сложность - O(n).
Если все, что у вас есть, это Eq, вам нужно пройти с чем-то вроде Data.List.nub:
Prelude> import Data.List
Prelude Data.List> nub [x+y | x<-[1,2,3], y<-[1,2,3]]
[2,3,4,5,6]
но сложность по своей сути квадратична.