Vector: length (and reverse) 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
module Data.Vector where

{--

Today's problem is for you to print "Hello, World!"

No, not really. I'm just kidding.

So, the next couple of questions (if you're following along, these are 
problems P04 and P05 from the P99-set mentioned yesterday) seem unrelated.

Or. Are. They?

We shall see.

So, the length of a list is declared as:

length : [a] -> Int

The problem here is that length list is computed, and that computation occurs
in linear time.

In a word: bleck!

Why 'bleck'? Because we know the list structure at every point, so we COULD
know its length at every point, and we COULD know that value in constant time,
as well.

There is such a type, called Vector, that does track this information with
a (possibly internal) Int value.

Create a data type Vector, such that

lengthV: Vector a -> Int

gives its answer in constant time (that is, regardless of the length of the
Vector).

BONUS:

reverse: [a] -> [a] is a function that returns in linear time.

Further refine Vector a such that

reverseV :: Vector a -> Vector a

is a function that returns in constant time.

(Hint for bonus: it is not necessary for Vectors to model list functionality 
*cough* Deque *cough*)

--}

data Vector a = OkayDependentTypesInHaskellNoWheyAKAPiForall -- ... perhaps

lengthV :: Vector a -> Int -- constant time
lengthV vect = undefined

----- BONUS:

reverseV :: Vector a -> Vector a -- constant time
reverseV vect = undefined

--- FURTHER RESEARCH for those curious about dependent types in pi-forall:
--- https://github.com/sweirich/pi-forall/