Haskell/库/映射

映射

库参考

模块 Data.Map 提供了 Map 数据类型，它允许您存储附加到特定键的值。这在其他语言中被称为查找表、字典或关联数组。

动机

通常，拥有某种数据结构来将值或值列表关联到特定键将非常有用。这通常被称为字典，源于现实世界中的例子：现实生活中的字典将定义（值）与每个单词（键）关联起来；我们说字典是 从单词到定义的映射。文件系统驱动程序可能会保留一个从文件名到文件信息的映射。电话簿应用程序可能会保留一个从联系人姓名到电话号码的映射。映射是一个非常通用和有用的数据类型。

为什么不直接使用 `[(a, b)]`?

您可能在其他章节中看到，成对列表（或“查找表”）通常用作一种映射，以及函数 lookup :: a -> [(a, b)] -> Maybe b。那么为什么不一直使用查找表呢？以下是一些原因

使用映射可以让您访问大量更实用的函数来处理查找表。
映射的实现效率远高于查找表，尤其是在查找速度方面。^[1]

库函数

模块 Data.Map 提供了大量用于处理映射的函数，包括集合操作，例如并集和交集。完整的列表可以在核心库文档中找到。^[2]

示例

以下示例实现了一个密码数据库。假设用户是可信的，因此没有经过身份验证，可以访问查看或更改密码。

 {- 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 "passdb"
   db'    <- mainLoop (parseMap dbFile)
   writeFile "passdb" (showMap db')