last (in constant time)

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

{-

Problem-solve you Haskell for fun and profit (well, ‘fun,’ anyway. Maybe.)

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

The first problem is this.

last :: [a] -> a

as implemented in GHC is guaranteed to be in linear time to the length of 
the list, in other words: bleck!

Create a data structure, 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, so:

deck |< x (or ‘postpend element x to deque deck’)

and

y >| deck (or ‘prepend element y to deque deck’) 

are both in ‘kinda good’ time, where ‘kinda good’ is (weak-in-the-knees) defined 
as ‘okay for prepend’ and for postpend is ‘waaaay' better than 

list ++ [x] 

for some (any?) list.

The data type Deque a should also, at minimum, be a Traversable instance (which 
further means it has to be a Functor instance and a Foldable instance). So, this 
means: be ‘kinda’ careful when constructing deques, of course, but also be 
'kinda' careful when destructuring them, as well. Please see the Typeclassopedia 
at  http://www.haskell.org/haskellwiki/Typeclassopedia for information about 
these typeclasses.

Bonus (for those of you yawning at the above and want a bit of a challenge in 
your daily problem-solving exercise): Prove (or show) that last (Deque a) is in 
constant time. Prove, or show, that an implementation of Deque a can have 

zweitletztes (Deque a)

such that zweitletztes (Deque a) is faster than 

zweitletztes [a]. 

Such an implementation of Deque a might be a bi-directional list-type over 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 list = [1..10]

last list ~> 10
zweitletztes list ~> 9

Hint: implementing last and zweitletztes in the CPS makes the bonus proof 
trivial, but you can also count reduction steps by hand if you prefer.

-}

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 :: Deque a -> a
zweitletztes deck = undefined

{-

1. Prove, or show, that your implementation of last for your implementation 
of Deque a is faster than the standard library last implementation (from GHC, 
for example). Hint: this should be an easy proof.

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

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

Prove, or show, that your implementation of zweitletztes (Deque a), for some 
(pretty good) implementation of Deque, is faster than some (pretty good) 
implementation of zweitletztes [a] for the Haskell standard implementation 
of [a].

-}