2011年11月18日金曜日

LeftistHeap in Haskell

Leftist Heapとは、Purely Functional Data Structuresによると、
Heap-ordered binary tees that satisfy the leftist property: the rank of any left child is at least as large as the rank of its right sibling. The rank of a node is defined to be the length of its right spine (i.e., the rightmost path from the node in question to an empty node).
という性質をもつHeapです。

同書に載っているML, Haskellによる実装では、insertはmergeを使ってinsert x h = merge (T 1 x E E) hとなっていますが、これを「mergeを使わずに実装せよ」というのが、Exercise 3.2です。

挿入先のHeap(以降h)がEmptyな場合は簡単で、xのみを要素として持つHeapを返せばよい: insert x E = T 1 x E E

hがEmptyじゃない場合は、現在のminimum value (以下 m)と x との大小関係によって、更に場合分けします。Heap-ordered treeなので、あるノードの値は、子ノードの値よりも小さいか等しくないといけないからです。

xがmより小さいか等しい場合は、xをルートノードにすればよい: makeT x h E
もしくは、makeTを展開して: T 1 x h E

xがmより大きい場合は、hの子のどちらかにxを挿入します。つまり、insertを再帰的に呼び出します: makeT (hの値) (hの子供1) $ insert x (hの子供2)

まとめると、
insert x E    = T 1 x E E
insert x h@(T _ y a b)
  | x <= y    = makeT x h E
  | otherwise = makeT y a $ insert x b
となります。ちなみに、最後の行のaとbは入れ替えてもよい(はず)。

これが正しく動くことを確認したいので、この辺を参考にしてQuickCheckを使ってみました。
QuickCheckは、テスト関数(テストデータ -> Bool)を与えると、テストデータを生成して、期待通りの結果が出るか調べてくれるツールのようです。

今回は、
  1. 整数のリストを受け取る
  2. LeftistHeapに挿入する
  3. リストをsortする
  4. findMinとリストの先頭の値が等しいかをチェックし、等しくなければFalse、等しければ、deleteMinとcdrを再帰的にチェック
とすればテストになるので、テスト関数を
test :: [Int] -> Bool
test ns = test' lh $ sort ns
  where
    lh :: LeftistHeap Int
    lh = foldl (\h n -> LeftistHeap.insert n h) empty ns

    test' :: (LeftistHeap Int) -> [Int] -> Bool
    test' _ []          = True
    test' h (m:ms)      = findMin h == m && test' (deleteMin h) ms
と定義して、ghciで実行。
orange:~/work/pfds% ghci -Wall         
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :l TestLeftistHeap.hs 
[1 of 3] Compiling Heap             ( Heap.hs, interpreted )
[2 of 3] Compiling LeftistHeap      ( LeftistHeap.hs, interpreted )
[3 of 3] Compiling TestLeftistHeap  ( TestLeftistHeap.hs, interpreted )

TestLeftistHeap.hs:4:1:
    Warning: The import of `Test.QuickCheck' is redundant
               except perhaps to import instances from `Test.QuickCheck'
             To import instances alone, use: import Test.QuickCheck()
Ok, modules loaded: TestLeftistHeap, LeftistHeap, Heap.
*TestLeftistHeap> quickCheck test
Loading package extensible-exceptions-0.1.1.2 ... linking ... done.
Loading package old-locale-1.0.0.2 ... linking ... done.
Loading package time-1.2.0.3 ... linking ... done.
Loading package random-1.0.0.3 ... linking ... done.
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
Loading package pretty-1.0.1.2 ... linking ... done.
Loading package template-haskell ... linking ... done.
Loading package QuickCheck-2.4.1.1 ... linking ... done.
+++ OK, passed 100 tests.

正しく動いてるっぽい。

[追記 2011-12-23] TestFrameworkを使った版

0 件のコメント:

コメントを投稿