{-# LANGUAGE Safe #-}

-- |
-- Copyright: © Herbert Valerio Riedel 2018
-- SPDX-License-Identifier: GPL-2.0-or-later
--
-- Minimal API-compatible rip-off of @Data.DList@
module Data.DList
    ( DList
    , empty
    , singleton
    , append
    , toList
    ) where

-- | A difference list is a function that, given a list, returns the original
-- contents of the difference list prepended to the given list.
newtype DList a = DList ([a] -> [a])

-- | Convert a dlist to a list
toList :: DList a -> [a]
toList :: DList a -> [a]
toList (DList [a] -> [a]
dl) = [a] -> [a]
dl []

-- | Create dlist with a single element
singleton :: a -> DList a
singleton :: a -> DList a
singleton a
x = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)

-- | Create a dlist containing no elements
empty :: DList a
empty :: DList a
empty = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList [a] -> [a]
forall a. a -> a
id

-- | O(1). Append dlists
append :: DList a -> DList a -> DList a
append :: DList a -> DList a -> DList a
append (DList [a] -> [a]
xs) (DList [a] -> [a]
ys) = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DList ([a] -> [a]
xs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
ys)