/
Solution.hs
73 lines (48 loc) · 1.83 KB
/
Solution.hs
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
{-# LANGUAGE TupleSections #-}
module Y2021.M03.D18.Solution where
-- Remember that exercise where we built a map of keys and indices?
import Y2021.M03.D11.Solution
{--
Now, what we want to do is to have a ... okay, don't panic! ... 'mutable'
map of keys and indicies.
--}
import Data.List (maximum)
import Data.Map (Map)
import qualified Data.Map as Map
import Prelude hiding (lookup)
data LookupTable =
LookupTable { values :: Map String Integer, nextIndex :: Integer }
deriving (Eq, Ord, Show)
-- give an empty lookup table with the first-next index of 1
initLookupTable :: LookupTable
initLookupTable = LookupTable Map.empty 1
-- given a preexisting map, return a lookup table with the max index + 1 as next
toLookupTable :: Map String Integer -> LookupTable
toLookupTable = LookupTable <*> succ . maximum . Map.elems
lookup :: String -> LookupTable -> (Integer, LookupTable)
lookup key l@(LookupTable m idx) =
maybe (idx, LookupTable (Map.insert key idx m) (succ idx))
((,l)) (Map.lookup key m)
{--
>>> let lk = toLookupTable (uniqueIds names)
lookup always succeeds.
If the key is in the lookup table, it returns the index with the existing
LookupTable
If the key is not in the lookup table, it inserts that key with next index,
updates next index and returns the key's index as well as the new lookup table.
What is the index of "Tom"?
>>> lookup "Tom" lk
(1,LookupTable {values = fromList [("Dick",2),("Harry",3),("Tom",1)], nextIndex = 4})
>>> let lk1 = snd it
What is the index of "quux"?
>>> lookup "quux" lk1
(4,LookupTable {values = fromList [("Dick",2),("Harry",3),("Tom",1),("quux",4)], nextIndex = 5})
>>> let lk2 = snd it
What is the index of "Joe"?
>>> let (joeIdx, lk3) = lookup "Joe" lk2
>>> joeIdx
5
On a new request, is the index of "quux" still the same? ("Yes" is correct.)
>>> fst $ lookup "quux" lk3
4
--}