プログラミングの経験はあるが、Haskell は使ったことがない人に、2時間ぐらいで Haskell のよさを教える演習のネタを考える。
Haskell の代表的な利点といえば、
- 型による厳密なプログラミング
- QuickCheck によるテストケースの自動生成
- Persec によるパーサーの作成
だ。今回は、パーサーの作成は諦めて、上2つについて教えてみる。
リストの探索プログラム
まず、連想リストを探索するプログラムを書く。標準では lookup という関数が用意されているが、これを search という名前で再発明する。オーダーは O(n)。
まず、型を考える。
search :: Eq k => k -> [(k,v)] -> Maybe v search = undefined
次に、実装を考える。
search :: Eq k => k -> [(k,v)] -> Maybe v search _ [] = Nothing search k ((xk,xv):xs) | k == xk = Just xv | otherwise = search k xs
実際には、雛形を見せて、穴埋め問題にする。ポイントとしては、
- 基底部の定義
- 再帰部の定義
- 枝分かれの末端で型が合っているか？
実際に動かしてみる。
search "bar" [("foo",1),("bar",2),("baz",3)] → Just 2
QuickCheck (0)
モデル実装 lookup に対して、search をテストする。lookup と search の定義はまったく同じなので本当は意味がない。でも、lookup の実装は異なると考えて、QuickCheck の練習をする。
import Test.QuickCheck prop_model0 :: String -> [(String, Int)] -> Bool prop_model0 k xs = search k xs == lookup k xs
テストしてみる。
quickCheck prop_model0 +++ OK, passed 100 tests.
探索木の定義
次に探索木での実装を考える。Haskell なら、木の定義は楽勝。すご過ぎると、おもちゃに見えるよ。
data Tree k v = Empty | Node k v (Tree k v) (Tree k v) deriving Show
今回は木のバランスは考えない。ランダムな入力に対しては、適度にバランスして、O(log n) となる。
バランスについては、時間があれば最後に方針だけ示す。
木の生成(1)
次に empty と singleton を定義する。
empty :: Tree k v empty = Empty singleton :: k -> v -> Tree k v singleton k v = Node k v Empty Empty
これは間違えようがないだろう。
木の生成(2)
次に insert を考える。型は次の通り。
insert :: Ord k => k -> v -> Tree k v -> Tree k v insert = undefined
子供が変化したら、ノードは新しく生成しないといけないことが、分かってない人の誤った実装。
insert :: Ord k => k -> v -> Tree k v -> Tree k v insert k v Empty = singleton k v insert k v (Node xk xv l r) | k < xk = insert k v l | otherwise = insert k v r
動かしてみる。
insert "bar" 2 $ insert "foo" 1 empty → Node "bar" 2 Empty Empty
あらら、"foo" が消えちゃった。ちゃんと、ノードは新しく生成しましょう。
insert :: Ord k => k -> v -> Tree k v -> Tree k v insert k v Empty = singleton k v insert k v (Node xk xv l r) | k < xk = Node xk xv (insert k v l) r | otherwise = Node xk xv l (insert k v r)
動かしてみる。
insert "bar" 2 $ insert "foo" 1 empty → Node "foo" 1 (Node "bar" 2 Empty Empty) Empty
実は、このコードにもわざとバグを入れてあるのだけれど、それは QuickCheck のときのお楽しみ。
fromList
便利なように fromList を定義しておく。fold については、今回は深追いしない。でも、fold が分かる人は、関数プログラミングが分かる人だ、ぐらいは言うかも。
fromList :: Ord k => [(k,v)] -> Tree k v fromList xs = foldl insert' empty xs where insert' t (k,v) = insert k v t
動かしてみる。
fromList [("foo",1),("bar",2)] → Node "foo" 1 (Node "bar" 2 Empty Empty) Empty
木の探索
木を探索する関数 searchTree を書く。
searchTree :: Ord k => k -> Tree k v -> Maybe v searchTree _ Empty = Nothing searchTree k (Node xk xv l r) | k == xk = Just xv | k < xk = searchTree k l | otherwise = searchTree k r
動かしてみる。
searchTree "foo" $ fromList [("foo",1),("bar",2)] → Just 1
QuickCheck (1)
search というモデル実装に対して、searchTree がうまく動くかテストする。
import Test.QuickCheck prop_model1 :: String -> [(String, Int)] -> Bool prop_model1 k xs = search k xs == searchTree k t where t = fromList xs
テストしてみる。
quickCheck prop_model1 +++ OK, passed 100 tests.
うまくいっていそう。
QuickCheck (2)
リストは左から探索していたけれど、右から探索してもよいはず。
prop_model2 :: String -> [(String, Int)] -> Bool prop_model2 k xs = search k xs' == searchTree k t where xs' = reverse xs t = fromList xs
テストしてみる。
quickCheck prop_model2 *** Failed! Falsifiable (after 51 tests and 30 shrinks): "" [("",0),("",1)]
あれれれ？
あ、キーが重複することを考えていなかった。
searchTree を直す
キーが重複するときは、新しい値で更新することにする。
insert :: Ord k => k -> v -> Tree k v -> Tree k v insert k v Empty = singleton k v insert k v (Node xk xv l r) | k == xk = Node k v l r -- ここを追加 | k < xk = Node xk xv (insert k v l) r | otherwise = Node xk xv l (insert k v r)
テストしてみる。
quickCheck prop_model2 +++ OK, passed 100 tests.
OK です。prop_model1 は、間違ったテストなので捨てましょう。
