在Haskell中创建HashTable

Question

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

我找到了这个文档,但我刚开始使用Haskell,因此我真的不知道如何使用这些函数.

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

Answer 1

我是第二个Ingo关于从更简单的东西开始的评论.但是,我会在一些细节上细分一些事情.

首先,我假设您已经安装了最新的Haskell平台.在平台的网站上有一个页面,其中包含随附的库的收集文档.任何不在该页面中的库都是您需要单独安装的.

平台确实包含Data.HashTable,所以你不需要安装任何东西,但如果你查看最新的平台文档,你会发现它已被弃用,很快就会被删除.所以我不会使用那个模块.

Haskell平台附带了两个最流行的Haskell实现的地图/字典数据结构:

• Data.Map.(大多数文档都是在这里Data.Map.Lazy.)这将地图实现为一种平衡搜索树,这意味着键需要是有序类型 - 实现Ord类的类型.很多内置的Haskell类型已经实现了这个类,所以这可能是你最初的最简单选择.
• 该Data.HashMap模块层次结构,有两个变种; Data.HashMap.Lazy将是一个很好的起点.这将map实现为一种哈希表,因此键需要实现Hashable该类.这个类比较新并且不那么流行Ord,所以通常你可能需要为你的键类型实现这个类.

所以Data.Map更容易使用的类型.但要有效地使用它,你需要了解最基本的语言结构旁边的一些东西:

1. 如何在源文件中导入模块.
2. 如何使用限定导入 - Data.Map具有与Haskell中的许多内置函数冲突的函数名称,这需要一些特殊的语法.
3. 如何将模块加载到ghci解释器中.
4. 如何编译使用生命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)]

有关如何使用地图的几个示例:

-- 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)]

Answer 2

作为 Ingo 答案的补充，请考虑使用纯函数Data.Map。

 import qualified Data.Map as M

 myMap :: M.Map Int String
 myMap = M.fromList $ zip [1..10] ['a'..'j']

 insertedMap :: M.Map Int String
 insertedMap = M.insert 11 "fizzbuzz" oldMap

 at11 :: Maybe String
 at11 = M.lookup 11 insertedMap

然后您可以使用M.lookup、M.insert和许多其他函数来修改/查询地图。这个数据结构也是纯粹的功能性/持久性（注意 IO 是如何在类型中无处可见的）。这意味着我们可以做类似的事情

  let newMap = M.insert key val oldMap
  in M.union oldMap otherMap

看看我们如何在插入一些东西后仍然可以使用旧版本的地图？这就是“持久性”，我们从不破坏旧版本的数据结构。

Answer 3

为了避免有人称 Haskell 社区傲慢，这里是您需要的第一个函数的简短分解：

new :: (key -> key -> Bool) -> (key -> Int32) -> IO (HashTable key val)

这告诉我们以下内容：要为特定键类型创建哈希表，key您需要传递一个检查键相等性的函数，以及一个计算键哈希值的函数。因此，如果eq和hashit是所需的函数，则如下：

new eq hashit

在 IO-Monad 中给你一个空的 HashTable。

一种更简单的方法可能是使用预定义的哈希函数之一从列表创建哈希表：

 fromList hashInt [(42, "forty-two"), (0, "zero")]