    --  The Compiler Toolkit: difference lists
    --
    --  Author : Manuel M. T. Chakravarty
    --  Created: 24 February 95
    --
    --  Copyright (c) [1995..2000] Manuel M. T. Chakravarty
    --
    --  This library is free software; you can redistribute it and/or
    --  modify it under the terms of the GNU Library General Public
    --  License as published by the Free Software Foundation; either
    --  version 2 of the License, or (at your option) any later version.
    --
    --  This library is distributed in the hope that it will be useful,
    --  but WITHOUT ANY WARRANTY; without even the implied warranty of
    --  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    --  Library General Public License for more details.
    --
    --- DESCRIPTION ---------------------------------------------------------------
    --
    --  This module provides the functional equivalent of the difference lists
    --  from logic programming.  They provide an O(1) append.
    --
    --- DOCU ----------------------------------------------------------------------
    --
    --  language: Haskell 98
    --
    --- TODO ----------------------------------------------------------------------
    --

    module DLists (DList, openDL, zeroDL, unitDL, snocDL, joinDL, closeDL)
    where

    -- a difference list is a function that given a list returns the original
    -- contents of the difference list prepended at the given list (EXPORTED)
    --
    type DList a = [a] -> [a]

    -- open a list for use as a difference list (EXPORTED)
    --
    openDL :: [a] -> DList a
    openDL :: forall a. [a] -> DList a
    openDL  = [a] -> [a] -> [a]
    forall a. [a] -> DList a
    (++)

    -- create a difference list containing no elements (EXPORTED)
    --
    zeroDL :: DList a
    zeroDL :: forall a. DList a
    zeroDL  = [a] -> [a]
    forall a. a -> a
    id

    -- create difference list with given single element (EXPORTED)
    --
    unitDL :: a -> DList a
    unitDL :: forall a. a -> DList a
    unitDL  = (:)

    -- append a single element at a difference list (EXPORTED)
    --
    snocDL      :: DList a -> a -> DList a
    snocDL :: forall a. DList a -> a -> DList a
    snocDL DList a
    dl a
    x  = \[a]
    l -> DList a
    dl (a
    xa -> DList a
    forall a. a -> DList a
    :[a]
    l)

    -- appending difference lists (EXPORTED)
    --
    joinDL :: DList a -> DList a -> DList a
    joinDL :: forall a. DList a -> DList a -> DList a
    joinDL  = ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    (.)

    -- closing a difference list into a normal list (EXPORTED)
    --
    closeDL :: DList a -> [a]
    closeDL :: forall a. DList a -> [a]
    closeDL  = (([a] -> [a]) -> [a] -> [a]
    forall a b. (a -> b) -> a -> b
    $[])