| -- |

| -- Copyright 2016, NICTA |

| -- |

| -- This software may be distributed and modified according to the terms of |

| -- the GNU General Public License version 2. Note that NO WARRANTY is provided. |

| -- See "LICENSE_GPLv2.txt" for details. |

| -- |

| -- @TAG(NICTA_GPL) |

| -- |

| |

| {-# LANGUAGE DeriveGeneric #-} |

| |

| module Data.DList |

| ( DList(..) |

| , empty |

| , singleton |

| , cons |

| , fromList |

| , toList |

| ) where |

| |

| import Control.Arrow (first) |

| import Data.Binary |

| import qualified Data.Set as S |

| import Data.List (find, foldl') |

| import GHC.Generics (Generic) |

| |

| {- |

| - Distinct list. |

| - Used to keep track of definitions, which require an ordering |

| - but don't need to be stored multiple times. |

| -} |

| data DList a = DList ![a] deriving (Eq, Ord, Generic) |

| |

| instance Binary a => Binary (DList a) |

| |

| -- Just implement functions that we currently use. |

| empty :: DList a |

| empty = DList [] |

| |

| singleton :: a -> DList a |

| singleton a = DList [a] |

| |

| cons :: Ord a => a -> DList a -> DList a |

| cons x dl@(DList xs) | x `elem` xs = dl |

| | otherwise = DList (x:xs) |

| |

| fromList :: Ord a => [a] -> DList a |

| fromList = foldl' (flip cons) empty . reverse |

| |

| toList :: DList a -> [a] |

| toList (DList xs) = xs |

| |

| instance Show a => Show (DList a) where |

| showsPrec n (DList xs) = showsPrec n xs |

| instance (Ord a, Read a) => Read (DList a) where |

| readsPrec n s = map (first DList) $ readsPrec n s |