Deque, last, all that

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
module Data.Deque where

{--

The following sets of problems over the next few days get their inspiration 
from some of the problems from the P-99, or Ninety-Nine Prolog Problems 
published by Werner Hett.

Create a traversable data type, let’s call it Deque a (‘Deque’ meaning: 
‘double-ended queue’) such that the operation

last :: Deque a -> a

is in constant time, also have this function obey the properties of the 
same-named function for lists, that is: it gives an error for an empty Deque.

That’s the ‘get.’ The ‘put’ for this type should also be in ‘kinda good’ time 
at either end (see declarations below for prepend and postpend).

Bonus: 

1. Prove (or show) that last (Deque a) is in constant time. 

2. Prove, or show, that an implementation of Deque a can have 

zweitletztes (Deque a)

such that zweitletztes (Deque a) is faster than 

zweitletztes [a]. 

Explanation:

The last element of a list or deque is its ultimate element
The zweitletztes element of a list or deque is its penultimate element.

So, for let deck = dequeFromList [1..10]

last deck ~> 10
zweitletztes deck ~> 9

--}

data Deque a = WhateverDeclarationWorksForYou

-- remember: instance Traversable Deque (and supporting instances)

last  :: Deque a -> a
last deck = undefined  -- constant time
first :: Deque a -> a
first deck = undefined -- constant time

(|<) :: Deque a -> a -> Deque a -- or 'postpend'
deck |< x = undefined           -- 'kinda good' time
(>|) :: a -> Deque a -> Deque a -- or 'prepend'
x >| deck = undefined           -- 'kinda good' time

-- bonus:

-- zweitletztes deck gives the penultimate element of a deque

zweitletztes :: Deque a -> a
zweitletztes deck = undefined

{-

An implementation of zweitletztes for [a] could be written:

zweitletztes :: [a] -> a
zweitletztes = last . init

-}

-- a verbose, hintful, version of this file is at http://lpaste.net/106730

-- The solution is Data.Deque: http://lpaste.net/106780