Thu Jul 04 2019

Haskell で BFS

Haskell にあるリスト (linked-list, cons-list) は実質そのままスタックとして用いることができる. そして深さ優先探索 (DFS) はスタックに次訪れる状態を入れることで書けるのでとても相性がよく、Haskell で DFS は簡単である. この双対となるのが幅優先探索 (BFS) であり、これはキューに次訪れる状態を入れて持てば簡単に書ける. Haskell で BFS する方法として以前には余再帰を書いた taglibro/2014/06/16 のが、もう余再帰がなんだかわからんし、このコードも読めないので二度と書ける自信がない.

そういえばキューというのはスタック2つで表現できる. その実現方法は簡単で適当にググれば出てくる (例: スタック2つでキューを作る ).

これ使えば難しい概念を使わなくても BFS も簡単に書けることに気づいた.

data Tree = Leaf | Node Int Tree Tree deriving Show

-- ダミーデータとして完全2分木を使う
nibun :: Int -> Tree
nibun n = nibun_sub n 0
    where
      nibun_sub 0 i = Leaf
      nibun_sub n i = Node i (nibun_sub (n - 1) (2 * i + 1)) (nibun_sub (n - 1) (2 * i + 2))


-- まずはスタック一つで深さ優先探索
-- 訪れたノードを返すことにする
dfs :: Tree -> [Int]
dfs tr = dfs_sub tr [] []
  where
    dfs_sub Leaf [] order = reverse order
    dfs_sub Leaf (x:xs) order = dfs_sub x xs order
    dfs_sub (Node val left right) stack order = dfs_sub left (right:stack) (val:order)


-- 次はスタック2つをもたせる
-- 1つ目が push 用で二つ目が pop 用 (一番最後のリストは訪れた順を保存して最後に返す用)
bfs :: Tree -> [Int]
bfs tr = bfs_sub tr [] [] []
  where
    bfs_sub tr q@(x:xs) [] order = bfs_sub tr [] (reverse q) order  -- queue
    bfs_sub Leaf [] [] order = reverse order
    bfs_sub Leaf queue_left (x:xs) order = bfs_sub x queue_left xs order
    bfs_sub (Node val left right) [] [] order = bfs_sub left [] [right] (val:order)
    bfs_sub (Node val left right) queue_left (x:xs) order = bfs_sub x (left:right:queue_left) xs (val:order)


main :: IO ()
main = do
  print $ tr
  print $ dfs tr
  print $ bfs tr
    where
      tr = nibun 3