わどぅー

記事については、中間出力の場合も多いので間違ってたらごめんなさい。twitter は waddlaw です。どうぞよろしく。

Data.Set を使ってみよう!

XML Processing の 8.1.1 章にある Top-down algorithm を Haskell で実装してみようと思う。

とりあえず、Haskell で集合を表現するためには Data.Set を利用すれば良いのかな。
以下の情報はGHC 7.2.1 の話です。
http://haskell.org/ghc/docs/7.2.1/html/libraries/containers-0.4.1.0/Data-Set.html

集合を表すデータタイプ

data Set a

実装みてみると

data Set a = Tip 
           | Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) 
type Size     = Int

リストから集合への変換

-- O(n*log n) でリストから集合へ変換
fromList :: Ord a => [a] -> Set a
-- O(n) で昇順リストから集合へ変換 (入力されたリストが昇順かどうかは、この関数でチェックしない)
fromAscList :: Eq a => [a] -> Set a
-- O(n) で異なる要素の昇順リストから集合へ変換 (入力されたリストが昇順かどうかは、この関数でチェックしない)
fromDistinctAscList :: [a] -> Set a

fromList と fromAscList, fromDistinctAscList のはっきりした違いは計算量のようだ。
実装を見てみると

fromList :: Ord a => [a] -> Set a 
fromList = foldlStrict ins empty
  where
    ins t x = insert x t

foldlStrict :: (a -> b -> a) -> a -> [b] -> a
foldlStrict f = go
  where
    go z []     = z
    go z (x:xs) = let z' = f z x in z' `seq` go z' xs

というように、内部で insert (計算量は O(log n) らしい) を呼んでるから O(n*log n) になるのかな。foldlStrict は明らかに O(n) だし。ここで、もしリストが

  • foldlStrict 関数はリストの先頭要素に対して z' = f z x を定義して、seq で正格評価してるから名前通りの動き。

次、fromAscList 関数の実装をみてみよ。

fromAscList :: Eq a => [a] -> Set a 
fromAscList xs
  = fromDistinctAscList (combineEq xs)
  where
  combineEq xs'
    = case xs' of
        []     -> []
        [x]    -> [x]
        (x:xx) -> combineEq' x xx

  combineEq' z [] = [z]
  combineEq' z (x:xs')
    | z==x      =   combineEq' z xs'
    | otherwise = z:combineEq' x xs'
  • Eq クラスのインスタンスという制約はリストの中に同じ要素が含まれている可能性があるから
  • combineEq に入ってくるリストを [1,1,1,2,3] としたとき (リストは昇順であるはず)
combineEq [1,1,1,2,3]
=> combineEq' 1 [1,1,2,3]
=> combineEq' 1 (1:[1,2,3])
=> combineEq' 1 [1,2,3]
=> combineEq' 1 (1:[2,3])
=> combineEq' 1 [2,3]
=> combineEq' 1 (2:[3])
=> 1: combineEq' 2 [3]
=> ...
=> [1,2,3]

よって、combineEq' で重複している要素を取り除いていることがわかる。

最後に、fromDistinctAscList を考察しよ。

fromDistinctAscList :: [a] -> Set a 
fromDistinctAscList xs
  = build const (length xs) xs
  where
    -- 1) スタック空間の代わりにヒープ空間を利用するため継続を使う
    -- 2) n == 5 の場合だけちょっと特別だよ
    build c 0 xs'  = c Tip xs'
    build c 5 xs'  = case xs' of
                       (x1:x2:x3:x4:x5:xx) 
                            -> c (bin x4 (bin x2 (singleton x1) (singleton x3)) (singleton x5)) xx
                       _ -> error "fromDistinctAscList build 5"
    build c n xs'  = seq nr $ build (buildR nr c) nl xs'
                   where
                     nl = n `div` 2
                     nr = n - nl - 1

    buildR n c l (x:ys) = build (buildB l x c) n ys
    buildR _ _ _ []     = error "fromDistinctAscList buildR []"
    buildB l x c r zs   = c (bin x l r) zs
  • const 関数は Prelude の const :: a -> b -> a の定数関数
  • build c 0 xs' は空リストの処理なので、const Tip xs' = Tip でOK
  • build c 5 xs' はリストの要素が5個の場合、
build const 5 [1,2,3,4,5]
=> const (bin 4 (bin 2 (singleton 1) (singleton 3)) (singleton 5)) []
=> const (bin 4 (bin 2 (Bin 1 1 Tip Tip) (Bin 1 3 Tip Tip)) (Bin 1 5 Tip Tip))) []
=> const (bin 4 (Bin 3 2 (Bin 1 1 Tip Tip) (Bin 1 3 Tip Tip)) (Bin 1 5 Tip Tip)) []
=> const (Bin 5 4 (Bin 3 2 (Bin 1 1 Tip Tip) (Bin 1 3 Tip Tip)) (Bin 1 5 Tip Tip)) []
=> (Bin 5 4 (Bin 3 2 (Bin 1 1 Tip Tip) (Bin 1 3 Tip Tip)) (Bin 1 5 Tip Tip))
  • singleton は要素1つだけの集合を作る
  • bin は新しい木を作る
    • この結果を foldr (:) [] に入れると、[1,2,3,4,5] が返ってくる。つまり、左下→真ん中→右下という順番で再帰的に要素を集めてる感じかな(ボトムアップで)
  • 最後に空リストでも、要素が5個でもない場合。
    build c n xs'  = seq nr $ build (buildR nr c) nl xs'
                   where
                     nl = n `div` 2
                     nr = n - nl - 1

    buildR n c l (x:ys) = build (buildB l x c) n ys
    buildR _ _ _ []     = error "fromDistinctAscList buildR []"
    buildB l x c r zs   = c (bin x l r) zs
  • seq nr は nr と nl を先に計算させておくため?
  • buildR, buildB は FOP 1.4章のラウンドロビンヒープの話?
    • わからないから [1,2,3,4,5,6,7] ぐらいの入力例で動きを確認してみよう
fromDistinctAscList [1,2,3,4,5,6,7]
=> build const (length [1,2,3,4,5,6,7]) [1,2,3,4,5,6,7]
=> build const 7 [1,2,3,4,5,6,7]
=> seq 3 $ build (buildR 3 const) 3 [1,2,3,4,5,6,7]
=> build (buildR 3 const) 3 [1,2,3,4,5,6,7]
=> seq 1 $ build (buildR 1 (buildR 3 const)) 1 [1,2,3,4,5,6,7]
=> build (buildR 1 (buildR 3 const)) 1 [1,2,3,4,5,6,7]
=> seq 0 $ build (buildR 0 (buildR 1 (buildR 3 const))) 0 [1,2,3,4,5,6,7]
=> build (buildR 0 (buildR 1 (buildR 3 const))) 0 [1,2,3,4,5,6,7]
=> buildR 0 (buildR 1 (buildR 3 const)) Tip [1,2,3,4,5,6,7]
=> build (buildB Tip 1 (buildR 1 (buildR 3 const))) 0 [2,3,4,5,6,7]
=> buildB Tip 1 (buildR 1 (buildR 3 const)) Tip [2,3,4,5,6,7]
=> buildR 1 (buildR 3 const) (bin 1 Tip Tip) [2,3,4,5,6,7]
=> build (buildB (bin 1 Tip Tip) 2 (buildR 3 const)) 1 [3,4,5,6,7]
=> build (buildR 0 (buildB (bin 1 Tip Tip) 2 (buildR 3 const))) 0 [3,4,5,6,7]
=> buildR 0 (buildB (bin 1 Tip Tip) 2 (buildR 3 const)) Tip [3,4,5,6,7]
=> build (buildB Tip 3 (buildB (bin 1 Tip Tip) 2 (buildR 3 const))) 0 [4,5,6,7]
=> buildB Tip 3 (buildB (bin 1 Tip Tip) 2 (buildR 3 const)) Tip [4,5,6,7]
=> buildB (bin 1 Tip Tip) 2 (buildR 3 const) (bin 3 Tip Tip) [4,5,6,7]
=> buildR 3 const (bin 2 (bin 1 Tip Tip) (bin 3 Tip Tip)) [4,5,6,7]
=>... 

やっぱりラウンドロビンヒープだけど、ボトムアップに構築しているのかぁ。
もう少しで理解できそう、明日もう一度図的に考えてみる。

集合からリストへの変換

-- O(n) で集合の要素からリストへ変換
elems :: Set a -> [a]
-- O(n) で集合からリストへ変換
toList :: Set a -> [a]
-- O(n) で集合から昇順リストへ変換
toAscList :: Set a -> [a]

とりあえず、elems、toList、toAscList の違いがドキュメント読んだだけだとわからん。実装みてみる。

elems :: Set a -> [a]
elems s = toList s

toList :: Set a -> [a]
toList s = toAscList s

toAscList :: Set a -> [a]
toAscList t = foldr (:) [] t

同じじゃん!w ここで気になるのが foldr なんだけど、これは Prelude の foldr ではなくて、内部で定義されている foldr だった。

foldr :: (a -> b -> b) -> b -> Set a -> b
foldr f = go
  where
    go z Tip           = z
    go z (Bin _ x l r) = go (f x (go z r)) l

例として以下の木を foldr してみると

t = (Bin 3 'a' (Bin 1 'b' Tip Tip) (Bin 1 'c' Tip Tip))

foldr (:) [] t
=> go [] (Bin 3 'a' (Bin 1 'b' Tip Tip) (Bin 1 'c' Tip Tip))
=> go ((:) 'a' (go [] (Bin 1 'c' Tip Tip))) (Bin 1 'b' Tip Tip)
=> go ((:) 'b' (go ((:) 'a' (go [] (Bin 1 'c' Tip Tip)))) Tip) Tip
=> (:) 'b' (go ((:) 'a' (go [] (Bin 1 'c' Tip Tip)))) Tip)
=> (:) 'b' {(:) 'a' (go [] (Bin 1 'c' Tip Tip)))}
=> (:) 'b' {(:) 'a' (go ((:) 'c' (go [] Tip))) Tip)}
=> (:) 'b' {(:) 'a' ((:) 'c' (go [] Tip))}
=> (:) 'b' {(:) 'a' ((:) 'c' [])}
=> ['b', 'a', 'c']


変換用の関数 6 個しか考察できなかったので次回に続く。