-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEx16_queues.hs
More file actions
109 lines (85 loc) · 2.22 KB
/
Copy pathEx16_queues.hs
File metadata and controls
109 lines (85 loc) · 2.22 KB
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
module Queue
( Queue,
emptyQ, -- Queue a
isEmptyQ, -- Queue a -> Bool
addQ, -- a -> Queue a -> Queue a
remQ -- Queue a -> (a, Queue a)
) where
import Deque
import Data.List (elem)
newtype Queue a = Qu [a] deriving Show
emptyQ = Qu []
isEmptyQ (Qu []) = True
isEmptyQ _ = False
addQ x (Qu xs) = Qu (xs++[x])
remQ q@(Qu xs)
| not (isEmptyQ q) = (head xs, Qu (tail xs))
| otherwise = error "remQ"
-- add elements at the beginning
{-
addQ x (Qu xs) = Qu (x:xs)
remQ q@(Qu xs)
| not (isEmptyQ q) = (last xs, Qu (init xs))
| otherwise = error "remQ"
-}
data QueueN a = QuN [a] [a] deriving Show
emptyQN = QuN [] []
isEmptyQN (QuN [] []) = True
isEmptyQN _ = False
addQN x (QuN xs ys) = QuN xs (x:ys)
remQN (QuN (x:xs) ys) = (x, QuN xs ys)
remQN (QuN [] (y:ys)) = remQN (QuN (reverse (y:ys)) [])
remQN (QuN [] []) = error "remQ"
-- Ex 16.7
-- Give calcutation of
{-
"abcde" ++ "f"
[] ++ ys - False
(x:xs) ys - True
a : "bcde" ++ "f"
...
a : b : c : d : e : ([] "f" - True)
"f"
[] ++ ys - True
a : b : c : d : e : "f"
...
"abcdef"
init "abcdef"
init x = take (length - 1) x
take (length "abcdef" - 1) "abcdef"
length "abcdef" = 1 + length "bcdef" + ... = 6
6 - 1 = 5
take 5 "abcdef"
a : take 4 "bcdef"
...
a : b : c : d : take 0 "ef"
a : b : c : d : []
"abcd"
last "abcdef"
last x = x !! (length x-1)
"abcdef" !! (length "abcdef" - 1)
"abcdef" !! (6 - 1)
"abcdef" !! 5
(!!) "abcdef" 5
a : "bcdef" 4
...
a : b : c : d : e : "f" 0
'f'
-}
-- Ex 16.8
-- Explain the behavior of the three queue models
-- on the following sequence of operations:
-- add 2, add 1, remove, add 3, remove, add 1, add 4, remove, remove
-- so behavior of 1qm and 2qm is the same
-- it adds an element to the end of the list
-- removes first element of the list
-- behavior of the third model
-- it will always add an element to the beginning of the second list
-- its removing first element of the first list
-- if the first list is empty, then it transfers reversed second list to the first list and removes its first element
-- Ex 16.9
-- imported from Deque.hs
-- Ex 16.10
-- A unique queue can contain only one occurrence of each entry
addUnQ x (Qu xs) =
if elem x xs then Qu xs else Qu (xs ++ [x])