DLists? We no need no steenkin' DLists!

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
module Control.DList where

infixl 5 <|
infixr 5 |>

{--

Okay, so I thought I was 'done' with lists ...

... (well, 'done' as in 'done for these problem sets.' One is never
'done' qua done with lists, is one?) ...

... but I wasn't.

Weren't.

Whatever.

So, with deques we see a more efficient storage and retrieval on either
end of that structure, both at the front and at the back of that structure,
whereas with lists, head is O(1)-efficient but last/(++) is in O(N)-time. 

Ick!

Or.
Is.
IT?!?!?

Prolog is awesome.

(flames are welcome at /dev/null)

I reiterate. Prolog is awesome in that it has a structure called a
difference-list such that it is a structure 'shared' over two lists:
the list-as-it-exists-now-during-its-intermediate-generation and the
list-as-it-will-appear-when-it-is-fully-materialized.

Append exploits this 'interim'-state so that append operations (++)
occur in constant time!

This exploitation is so useful that it was eventually rolled into the
language syntax as definite-clause grammars, making, e.g.: the
implementation of DSLs (both scanning and parsing) a nearly trivial
exercise.

Thus endeth my Prolog digression.

With Haskell, I find difference lists useful from time-to-time, particularly
when I find an operation I'm working with best expressed by appending to
the back of a list... or the front. Either way.

So!

Create the difference list type: --}

data DList a = DL { unDL :: [a] -> [a] }

{--

such that prepending and appending elements to it occur in constant time. So,
given the following operation (that may or may not be helpful):

 --}

cons :: a -> [a] -> [a]
cons a list = a : list

{--

Write the following operations for DLists

 --}

(|>) :: a -> DList a -> DList a  -- operation in constant-time
a |> dlist = undefined           -- prepends an element to a DList

(<|) :: DList a -> a -> DList a  -- operation in constant-time
dlist <| a = undefined           -- appends an element to a DList

emptyDL :: DList a
emptyDL = undefined

dlToList :: DList a -> [a]
dlToList dlist = undefined

{--

So:

*Control.DList> let ld = 1 |> 2 |> 3 |> emptyDL
*Control.DList> let dl = emptyDL <| 1 <| 2 <| 3
*Control.DList> dlToList dl
[1,2,3]
*Control.DList> dlToList ld
[1,2,3]

A solution is posted at http://lpaste.net/107607

 --}