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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
-- |
-- Strict Deque API lifted to a State monad, \"mtl\"-style.
module Deque.Strict.State where
import Deque.Prelude hiding (dropWhile, head, init, last, null, reverse, tail, takeWhile)
import qualified Deque.Prelude as Prelude
import Deque.Strict (Deque)
import qualified Deque.Strict as Deque
-- |
-- \(\mathcal{O}(n)\).
-- Modify each element of the queue.
map :: (MonadState (Deque a) m) => (a -> a) -> m ()
map f = modify (fmap f)
-- |
-- \(\mathcal{O}(n)\).
-- Add elements to the begginning.
prepend :: (MonadState (Deque a) m) => Deque a -> m ()
prepend deque = modify (deque <>)
-- |
-- \(\mathcal{O}(n)\).
-- Add elements to the ending.
append :: (MonadState (Deque a) m) => Deque a -> m ()
append deque = modify (<> deque)
-- |
-- \(\mathcal{O}(1)\).
-- Add element in the beginning.
cons :: (MonadState (Deque a) m) => a -> m ()
cons a = modify (Deque.cons a)
-- |
-- \(\mathcal{O}(1)\).
-- Add element in the ending.
snoc :: (MonadState (Deque a) m) => a -> m ()
snoc a = modify (Deque.snoc a)
-- |
-- \(\mathcal{O}(1)\).
-- Reverse the deque.
reverse :: (MonadState (Deque a) m) => m ()
reverse = modify Deque.reverse
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Move the first element to the end.
shiftLeft :: (MonadState (Deque a) m) => m ()
shiftLeft = modify Deque.shiftLeft
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Move the last element to the beginning.
shiftRight :: (MonadState (Deque a) m) => m ()
shiftRight = modify Deque.shiftRight
-- |
-- \(\mathcal{O}(n)\).
-- Leave only the elements satisfying the predicate.
filter :: (MonadState (Deque a) m) => (a -> Bool) -> m ()
filter predicate = modify (Deque.filter predicate)
-- |
-- \(\mathcal{O}(n)\).
-- Leave only the specified amount of first elements.
take :: (MonadState (Deque a) m) => Int -> m ()
take = modify . Deque.take
-- |
-- \(\mathcal{O}(n)\).
-- Drop the specified amount of first elements.
drop :: (MonadState (Deque a) m) => Int -> m ()
drop = modify . Deque.drop
-- |
-- \(\mathcal{O}(n)\).
-- Leave only the first elements satisfying the predicate.
takeWhile :: (MonadState (Deque a) m) => (a -> Bool) -> m ()
takeWhile predicate = modify (Deque.takeWhile predicate)
-- |
-- \(\mathcal{O}(n)\).
-- Drop the first elements satisfying the predicate.
dropWhile :: (MonadState (Deque a) m) => (a -> Bool) -> m ()
dropWhile predicate = modify (Deque.dropWhile predicate)
-- |
-- \(\mathcal{O}(n)\).
-- Return the first elements satisfying the predicate, removing them from the state.
span :: (MonadState (Deque a) m) => (a -> Bool) -> m (Deque a)
span predicate = state (Deque.span predicate)
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the first element if deque is not empty,
-- removing the element.
uncons :: (MonadState (Deque a) m) => m (Maybe a)
uncons =
state
( \deque -> case Deque.uncons deque of
Nothing -> (Nothing, deque)
Just (a, newDeque) -> (Just a, newDeque)
)
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the last element if deque is not empty,
-- removing the element.
unsnoc :: (MonadState (Deque a) m) => m (Maybe a)
unsnoc =
state
( \deque -> case Deque.unsnoc deque of
Nothing -> (Nothing, deque)
Just (a, newDeque) -> (Just a, newDeque)
)
-- |
-- \(\mathcal{O}(1)\).
-- Check whether deque is empty.
null :: (MonadState (Deque a) m) => m Bool
null = gets Deque.null
-- |
-- \(\mathcal{O}(1)\).
-- Check whether deque is empty.
length :: (MonadState (Deque a) m) => m Int
length = gets Prelude.length
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the first element if deque is not empty.
head :: (MonadState (Deque a) m) => m (Maybe a)
head = gets Deque.head
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the last element if deque is not empty.
last :: (MonadState (Deque a) m) => m (Maybe a)
last = gets Deque.last
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Keep all elements but the first one.
tail :: (MonadState (Deque a) m) => m ()
tail = modify Deque.tail
-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Keep all elements but the last one.
init :: (MonadState (Deque a) m) => m ()
init = modify Deque.init
|
