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
|
-- |
-- Module : Foundation.List.DList
-- License : BSD-style
-- Maintainer : Nicolas Di Prima <nicolas@primetype.co.uk>
-- Stability : statble
-- Portability : portable
--
-- Data structure for optimised operations (append, cons, snoc) on list
--
module Foundation.List.DList
( DList
) where
import Basement.Compat.Base
import Basement.Compat.Semigroup
import Basement.Compat.Bifunctor
import Foundation.Collection
newtype DList a = DList { unDList :: [a] -> [a] }
deriving (Typeable)
instance Eq a => Eq (DList a) where
(==) dl1 dl2 = (==) (toList dl1) (toList dl2)
instance Ord a => Ord (DList a) where
compare dl1 dl2 = compare (toList dl1) (toList dl2)
instance Show a => Show (DList a) where
show = show . toList
instance IsList (DList a) where
type Item (DList a) = a
fromList = DList . (Basement.Compat.Semigroup.<>)
toList = flip unDList []
instance Semigroup (DList a) where
(<>) dl1 dl2 = DList $ unDList dl1 . unDList dl2
instance Monoid (DList a) where
mempty = DList id
instance Functor DList where
fmap f = foldr (cons . f) mempty
instance Applicative DList where
pure = singleton
(<*>) m1 m2 = m1 >>= \x1 -> m2 >>= \x2 -> return (x1 x2)
instance Monad DList where
(>>=) m k = foldr (mappend . k) mempty m
return = pure
type instance Element (DList a) = a
instance Foldable (DList a) where
foldr f b = foldr f b . toList
foldl' f b = foldl' f b . toList
instance Collection (DList a) where
null = null . toList
length = length . toList
elem a = elem a . toList
maximum = maximum . nonEmpty_ . toList
minimum = minimum . nonEmpty_ . toList
all f = all f . toList
any f = any f . toList
instance Sequential (DList a) where
take n = fromList . take n . toList
revTake n = fromList . revTake n . toList
drop n = fromList . drop n . toList
revDrop n = fromList . revDrop n . toList
splitAt n = bimap fromList fromList . splitAt n . toList
splitOn f = fmap fromList . splitOn f . toList
break f = bimap fromList fromList . break f . toList
breakEnd f = bimap fromList fromList . breakEnd f . toList
breakElem e = bimap fromList fromList . breakElem e . toList
intersperse e = fromList . intersperse e . toList
intercalate e = intercalate e . toList
span f = bimap fromList fromList . span f . toList
spanEnd f = bimap fromList fromList . spanEnd f . toList
filter f = fromList . filter f . toList
partition f = bimap fromList fromList . partition f . toList
reverse = fromList . reverse . toList
uncons dl = second fromList <$> uncons (toList dl)
unsnoc dl = first fromList <$> unsnoc (toList dl)
cons e dl = DList $ (:) e . unDList dl
snoc dl e = DList $ unDList dl . (:) e
find f = find f . toList
sortBy comp = fromList . sortBy comp . toList
singleton = DList . (:)
replicate n e = fromList $ replicate n e
|
