算法算法图解笔记广度优先搜索-Haskell代码实现

之前的广度优先遍历没有 Haskell 代码的实现，这里补上。下面代码使用了 unordered-containers 包的哈希表，用来实现图；containers 包的 Seq 类型，用来实现队列，主要是因为使用内置的列表类型效率太差。

module Main where

import qualified Data.HashMap.Strict as HM
import           Data.Maybe (fromJust)
import qualified Data.Sequence       as DS

graph :: HM.HashMap String [String]
graph = HM.fromList [("you",["alice", "bob", "claire"]),
                    ("bob", ["anuj", "peggy"]),
                    ("alice", ["peggy"]),
                    ("claire", ["thom", "jonny"]),
                    ("anuj",[]),
                    ("peggy",[]),
                    ("thom",[]),
                    ("jonny",[])
                   ]

personIsSeller :: String -> Bool
personIsSeller name = last name == 'm'

search :: HM.HashMap String [String] -> String -> Bool
search graph name = loop $ DS.fromList (graph HM.! name)
  where loop queue
          | null queue = False
          | personIsSeller h = True
          | otherwise = loop $ (DS.drop 1 queue) DS.>< DS.fromList (graph HM.! h)
          where h = queue `DS.index` 0

main :: IO ()
main = do
  print $ search graph "you"

为了能与 Python 对照，整体风格上与 Python 代码保持一致，包括测试用例、图的实现方式等等。
Haskell 标准模块并不包含一些常用的数据类型，所以，日常开发中需要大量使用其他三方的包，其中 containers 和 unordered-containers 是最常用的容器包。

containers 包含常用的图、树、集合等结构，具体包含 Data.Graph、Data.Tree、Data.Map、Data.IntMap、Data.Set、Data.IntSet、以及例子中使用到的 Data.Sequence 等。

正如名字所示，unordered-containers 包实现了基于无序的数据结构，包含基于哈希的映射和集合。

请继续关注我的公众号文章