DList.hs

newtype DL a = DL { unDL :: [a] -> [a] }                                                                                                                                                     
                                                                                                                                                                                             
instance Show a => Show (DL a) where                                                                                                                                                         
  show = show . toList                                                                                                                                                                       
                                                                                                                                                                                             
instance Semigroup (DL a) where                                                                                                                                                              
  DL f <> DL g = DL (f <> g)                                                                                                                                                                 
                                                                                                                                                                                             
instance Monoid (DL a) where                                                                                                                                                                 
  mempty = DL mempty                                                                                                                                                                         
                                                                                                                                                                                             
instance Functor DL where                                                                                                                                                                    
  fmap = liftM                                                                                                                                                                               
                                                                                                                                                                                             
instance Foldable DL where                                                                                                                                                                   
  foldMap f g = foldMap f (toList g)                                                                                                                                                         
                                                                                                                                                                                             
instance Applicative DL where                                                                                                                                                                
  pure  = return                                                                                                                                                                             
  (<*>) = ap                                                                                                                                                                                 
                                                                                                                                                                                             
instance Monad DL where                                                                                                                                                                      
  return = \x -> DL $ \xs -> [x]                                                                                                                                                             
  m >>= f = foldMap f m                                                                                                                                                                      
                                                                                                                                                                                             
concat :: [DL a] -> DL a                                                                                                                                                                     
concat = mconcat                                                                                                                                                                             
                                                                                                                                                                                             
append :: DL a -> DL a -> DL a                                                                                                                                                               
append = (<>)                                                                                                                                                                                
                                                                                                                                                                                             
fromList :: [a] -> DL a                                                                                                                                                                      
fromList = foldMap pure                                                                                                                                                                      
                                                                                                                                                                                             
toList :: DL a -> [a]                                                                                                                                                                        
toList (DL f) = f mempty                                                                                                                                                                     
                                                                                                                                                                                             
singleton :: a -> DL a                                                                                                                                                                       
singleton = pure