An association list is a list of tuples of keys to values. For example:
alist :: [(String,Double)]
alist = [("pi", 3.14159265), ("e", 2.71828183), ("phi", 1.61803398874)]
getConstant :: String -> Maybe Double
getConstant name = lookup name alist
lookupis a prelude function that returns the value (if existing) for the supplied key. Association lists are useful for small lists, but the lookup time is O(N) in the size of elements. Enter Map which provides the same key/value abstraction but with efficient lookup.
Data.Mapprovides operations for insertion, deletion and inspection of keys. For example:
-- Given an association list, make a map
-- Insert a new key/value into the empty map
Map.insert "pi" 3.14159265 $ Map.empty
-- Is a key in a map?
Map.member key map
-- lookup and findWithDefault allow you to find values.
$ is the function application operator - it's right associative so it means less brackets.
Data.Setprovides a functional implementation of sets.
We can put these together and change the implementation of the anagrams to create a map of search key to a set of results. This is hideously inefficient initially, but once the data structure is built up finding anagrams should be a little quicker.
anagramList :: String -> IO (Map String (Set String))
anagramList file = do
filecontent <- readFile file
return (foldl (\x y -> Map.insertWith Set.union (stringToKey y) (Set.singleton y) x)
(filter validWord $ lines filecontent))
anagramsOf :: String -> IO ()
anagramsOf word = do
anagrams <- anagramList wordfile
putStrLn (show (Map.lookup (stringToKey word) anagrams))