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

--- ----------------------------------------------------------------------------
--- Difference list implementation for Curry
---
--- @author  Jan Tikovsky
--- @version October 2017
--- ----------------------------------------------------------------------------
module Data.DList where

import List (nub)

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

--- Create an empty diff list
empty :: DList a
empty = DL id

--- Create a diff list with a single element
singleton :: a -> DList a
singleton = DL . (:)

--- Prepend an element to a diff list
cons :: a -> DList a -> DList a
cons x xs = DL ((x:) . unDL xs)

--- Append two diff lists
append :: DList a -> DList a -> DList a
append xs ys = DL (unDL xs . unDL ys)

--- Convert a list to a diff list
fromList :: [a] -> DList a
fromList = DL . (++)

--- Convert a diff list to a list
toList :: DList a -> [a]
toList = ($ []) . unDL

--- Convert a diff list to a duplicate free list
toListNub :: Eq a => DList a -> [a]
toListNub = nub . toList

--- Get the head element of a diff list
hd :: DList a -> a
hd xs = case toList xs of
  []    -> error "Data.DList.hd: List is empty"
  (y:_) -> y

--- Get the tail of a diff list
tl :: DList a -> DList a
tl xs = case toList xs of
  []     -> error "Data.DList.hd: List is empty"
  (_:ys) -> fromList ys

--- Show instance
instance Show a => Show (DList a) where
  show = show . toList