AssociationList.hs

{-| Module  : FiniteCategories
Description : The type for association lists.
Copyright   : Guillaume Sabbagh 2021
License     : GPL-3
Maintainer  : guillaumesabbagh@protonmail.com
Stability   : experimental
Portability : portable

The type for association lists.

It is used when the 'Ord' constraint of `Data.Map` is too restrictive.
-}

module Utils.AssociationList
(
    AssociationList,
    keys,
    values,
    (!-),
    (!-!),
    (!-?),
    (!-.),
    mkAssocListIdentity,
    enumAssocLists,
    functToAssocList,
    assocListToFunct,
    inverse,
    removeKey,
    removeValue,
)
where
    import Utils.CartesianProduct
    import Data.Tuple (swap)
    
    -- | The type of association lists (a list of couples).
    type AssociationList a b = [(a, b)]
    
    -- | Returns the keys of the association list.
    keys :: (AssociationList a b) -> [a]
    keys = fmap fst
    
    -- | Returns the values of the association list.
    values :: (AssociationList a b) -> [b]
    values = fmap snd
    
    -- | If the key is in the association list, returns Just the value associated, otherwise Nothing.
    --
    -- Same as lookup in `Data.Map`.
    (!-) :: (Eq a) => a -> (AssociationList a b) -> Maybe b
    (!-) _ [] = Nothing
    (!-) k ((a,b):xs)
        | a == k = Just b
        | otherwise = k !- xs
        
    -- | If the key is in the association list, returns the value associated, otherwise throws an error.
    --
    -- Same as (!) in `Data.Map`.
    (!-!) :: (Eq a) => (AssociationList a b) -> a -> b
    (!-!) [] _ = error "Key not in association list."
    (!-!) ((a,b):xs) k
        | a == k = b
        | otherwise = xs !-! k
      
    -- | If the key is in the association list, returns the value associated, otherwise returns a default value.
    --
    -- Same as /findWithDefault/ in `Data.Map`.      
    (!-?) :: (Eq a) => b -> a -> (AssociationList a b) -> b
    (!-?) d _ [] = d
    (!-?) d k ((a,b):xs)
        | a == k = b
        | otherwise = (!-?) d k xs
                               
    -- | Composition of association lists.
    (!-.) :: (Eq a, Eq b) => (AssociationList b c) -> (AssociationList a b) -> (AssociationList a c)
    (!-.) al2 al1 = [(k, al2 !-! (al1 !-! k)) | k <- keys al1, elem (al1 !-! k) (keys al2)]
    
    -- | Constructs the identity association list of a list of values.
    -- 
    -- For example, @ mkAssocListIdentity [1,2,3] = [(1,1),(2,2),(3,3)]@
    mkAssocListIdentity :: [a] -> AssociationList a a
    mkAssocListIdentity xs = [(o,o) | o <- xs]
    
    -- | Enumerates all association lists possible between a domain and a codomain.
    enumAssocLists :: [a] -> [b] -> [AssociationList a b]
    enumAssocLists dom codom = [zip dom im | im <- (codom |^| (length dom))]
    
    -- | Transforms a function and a domain into an association list.
    functToAssocList :: (a -> b) -> [a] -> (AssociationList a b)
    functToAssocList f d = [(o, f o) | o <- d]
    
    -- | Transforms an association list to a function.
    assocListToFunct :: (Eq a) => (AssociationList a b) -> a -> b
    assocListToFunct [] _ = error "Can't transform an empty list into a function."
    assocListToFunct ((k,v):xs) x
        | k == x = v
        | otherwise = assocListToFunct xs x
        
    -- | Inverse of an association list
    inverse :: (AssociationList a b) -> (AssociationList b a)
    inverse kvs = swap <$> kvs
    
    -- | Remove all couples with a certain key
    removeKey :: (Eq a) => (AssociationList a b) -> a -> (AssociationList a b)
    removeKey al key = [c | c@(k,_) <- al, k /= key]
    
    -- | Remove all couples with a certain value
    removeValue :: (Eq b) => (AssociationList a b) -> b -> (AssociationList a b)
    removeValue al value = [c | c@(_,v) <- al, v /= value]