Some Haskell Data Structures

So far I've seen the list data structure, but Haskell also supports items like Maps and Sets.

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

lookup is 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.Map provides operations for insertion, deletion and inspection of keys. For example:


-- Given an association list, make a map
Map.fromList aList

-- 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.

Similarly, Data.Set provides 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)
                  Map.empty 
                  (filter validWord $ lines filecontent))

  anagramsOf :: String -> IO ()
  anagramsOf word = do
    anagrams <- anagramList wordfile
    putStrLn (show (Map.lookup (stringToKey word) anagrams))