なぜ Haskell ではキューが軽んじられているか？

Haskell ではキューが欲しくなったら Data.Sequence を使えと言われる。Seq は両端キューだし、シーケンスとして使えば、連結(><)や分割(splitAt)が、ならし計算量で O(log N) という優れものである。しかし、内部がfinger treeなのでコードが複雑なのと、計算量が「ならし」なところが玉に傷である。

もっと単純で、最悪計算量を保証する(両端でない)キューが標準で提供されてもいい気がする。その候補には、リアルタイムキューがある。どうして標準でキューが提供されないのだろう？ 僕なりの答えは「需要がない」だ。

問題を解くときにスタックはよく使うが、キューが必要な問題はそんなに思いつかない。僕はネットワーク屋なので、もちろんルータにはキューが必要なことは知っているが、それ以外で有名どころと言えば幅優先探索ぐらいだ。

幅優先探索

でも、Haskellではキューを使わなくても幅優先探索を実装できる。そう、遅延評価だから、余再帰というテクニックが使える。実際のコードはこう。

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Show

breadthFirst :: Tree a -> [a]
breadthFirst t = postprocess queue
  where
    queue = t : walk 1 queue
    postprocess = map extract . filter isNode
    
walk :: Int -> [Tree a] -> [Tree a]
walk 0 _                = []
walk n (Leaf : q)       = walk (n - 1) q
walk n (Node l _ r : q) = l : r : walk (n + 1) q
walk _ _                = error "walk"

extract :: Tree t -> t
extract (Node _ x _) = x
extract _            = error "extract"
    
isNode :: Tree t -> Bool
isNode (Node _ _ _) = True
isNode _            = False

queue の部分が余再帰である。呼び出される walk は、無限ループに陥らないように、キューの長さを管理している。引数のキューからは要素が一個取り除かれる。生成するキューで要素が何個付け加えられるかをよく見れば、どう長さを管理しているか理解できるだろう。

postprocess は Leaf を取り除き、Node から値を取り出しているだけなので、本質的な部分ではない。

使ってみよう：

breadthFirst (Node (Node (Node Leaf 3 Leaf) 2 (Node Leaf 4 Leaf)) 1 (Node (Node Leaf 6 Leaf) 5 (Node Leaf 7 Leaf)))
→ [1,2,5,3,4,6,7]

という訳で、一番需要のありそうな幅優先探索でも、別途キューのライブラリは必要なかった。

深さ優先探索

おまけで、深さ優先探索のコードも載せておく。まず、素朴に ++ を使う実装：

preorder :: Tree a -> [a]
preorder Leaf          = []
preorder (Node l x r)  = [x] ++ preorder l ++ preorder r

inorder :: Tree a -> [a]
inorder Leaf           = []
inorder (Node l x r)   = inorder l ++ [x] ++ inorder r

postorder :: Tree a -> [a]
postorder Leaf         = []
postorder (Node l x r) = postorder l ++ postorder r ++ [x]

効率をよくするために ++ を取り除いた実装はこう：

preorder :: Tree a -> [a]
preorder t = go t []
  where
    go Leaf xs         = xs
    go (Node l x r) xs = x : (go l (go r xs))

inorder :: Tree a -> [a]
inorder t = go t []
  where
    go Leaf xs         = xs
    go (Node l x r) xs = go l (x : (go r xs))

postorder :: Tree a -> [a]
postorder t = go t []
  where
    go Leaf xs         = xs
    go (Node l x r) xs = go l (go r (x : xs))

深さ優先探索の話も詳しく載っている書籍は見たことがないので、このコードも少しは参考になるかも。