haskell - 在 Haskell 中创建哈希表

Question

我想在 Haskell 中创建一个 HashTable，在里面插入哈希值并在这个 HashTable 中查找。

我找到了 documentation 但是我刚开始使用 Haskell，因此我真的不知道如何使用这些功能。

如果你们中的一些人可以向我展示一些代码行，那将是完美的。

Answer 1

我赞同 Ingo 关于从更简单的事情开始的评论。但是，我将详细介绍一些内容。

首先，我假设你已经安装了最新的 Haskell Platform .在平台的网站上有a page with collected documentation for the libraries included with it .任何不在该页面中的库都需要单独安装。

该平台确实包括Data.HashTable ，所以你不需要安装任何东西，但是如果你看一下 the latest Platform's documentation on it ，您会看到它已被弃用并很快将被删除。所以我不会使用那个模块。

Haskell 平台带有 map /字典数据结构的两个最流行的 Haskell 实现:

Data.Map . (这方面的大部分文档都在 Data.Map.Lazy 中。)这将映射实现为一种平衡搜索树，这意味着键需要是有序类型——一种实现 Ord 的类型。类(class)。许多内置的 Haskell 类型已经实现了这个类，所以一开始这可能是你最容易的选择。

Data.HashMap模块层次结构，有两种变体； Data.HashMap.Lazy 将是一个很好的起点。这将映射实现为一种哈希表，因此键需要实现 Hashable 类(class)。此类较新，不如 Ord 受欢迎。 ，因此您可能经常需要为您的键类型实现此类。

所以 Data.Map是更容易使用的类型。但是要有效地使用它，除了最基本的语言结构之外，您还需要了解一些事情:

如何在源文件中导入模块。

如何使用合格进口— Data.Map具有与 Haskell 中的许多内置函数名称冲突的函数名称，这需要一些特殊的语法。

如何将模块加载到 ghci 解释器中。

如何编译使用 containers 的项目图书馆Data.Map生命(使用 cabal 工具)。

完成后，构建映射的最简单方法是使用键/值对列表:

module MyModule where

import Data.Map (Map)             -- This just imports the type name
import qualified Data.Map as Map  -- Imports everything else, but with names 
                                  -- prefixed with "Map." (with the period).

-- Example: make a Map from a key/value pair
ages :: Map String Integer
ages = Map.fromList [("Joe", 35), ("Mary", 37), ("Irma", 16)]

关于如何使用 map 的几个例子:

-- Example: look up somebody and return a message saying what their age is.
-- 'Nothing' means that the map didn't have the key.
findAge :: String -> String
findAge name = case Map.lookup name ages of
                 Nothing  -> "I don't know the age of " ++ name ++ "."
                 Just age -> name ++ " is " ++ show age ++ " years old."

-- Example: make a map with one extra entry compared to `ages` above.
moreAges :: Map String Integer
moreAges = Map.insert "Steve" 23 ages

-- Example: union of two maps.
evenMoreAges :: Map String Integer
evenMoreAges = Map.union moreAges anotherMap
    where anotherMap = Map.fromList [("Metuselah", 111), ("Anuq", 3)]