あどけない話

インターネットに関する技術的な話など

Haskell演習の草稿

プログラミングの経験はあるが、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 は、間違ったテストなので捨てましょう。