-
Notifications
You must be signed in to change notification settings - Fork 4
/
Deque.hs
42 lines (28 loc) · 932 Bytes
/
Deque.hs
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
{- Exercise 5.1 -}
module Okasaki.Chapter5.Deque(Deque(..), BatchedDeque) where
import Okasaki.Chapter5.Queue
class Queue d => Deque d where
cons :: a -> d a -> d a
qlast :: d a -> a
qinit :: d a -> d a
data BatchedDeque a = BD [a] [a]
balance xs = (take mid xs, reverse $ drop mid xs) where
mid = length xs `div` 2
makeBD [] ys = uncurry (flip BD) $ balance ys
makeBD xs [] = uncurry BD $ balance xs
makeBD xs ys = BD xs ys
instance Queue BatchedDeque where
empty = BD [] []
isEmpty (BD [] []) = True
isEmpty _ = False
snoc v (BD xs ys) = makeBD xs (v : ys)
qhead (BD (x:_) _) = x
qhead (BD [] [y]) = y
qtail (BD (_:xs) ys) = makeBD xs ys
qtail (BD [] [_]) = empty
instance Deque BatchedDeque where
cons v (BD xs ys) = makeBD (v : xs) ys
qlast (BD _ (y:_)) = y
qlast (BD [x] []) = x
qinit (BD xs (_:ys)) = makeBD xs ys
qinit (BD [_] []) = empty