Haskell/Hierarchical libraries/Maps

From Wikibooks, the open-content textbooks collection

The module Data.Map provides the Map datatype, which allows you to store values attached to specific keys. This is called a lookup table, dictionary or associative array in other languages.

[edit] Motivation

Very often it would be useful to have some kind of data structure that relates a value or list of values to a specific key. This is often called a dictionary after the real-world example: a real-life dictionary associates a definition (the value) to each word (the key); we say the dictionary is a map from words to definitions. A filesystem driver might keep a map from filenames to file information. A phonebook application might keep a map from contact names to phone numbers. Maps are a very versatile and useful datatype.

[edit] Why not just [(a, b)]?

You may have seen in other chapters that a list of pairs (or 'lookup table') is often used as a kind of map, along with the function lookup :: [(a, b)] -> a -> Maybe b. So why not just use a lookup table all the time? Here are a few reasons:

• Working with maps gives you access to a whole load more useful functions for working with lookup tables.
• Maps are implemented far more efficiently than a lookup table would be, both in terms of speed and the amount of memory it takes up.

[edit] Definition

Internally, maps are defined using a complicated datatype called a balanced tree for efficiency reasons, so we don't give the details here.

[edit] Library functions

The module Data.Map provides an absolute wealth of functions for dealing with Maps, including setlike operations like unions and intersections. There are so many we don't include a list here; instead the reader is defered to the hierarchical libraries documentation for Data.Map.

[edit] Example

The following example implements a password database. The user is assumed to be trusted, so is not authenticated and has access to view or change passwords.

{- A quick note for the over-eager refactorers out there: This is (somewhat)
   intentionally ugly. It doesn't use the State monad to hold the DB because it
   hasn't been introduced yet. Perhaps we could use this as an example of How
   Monads Improve Things? -}

module PassDB where

import qualified Data.Map as M
import System.Exit

type UserName = String
type Password = String
type PassDB   = M.Map UserName Password 
  -- PassBD is a map from usernames to passwords

-- | Ask the user for a username and new password, and return the new PassDB
changePass :: PassDB -> IO PassDB
changePass db = do
  putStrLn "Enter a username and new password to change."
  putStr "Username: "
  un <- getLine
  putStrLn "New password: "
  pw <- getLine
  if un `M.member` db               -- if un is one of the keys of the map
    then return $ M.insert un pw db -- then update the value with the new password
    else do putStrLn $ "Can't find username '" ++ un ++ "' in the database."
            return db

-- | Ask the user for a username, whose password will be displayed.
viewPass :: PassDB -> IO ()
viewPass db = do
  putStrLn "Enter a username, whose password will be displayed."
  putStr "Username: "
  un <- getLine
  putStrLn $ case M.lookup un db of
               Nothing -> "Can't find username '" ++ un ++ "' in the database."
               Just pw -> pw

-- | The main loop for interacting with the user. 
mainLoop :: PassDB -> IO PassDB
mainLoop db = do
  putStr "Command [cvq]: "
  c <- getChar
  putStr "\n"
  -- See what they want us to do. If they chose a command other than 'q', then
  -- recurse (i.e. ask the user for the next command). We use the Maybe datatype
  -- to indicate whether to recurse or not: 'Just db' means do recurse, and in
  -- running the command, the old datbase changed to db. 'Nothing' means don't
  -- recurse.
  db' <- case c of
           'c' -> fmap Just $ changePass db
           'v' -> do viewPass db; return (Just db)
           'q' -> return Nothing
           _   -> do putStrLn $ "Not a recognised command, '" ++ [c] ++ "'."
                     return (Just db)
  maybe (return db) mainLoop db'

-- | Parse the file we've just read in, by converting it to a list of lines,
--   then folding down this list, starting with an empty map and adding the
--   username and password for each line at each stage.
parseMap :: String -> PassDB
parseMap = foldr parseLine M.empty . lines
    where parseLine ln map = 
            let [un, pw] = words ln
            in M.insert un pw map

-- | Convert our database to the format we store in the file by first converting
--   it to a list of pairs, then mapping over this list to put a space between
--   the username and password
showMap :: PassDB -> String
showMap = unlines . map (\(un, pw) -> un ++ " " ++ pw) . M.toAscList

main :: IO ()
main = do
  putStrLn $ "Welcome to PassDB. Enter a command: (c)hange a password, " ++
             "(v)iew a password or (q)uit."
  dbFile <- readFile "/etc/passdb"
  db'    <- mainLoop (parseMap dbFile)
  writeFile "/etc/passdb" (showMap db')

Exercises
FIXME: write some exercises