    {-# 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 :: forall a. DList a -> [a]
    toList (DList [a] -> [a]
    dl) = [a] -> [a]
    dl []

    -- | Create dlist with a single element
    singleton :: a -> DList a
    singleton :: forall a. 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 :: forall a. 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 :: forall a. 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)