Skip to content

Instantly share code, notes, and snippets.

@rob-b
Created September 23, 2016 07:57
Show Gist options
  • Save rob-b/a7487ec460f6fe8cddf0b4e1a8adfa10 to your computer and use it in GitHub Desktop.
Save rob-b/a7487ec460f6fe8cddf0b4e1a8adfa10 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment