maps.patch

From 8c7356085c05975f69f71c0023db791f09b296c1 Mon Sep 17 00:00:00 2001
From: Rob Berry <rob@example.com>
Date: Fri, 23 Sep 2016 08:55:30 +0100
Subject: [PATCH] Hash and List maps

---
 src/Data/Workshop/HashMap.hs | 37 +++++++++++++++++++++++++++----------
 src/Data/Workshop/ListMap.hs | 20 +++++++++++---------
 2 files changed, 38 insertions(+), 19 deletions(-)

diff --git a/src/Data/Workshop/HashMap.hs b/src/Data/Workshop/HashMap.hs
index 62789bc..eb57666 100644
--- a/src/Data/Workshop/HashMap.hs
+++ b/src/Data/Workshop/HashMap.hs
@@ -1,3 +1,5 @@
+{-# LANGUAGE ScopedTypeVariables #-}
+
 module Data.Workshop.HashMap
        (
          HashMap(..)
@@ -17,6 +19,7 @@ module Data.Workshop.HashMap
 
 import qualified Data.Vector as V
 import qualified Data.Hashable as H
+import Data.Maybe
 
 type MapKey = String
 
@@ -29,13 +32,15 @@ pairKey (MapPair k _) = k
 pairValue :: MapPair a -> a
 pairValue (MapPair _ v) = v
 
-type Buckets a = (V.Vector (Maybe (MapPair a)))
+type Buckets a = V.Vector (Maybe (MapPair a))
+
+data HashMap a = HashMap (Buckets a) deriving (Show)
 
-data HashMap a = HashMap (Buckets a)
+bucketSize = 10
 
 -- create an empty map
 empty :: Eq a => HashMap a
-empty = undefined
+empty = HashMap V.empty
 
 -- return the number of items in the map
 size :: Eq a => HashMap a -> Int
@@ -50,20 +55,32 @@ keys :: HashMap a -> [MapKey]
 keys (HashMap b) = undefined
 
 -- return all values in the map
-values :: HashMap a -> [a]
-values (HashMap b) = undefined
+values :: forall a. HashMap a -> [a]
+values (HashMap b) = mapMaybe f (V.toList b)
+  where
+    f :: Maybe (MapPair a) -> Maybe a
+    f = maybe Nothing (fmap pairValue)
+
+finder :: MapKey -> Maybe (MapPair a) -> Bool
+finder mk = maybe False (\mp -> pairKey mp == mk)
 
 -- determine whether the map contains a key or not
-contains :: HashMap a -> MapKey -> Bool
-contains (HashMap b) k = undefined
+contains :: forall a. HashMap a -> MapKey -> Bool
+contains (HashMap b) k = isJust $ fromMaybe Nothing (V.find (finder k) b)
 
 -- insert a value into the map
 put :: HashMap a -> MapKey -> a -> HashMap a
-put (HashMap b) k value = undefined
+put h@(HashMap b) k value =
+  if contains h k
+    then h
+    else HashMap $ b `V.snoc` Just (MapPair k value)
 
 -- retrieve a value from the map
-get :: HashMap a -> MapKey -> Maybe a
-get (HashMap b) k = undefined
+get :: forall a. HashMap a -> MapKey -> Maybe a
+get (HashMap b) k = maybe Nothing extractValue (V.find (finder k) b)
+  where
+    extractValue :: Maybe (MapPair a) -> Maybe a
+    extractValue = fmap pairValue
 
 -- delete a value from the map
 delete ::  HashMap a -> MapKey -> HashMap a
diff --git a/src/Data/Workshop/ListMap.hs b/src/Data/Workshop/ListMap.hs
index ded2bc7..e22381d 100644
--- a/src/Data/Workshop/ListMap.hs
+++ b/src/Data/Workshop/ListMap.hs
@@ -21,27 +21,27 @@ data ListMap a = ListMap [(MapKey,a)]
 
 -- create an empty map
 empty :: ListMap a
-empty = undefined
+empty = ListMap []
 
 -- return the number of items in the map
 size :: ListMap a -> Int
-size (ListMap pairs) = undefined
+size (ListMap pairs) = length pairs
 
 -- determine whether the map is empty
 isEmpty :: ListMap a -> Bool
-isEmpty m = undefined
+isEmpty m = size m == 0
 
 -- return all keys in the map
 keys :: ListMap a -> [MapKey]
-keys (ListMap pairs) = undefined
+keys (ListMap pairs) = map fst pairs
 
 -- return all values in the map
 values :: ListMap a -> [a]
-values (ListMap pairs) = undefined
+values (ListMap pairs) = map snd pairs
 
 -- determine whether the map contains a key or not
 contains :: ListMap a -> MapKey -> Bool
-contains m k = undefined
+contains m k = k `elem` keys m
 
 -- insert a value into the map
 put :: ListMap a -> MapKey -> a -> ListMap a
@@ -49,15 +49,17 @@ put m k v = undefined
 
 -- retrieve a value from the map
 get :: ListMap a -> MapKey -> Maybe a
-get (ListMap pairs) k = undefined
+get (ListMap pairs) k = lookup k pairs
 
 -- delete a value from the map
 delete ::  ListMap a -> MapKey -> ListMap a
-delete (ListMap pairs) k = undefined
+delete (ListMap pairs) k = ListMap newPairs
+  where
+    newPairs = filter (\p -> fst p == k) pairs
 
 -- clear all values from the map
 clear :: ListMap a -> ListMap a
-clear _ = undefined
+clear _ = empty
 
 dump :: Show a => ListMap a -> String
 dump (ListMap pairs) = undefined
-- 
2.8.3