1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
-- The Compiler Toolkit: difference lists
--
-- Author : Manuel M. T. Chakravarty
-- Created: 24 February 95
--
-- Copyright (c) [1995..1999] 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 to 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 = (++)
-- create a difference list containing no elements (EXPORTED)
--
zeroDL :: DList a
zeroDL = id
-- create difference list with given single element (EXPORTED)
--
unitDL :: a -> DList a
unitDL = (:)
-- append a single element at a difference list (EXPORTED)
--
snocDL :: DList a -> a -> DList a
snocDL dl x = \l -> dl (x:l)
-- appending difference lists (EXPORTED)
--
joinDL :: DList a -> DList a -> DList a
joinDL = (.)
-- closing a difference list into a normal list (EXPORTED)
--
closeDL :: DList a -> [a]
closeDL = ($[])
|
