データ構造列伝

Haskellの世界にはたくさんのデータ構造があり、魅力の一つであるとも言える。とは言え、どれを使えばいいのかは悩みの種。Haskellで実装されている様々なデータ構造の特徴と使い方を紹介する。

リスト

難易度: ☆

data [] a = a : [a] | []

誰もが真っ先に触れるであろうデータ構造、リスト。順番に処理したいデータをまとめる構造としては王道中の王道だ。また、多くのデータ構造はリストとの相互変換をする関数を提供している。

リストを構築する手段は多数ある。

  • コンストラクタ(:)[]で直接構築する
  • リテラル [0,1,2,3]
  • FromThenTo記法 [0,2..12]
  • 構築関数 unfoldr, iterate, replicate, repeatなど

逐次的な処理のための表現だけでなく、他の構造への橋渡しとしてもリストは重要な役割を担っている。

利点

  • 扱いが簡単で、リストを取るまたは返す関数がたくさんある

欠点

セルオートマトン

以下はルール110のセルオートマトンの実装である。多くの関数がPreludeにあるのもリストの利点だ。

rule110 :: Bool -> Bool -> Bool -> Bool
rule110 False a b = a || b
rule110 True a b = a /= b

automata :: (Bool -> Bool -> Bool -> Bool) -> [Bool] -> [Bool]
automata f xs = go ([False, False] ++ xs ++ [False, False]) where
  go (x : ys@(y : z : _)) = f x y z : go ys
  go _ = []

main = putStr $ unlines
  $ map (map (\b -> if b then '.' else ' '))
  $ take 80
  $ iterate (automata rule110) [True]

Set

難易度: ☆☆

Setはその名の通り集合を表すデータ構造で、順序と重複の概念がない。要素を追加・削除するinsertdelete、要素の存在を確かめるmemberが基本操作となる。

insert :: Ord a => a -> Set a -> Set a
delete :: Ord a => a -> Set a -> Set a
member :: Ord a => a -> Set a -> Bool

もちろん集合演算もあり、小さい方をmとして計算量はO(m*log(n/m + 1))となかなか優秀だ。

union :: Ord a => Set a -> Set a -> Set a
difference :: Ord a => Set a -> Set a -> Set a
intersection :: Ord a => Set a -> Set a -> Set a

必要な場面はそこまで多くはないが、要素の有無を確かめたり、集合の演算を使いたい時に気軽に持ち出せる。

利点

  • 各種操作が速く使いやすい

欠点

  • 要素の比較演算にパフォーマンスが左右される

速いnub

Setを利用するとリストの重複をData.List.nubよりも効率よく取り除ける。

import qualified Data.Set as Set

ordNub :: Ord a => [a] -> [a]
ordNub xs = foldr (\x k s -> if Set.member x s
  then k s
  else x : k (Set.insert x s))
  (const []) xs Set.empty

Heap

難易度: ☆

heapsのData.Heapは、Bootstrapped skew binomial heapの実装である。Setと違い、重複した要素を持つことができる。

insert :: a -> Heap a -> Heap a
viewMin :: Ord a => Heap a -> Maybe (a, Heap a)

挿入だけでなく、結合(mappend)も定数時間なのが面白い、クセの少ない構造である。

タプルとよく似たEntry型が定義されており、大小比較がpriorityフィールドに基づいて行われる。優先度付きキューとして使うときに有用だ。

data Entry p a = Entry { priority :: p, payload :: a }

利点

  • 優秀なヒープの実装である

欠点

  • 挿入・取り出し・結合以外の操作はやや苦手

トップ3

標準入力から受け取った整数のうち、トップ3を表示する。

insertN :: Ord a => Int -> a -> H.Heap a -> H.Heap a
insertN n a h = case H.insert a h of
  h' | H.size h' <= n -> h'
     | otherwise -> H.deleteMin h'

main = interact $ unlines . map show . toList
  . foldl' (flip $ insertN 3) H.empty
  . map (read :: String -> Int) . lines

Seq

難易度: ☆☆☆

containersのData.Sequenceモジュールは2-3 Finger treeというデータ構造を実装している。

要素の追加・削除を含め、両端へのアクセスはO(1)、任意の要素でもO(log n)と、カタログスペックは優秀だ。しかし、リストと比べると、オーダーは同じでも定数倍の違いは大きく、実は使いこなすのが難しい上級者向けの構造だ。

<|演算子で左に要素を追加する。

(<|) :: a -> Seq a -> Seq a

|>演算子で右に要素を追加する。

(|>) :: Seq a -> a -> Seq a

左端の要素はviewlで取り出す。

viewl :: Seq a -> ViewL a
data ViewL = EmptyL | a :< (Seq a)

右端の要素はviewrで取り出す。

viewr :: Seq a -> ViewL a
data ViewL = EmptyR | Seq a :> a

結合(mappend)もsplitAtも対数時間である。

splitAt :: Int -> Seq a -> (Seq a, Seq a) -- O(log(min(i, n - i)))

両端のアクセスが定数時間であるという性質を生かし、手軽なキューとしてしばしば使われる。 永続性を生かしつつ様々な操作をバランスよく組み合わせたいという状況に刺さることもある。

利点

  • 操作が充実しており、オーダーも良い
  • 要素数が多いほど時間計算量の面で有利

欠点

  • 利点を生かしにくい

例 TBD

fingertree

テキストエディタyiやパーサーコンビネータtrifectaでは、亜種のfingertree を文字列の表現に活用している。新たな型変数vに位置を、要素としてバイト列を当てはめることで、柔軟かつ高速な文字列の操作を実現できる。

配列(Boxed Vector)

難易度: ☆☆

vectorパッケージでは、一次元の配列Vectorが定義されている。配列なので、要素へのアクセス(index)が定数時間である。要素数が変わらないような演算、例えばmapzipWithなどを多用するときに適している。

要素を更新したいときはaccumでまとめて更新するとお得だ。

accum :: (a -> b -> a)
  -> Vector a
  -> [(Int, b)]
  -> Vector a

個々の要素の更新は得意ではなく、それが必要な場合はMVectorというミュータブルな表現に一度変換する必要がある。基本は簡単だが、性能を活かそうとなるとややテクニカルな側面がある。

Data.Vector.UnboxedData.Vector.Storableという変種もあり、要素の型に制約がある代わり、より高いメモリ効率とパフォーマンスを持つ。Data.Vector.StorableはFFIを使う際のマストアイテムだ。

利点

  • 定数時間で要素にアクセスできる
  • 融合変換が充実しており、 高速なコードになりやすい
  • メモリ効率が良い

欠点

 consのような構造が変わる操作は、線形時間を使って丸々作り直さないといけない チューニングが難しい

任意の範囲について、平均を定数時間で得られる表現を作る。

import qualified Data.Vector.Unboxed as U

newtype Integrated a = Integrated (U.Vector a) deriving Show

integrate :: (Num a, U.Unbox a) => [a] -> Integrated a
integrate = Integrated . U.postscanl' (+) 0 . U.fromList

average :: (Fractional a, U.Unbox a) => Integrated a -> Int -> Int -> a
average (Integrated v) i j = (v U.! j - v U.! i) / fromIntegral (j - i + 1)