{-| Module  : WeakSets
Description : Homogeneous sets are sets which can contain only one type of values. They are more flexible than Data.Set because they do not require the objects contained to be orderable.
Copyright   : Guillaume Sabbagh 2022
License     : LGPL-3.0-or-later
Maintainer  : guillaumesabbagh@protonmail.com
Stability   : experimental
Portability : portable

Homogeneous sets are sets which can contain only one type of values.

They are more flexible than Data.Set because they do not require the objects contained to be orderable.

The datatype only assumes its components are equatable, it is therefore slower than the Data.Set datatype.

We use this datatype because most of the datatypes we care about are not orderable.

Inline functions related to homogeneous sets are written between pipes @|@.

Function names should not collide with Prelude but should collide with Data.Set.
-}

module Data.WeakSets.HomogeneousSet
(
    -- * Set datatype and smart constructor

    Set, -- abstract type, the smart constructor is `set`

    set, -- the smart constructor for `Set`

    -- * Set related functions

    setToList,
    isIncludedIn,
    cardinal,
    isIn,
    (|&|),
    (|||),
    (|*|),
    (|+|),
    (|-|),
    (|^|),
    powerSet,
    filterSet,
    -- * Functions to work with `Maybe`

    setToMaybe,
    maybeToSet,
    catMaybesToSet,
    mapMaybeToSet,
    -- * Function datatype and smart constructor

    AssociationList(..),
    Function, -- abstract type, the smart constructor is `function`

    function, -- the smart constructor for `Function`

    -- * Function related functions

    functionToSet,
    domain,
    image,
    (|$|),
    (|!|),
    findWithDefault,
    (|.|),
    memorizeFunction,
)
where
    import              Data.List               (intercalate, nub, nubBy, intersect, union, (\\), subsequences)
    import              Data.Maybe
    
    -- | A homogeneous set is a list of values.

    --

    -- The only differences are that we don't want duplicate elements and we don't need the order of the list elements.

    --

    -- To force these constraints, the `Set` constructor is abstract and is not exported. The only way to construct a set is to use the smart constructor `set` which ensures the previous conditions.

    data Set a = Set [a]
    
    -- | The smart constructor of sets. This is the only way of instantiating a `Set`.

    --

    -- If several elements are equal, they are kept until the user wants a list back.

    set :: [a] -> Set a
    set :: forall a. [a] -> Set a
set [a]
xs = [a] -> Set a
forall a. [a] -> Set a
Set [a]
xs
    
    instance (Show a) => Show (Set a) where
        show :: Set a -> String
show (Set [a]
xs) = String
"(set "String -> ShowS
forall a. [a] -> [a] -> [a]
++[a] -> String
forall a. Show a => a -> String
show [a]
xsString -> ShowS
forall a. [a] -> [a] -> [a]
++String
")"
    
    -- | Return a boolean indicating if a `Set` is included in another one.

    isIncludedIn :: (Eq a) => Set a -> Set a -> Bool
    (Set []) isIncludedIn :: forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
_ = Bool
True
    (Set (a
x:[a]
xs)) `isIncludedIn` (Set [a]
ys)
        | a
x a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
ys = ([a] -> Set a
forall a. [a] -> Set a
Set [a]
xs) Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` ([a] -> Set a
forall a. [a] -> Set a
Set [a]
ys)
        | Bool
otherwise = Bool
False
    
    instance (Eq a) => Eq (Set a) where
        Set a
x == :: Set a -> Set a -> Bool
== Set a
y = Set a
x Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
y Bool -> Bool -> Bool
&& Set a
y Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
x
        
    instance (Eq a) => Semigroup (Set a) where
        (Set [a]
xs) <> :: Set a -> Set a -> Set a
<> (Set [a]
ys) = [a] -> Set a
forall a. [a] -> Set a
set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
ys
        
    instance (Eq a) => Monoid (Set a) where
        mempty :: Set a
mempty = [a] -> Set a
forall a. [a] -> Set a
Set []
    
    instance Foldable Set where
        foldr :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
f b
d (Set [a]
xs) = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
d [a]
xs

    instance Functor Set where
        fmap :: forall a b. (a -> b) -> Set a -> Set b
fmap a -> b
f (Set [a]
xs) = [b] -> Set b
forall a. [a] -> Set a
Set ([b] -> Set b) -> [b] -> Set b
forall a b. (a -> b) -> a -> b
$ a -> b
f (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a]
xs
    
    instance Applicative Set where
        pure :: forall a. a -> Set a
pure a
x = [a] -> Set a
forall a. [a] -> Set a
Set [a
x]
        <*> :: forall a b. Set (a -> b) -> Set a -> Set b
(<*>) (Set [a -> b]
fs) (Set [a]
xs) = [b] -> Set b
forall a. [a] -> Set a
Set ([b] -> Set b) -> [b] -> Set b
forall a b. (a -> b) -> a -> b
$ [a -> b]
fs [a -> b] -> [a] -> [b]
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> [a]
xs

    instance Monad Set where
        >>= :: forall a b. Set a -> (a -> Set b) -> Set b
(>>=) (Set [a]
xs) a -> Set b
f = [b] -> Set b
forall a. [a] -> Set a
Set ([b] -> Set b) -> [b] -> Set b
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> (a -> [b]) -> [b]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (Set b -> [b]
forall a. Set a -> [a]
unsafeSetToList(Set b -> [b]) -> (a -> Set b) -> a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> Set b
f)
    
    -- | Transform a `Set` back into a list, the list returned does not have duplicate elements, the order of the original list holds.

    setToList :: (Eq a) => Set a -> [a]
    setToList :: forall a. Eq a => Set a -> [a]
setToList (Set [a]
xs) = [a] -> [a]
forall a. Eq a => [a] -> [a]
nub [a]
xs
    
    -- | Gives the underlying list of a set without removing duplicates, this function is not exported.

    unsafeSetToList :: Set a -> [a]
    unsafeSetToList :: forall a. Set a -> [a]
unsafeSetToList (Set [a]
xs) = [a]
xs
    
    -- | Size of a set.

    cardinal :: (Eq a) => Set a -> Int
    cardinal :: forall a. Eq a => Set a -> Int
cardinal = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length([a] -> Int) -> (Set a -> [a]) -> Set a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList
    
    -- | Return wether an element is in a set.

    isIn :: (Eq a) => a -> Set a -> Bool
    isIn :: forall a. Eq a => a -> Set a -> Bool
isIn a
x = (a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
elem a
x)([a] -> Bool) -> (Set a -> [a]) -> Set a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
    
    -- | Return the intersection of two sets.

    (|&|) :: (Eq a) => Set a -> Set a -> Set a
    |&| :: forall a. Eq a => Set a -> Set a -> Set a
(|&|) (Set [a]
xs) (Set [a]
ys) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
`intersect` [a]
ys
    
    -- | Return the union of two sets.

    (|||) ::  Set a -> Set a -> Set a
    ||| :: forall a. Set a -> Set a -> Set a
(|||) (Set [a]
xs) (Set [a]
ys) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys
    
    -- | Return the cartesian product of two sets.

    (|*|) ::  Set a -> Set b -> Set (a,b)
    |*| :: forall a b. Set a -> Set b -> Set (a, b)
(|*|) (Set [a]
xs) (Set [b]
ys) = [(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set ([(a, b)] -> Set (a, b)) -> [(a, b)] -> Set (a, b)
forall a b. (a -> b) -> a -> b
$ [(a
x,b
y) | a
x <- [a]
xs, b
y <- [b]
ys]
    
    -- | Return the disjoint union of two sets.

    (|+|) :: Set a -> Set b -> Set (Either a b)
    |+| :: forall a b. Set a -> Set b -> Set (Either a b)
(|+|) (Set [a]
xs) (Set [b]
ys) = [Either a b] -> Set (Either a b)
forall a. [a] -> Set a
Set ([Either a b] -> Set (Either a b))
-> [Either a b] -> Set (Either a b)
forall a b. (a -> b) -> a -> b
$ [a -> Either a b
forall a b. a -> Either a b
Left a
x | a
x <- [a]
xs] [Either a b] -> [Either a b] -> [Either a b]
forall a. [a] -> [a] -> [a]
++ [b -> Either a b
forall a b. b -> Either a b
Right b
y | b
y <- [b]
ys]
    
    -- | Returns the cartesian product of a set with itself n times.

    (|^|) :: (Num a, Eq a) => Set a -> a -> Set [a]
    |^| :: forall a. (Num a, Eq a) => Set a -> a -> Set [a]
(|^|) Set a
_ a
0 = [[a]] -> Set [a]
forall a. [a] -> Set a
Set [[]]
    (|^|) Set a
s a
n = (:) (a -> [a] -> [a]) -> Set a -> Set ([a] -> [a])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a
s Set ([a] -> [a]) -> Set [a] -> Set [a]
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (Set a
s Set a -> a -> Set [a]
forall a. (Num a, Eq a) => Set a -> a -> Set [a]
|^| (a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1))
    
    -- | Return the difference of two sets.

    (|-|) :: (Eq a) => Set a -> Set a -> Set a
    |-| :: forall a. Eq a => Set a -> Set a -> Set a
(|-|) (Set [a]
xs) (Set [a]
ys) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
\\ [a]
ys
    
    -- | Return the set of all subsets of a given set.

    powerSet :: Set a -> Set (Set a)
    powerSet :: forall a. Set a -> Set (Set a)
powerSet (Set [a]
xs) = [Set a] -> Set (Set a)
forall a. [a] -> Set a
Set ([Set a] -> Set (Set a)) -> [Set a] -> Set (Set a)
forall a b. (a -> b) -> a -> b
$ [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [[a]] -> [Set a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [[a]]
forall a. [a] -> [[a]]
subsequences [a]
xs
    
    -- | Filter a set according to a condition.

    filterSet :: (a -> Bool) -> Set a -> Set a
    filterSet :: forall a. (a -> Bool) -> Set a -> Set a
filterSet a -> Bool
f (Set [a]
xs) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
f [a]
xs
    
    -- | Set version of listToMaybe.

    setToMaybe :: Set a -> Maybe a
    setToMaybe :: forall a. Set a -> Maybe a
setToMaybe = [a] -> Maybe a
forall a. [a] -> Maybe a
listToMaybe([a] -> Maybe a) -> (Set a -> [a]) -> Set a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
    
    -- | Set version of maybeToList.

    maybeToSet :: Maybe a -> Set a
    maybeToSet :: forall a. Maybe a -> Set a
maybeToSet Maybe a
x = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ Maybe a -> [a]
forall a. Maybe a -> [a]
maybeToList Maybe a
x
    
    -- | Set version of catMaybes.

    catMaybesToSet :: Set (Maybe a) -> Set a
    catMaybesToSet :: forall a. Set (Maybe a) -> Set a
catMaybesToSet = [a] -> Set a
forall a. [a] -> Set a
set([a] -> Set a) -> (Set (Maybe a) -> [a]) -> Set (Maybe a) -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.[Maybe a] -> [a]
forall a. [Maybe a] -> [a]
catMaybes([Maybe a] -> [a])
-> (Set (Maybe a) -> [Maybe a]) -> Set (Maybe a) -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set (Maybe a) -> [Maybe a]
forall a. Set a -> [a]
unsafeSetToList
    
    -- | Set version of mapMaybe.

    mapMaybeToSet :: (a -> Maybe b) -> Set a -> Set b
    mapMaybeToSet :: forall a b. (a -> Maybe b) -> Set a -> Set b
mapMaybeToSet a -> Maybe b
f = [b] -> Set b
forall a. [a] -> Set a
set([b] -> Set b) -> (Set a -> [b]) -> Set a -> Set b
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((a -> Maybe b) -> [a] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe a -> Maybe b
f)([a] -> [b]) -> (Set a -> [a]) -> Set a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
    
    -- | A function of homogeneous sets. It is a set of pairs (key,value) such that their should only be one pair with a given key.

    --

    -- It is an abstract type, the smart constructor is `function`.

    data Function a b = Function (Set (a,b)) deriving (Function a b -> Function a b -> Bool
(Function a b -> Function a b -> Bool)
-> (Function a b -> Function a b -> Bool) -> Eq (Function a b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b. (Eq a, Eq b) => Function a b -> Function a b -> Bool
/= :: Function a b -> Function a b -> Bool
$c/= :: forall a b. (Eq a, Eq b) => Function a b -> Function a b -> Bool
== :: Function a b -> Function a b -> Bool
$c== :: forall a b. (Eq a, Eq b) => Function a b -> Function a b -> Bool
Eq)
    
    instance (Show a, Show b) => Show (Function a b) where
        show :: Function a b -> String
show (Function Set (a, b)
al) = String
"(function "String -> ShowS
forall a. [a] -> [a] -> [a]
++Set (a, b) -> String
forall a. Show a => a -> String
show Set (a, b)
alString -> ShowS
forall a. [a] -> [a] -> [a]
++String
")"
    
    -- | An association list is a list of pairs (key,value).

    type AssociationList a b = [(a,b)]
    
    -- | The smart constructor of functions. This is the only way of instantiating a `Function`.

    --

    -- Takes an association list and returns a function which maps to each key the value associated.

    --

    -- If several pairs have the same keys, they are kept until the user wants an association list back.

    function :: AssociationList a b -> Function a b
    function :: forall a b. AssociationList a b -> Function a b
function AssociationList a b
al = Set (a, b) -> Function a b
forall a b. Set (a, b) -> Function a b
Function (Set (a, b) -> Function a b) -> Set (a, b) -> Function a b
forall a b. (a -> b) -> a -> b
$ AssociationList a b -> Set (a, b)
forall a. [a] -> Set a
Set (AssociationList a b -> Set (a, b))
-> AssociationList a b -> Set (a, b)
forall a b. (a -> b) -> a -> b
$ AssociationList a b
al
    
    -- | Transform a function back into its underlying association list.

    functionToSet :: (Eq a) => Function a b -> Set (a,b)
    functionToSet :: forall a b. Eq a => Function a b -> Set (a, b)
functionToSet (Function (Set [(a, b)]
al)) = [(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set ([(a, b)] -> Set (a, b)) -> [(a, b)] -> Set (a, b)
forall a b. (a -> b) -> a -> b
$ ((a, b) -> (a, b) -> Bool) -> [(a, b)] -> [(a, b)]
forall a. (a -> a -> Bool) -> [a] -> [a]
nubBy (\(a, b)
x (a, b)
y -> ((a, b) -> a
forall a b. (a, b) -> a
fst (a, b)
x) a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== ((a, b) -> a
forall a b. (a, b) -> a
fst (a, b)
y)) [(a, b)]
al
    
    -- | Return the domain of a function.

    domain :: Function a b -> Set a
    domain :: forall a b. Function a b -> Set a
domain (Function Set (a, b)
al) = (a, b) -> a
forall a b. (a, b) -> a
fst ((a, b) -> a) -> Set (a, b) -> Set a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (a, b)
al
    
    -- | Return the image of a function. The image of a function is the set of values which are reachable by applying the function.

    image :: Function a b -> Set b
    image :: forall a b. Function a b -> Set b
image (Function Set (a, b)
al) = (a, b) -> b
forall a b. (a, b) -> b
snd ((a, b) -> b) -> Set (a, b) -> Set b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (a, b)
al
        
    -- | Apply a function to a given value. If the function is not defined on the given value returns `Nothing`, otherwise returns `Just` the image.

    --

    -- This function is like `lookup` in Data.Map for function (the order of the argument are reversed though).

    (|$|) :: (Eq a) => Function a b -> a -> Maybe b
    |$| :: forall a b. Eq a => Function a b -> a -> Maybe b
(|$|) (Function (Set [])) a
_ = Maybe b
forall a. Maybe a
Nothing
    (|$|) (Function (Set ((a
k,b
v):[(a, b)]
xs))) a
x
        | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k = b -> Maybe b
forall a. a -> Maybe a
Just b
v
        | Bool
otherwise = (Set (a, b) -> Function a b
forall a b. Set (a, b) -> Function a b
Function ([(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set [(a, b)]
xs)) Function a b -> a -> Maybe b
forall a b. Eq a => Function a b -> a -> Maybe b
|$| a
x
    
    -- | Unsafe version of `(|$|)`.

    --

    -- This function is like `(!)` in Data.Map for function.

    (|!|) :: (Eq a) => Function a b -> a -> b
    |!| :: forall a b. Eq a => Function a b -> a -> b
(|!|) (Function (Set [])) a
_ = String -> b
forall a. HasCallStack => String -> a
error String
"Function applied on a value not in the domain."
    (|!|) (Function (Set ((a
k,b
v):[(a, b)]
xs))) a
x
        | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k = b
v
        | Bool
otherwise = (Set (a, b) -> Function a b
forall a b. Set (a, b) -> Function a b
Function ([(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set [(a, b)]
xs)) Function a b -> a -> b
forall a b. Eq a => Function a b -> a -> b
|!| a
x
    
    -- | Apply a function to a given value, if the value is in the domain returns the image, otherwise return a default value.

    --

    -- This function is like `findWithDefault` in Data.Map for function (the order of the argument are reversed though).

    findWithDefault :: (Eq a) => Function a b -> b -> a -> b
    findWithDefault :: forall a b. Eq a => Function a b -> b -> a -> b
findWithDefault (Function (Set [])) b
d a
_ = b
d
    findWithDefault (Function (Set ((a
k,b
v):[(a, b)]
xs))) b
d a
x
        | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k = b
v
        | Bool
otherwise = Function a b -> b -> a -> b
forall a b. Eq a => Function a b -> b -> a -> b
findWithDefault (Set (a, b) -> Function a b
forall a b. Set (a, b) -> Function a b
Function ([(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set [(a, b)]
xs)) b
d a
x
   
    -- | Compose two functions. If the two functions are not composable, strips the functions until they can compose.

    (|.|) :: (Eq a, Eq b) => Function b c -> Function a b -> Function a c
    |.| :: forall a b c.
(Eq a, Eq b) =>
Function b c -> Function a b -> Function a c
(|.|) Function b c
f2 Function a b
f1 = Set (a, c) -> Function a c
forall a b. Set (a, b) -> Function a b
Function (Set (a, c) -> Function a c) -> Set (a, c) -> Function a c
forall a b. (a -> b) -> a -> b
$ [(a, c)] -> Set (a, c)
forall a. [a] -> Set a
Set [(a
k,(Function b c
f2 Function b c -> b -> c
forall a b. Eq a => Function a b -> a -> b
|!| (Function a b
f1 Function a b -> a -> b
forall a b. Eq a => Function a b -> a -> b
|!| a
k))) | a
k <- (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList(Set a -> [a]) -> (Function a b -> Set a) -> Function a b -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Function a b -> Set a
forall a b. Function a b -> Set a
domain (Function a b -> [a]) -> Function a b -> [a]
forall a b. (a -> b) -> a -> b
$ Function a b
f1), Function a b
f1 Function a b -> a -> b
forall a b. Eq a => Function a b -> a -> b
|!| a
k b -> Set b -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` (Function b c -> Set b
forall a b. Function a b -> Set a
domain Function b c
f2)]
    
    -- | Memorize a Haskell function on a given finite domain.

    memorizeFunction :: (a -> b) -> Set a -> Function a b
    memorizeFunction :: forall a b. (a -> b) -> Set a -> Function a b
memorizeFunction a -> b
f (Set [a]
xs) = Set (a, b) -> Function a b
forall a b. Set (a, b) -> Function a b
Function (Set (a, b) -> Function a b) -> Set (a, b) -> Function a b
forall a b. (a -> b) -> a -> b
$ [(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set [(a
k, a -> b
f a
k) | a
k <- [a]
xs]