**Paste:**#106843**Author:**1HaskellADay**Language:**Haskell**Channel:**-**Created:**2014-07-03 10:42:10 UTC**Revisions:**- 2014-07-03 10:45:44 UTC #106844 (diff): No title (1HaskellADay)
- 2014-07-03 10:42:10 UTC #106843: Vector: length (and reverse) in constant time (1HaskellADay)

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/ |