**Paste:**#106730**Author(s):**1HaskellADay**Language:**Haskell**Channel:**-**Created:**2014-07-01 15:04:47 UTC**Revisions:**- 2014-07-01 15:57:12 UTC #106741 (diff): No title (1HaskellADay)
- 2014-07-01 15:09:57 UTC #106733 (diff): No title (1HaskellADay)
- 2014-07-01 15:08:19 UTC #106732 (diff): No title (1HaskellADay)
- 2014-07-01 15:04:47 UTC #106730: last (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 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]. -} |