CS计算机代考程序代写 — ** Faster Keymap implementation using hash tables.

— ** Faster Keymap implementation using hash tables.
{-# LANGUAGE ScopedTypeVariables #-}
module KeymapTable
( gather
, hash
, Keymap
, fromList
, get
, toList
, size
) where

import Test.QuickCheck
import Data.Char (ord)
import GHC.Arr

import qualified KeymapList as L

— * Exercise 4: gather

gather :: Ix i => (i,i) -> [(i,a)] -> [(i,[a])]
gather = undefined

— Hashes and hash tables

type Hash = Int

data Keymap k v = HashTable
(Array Hash (L.Keymap k v)) — an array mapping hashes to keymap lists
Int — capacity
deriving Show

class Hashable a where
hash :: a -> Hash

hashMod :: Hashable a => a -> Int -> Hash
hashMod x cap = hash x `mod` cap

instance Hashable Char where
hash = ord

— * Exercise 5: hashing a list

instance Hashable a => Hashable [a] where
hash s = undefined

— * Exercise 6: fromList

fromList :: forall k v. (Eq k, Hashable k) => [(k, v)] -> Keymap k v
fromList kvs = HashTable arr2 capacity
where
capacity :: Int
capacity = length kvs

— * Exercise 6a: calculating the list-valued array
arr :: Array Hash [(k, v)]
arr = undefined

— * Exercise 6b: calculating the keymap-valued array
arr2 :: Array Hash (L.Keymap k v)
arr2 = undefined

— * Exercise 7: get/toList/size

get :: (Eq k, Hashable k) => k -> Keymap k v -> Maybe v
get = undefined

prop_get :: [(String, Int)] -> Property
prop_get kvs = not (null kvs) ==>
let (k, v) = head kvs in
get k (fromList kvs) == Just v

toList :: (Eq k, Hashable k) => Keymap k v -> [(k, v)]
toList = undefined

prop_fromToList :: [(String, Int)] -> Bool
prop_fromToList kvs = toList (fromList kvs) ~~ kvs

size :: Eq k => Keymap k a -> Int
size = undefined

prop_size :: [(String, Int)] -> Bool
prop_size kvs = size (fromList kvs) == length kvs