Haskell です.
Eq k => [(k, v)] の形をしたリスト t について考えます.
k は Eq クラスを実装した型(*1)
v は任意の型です.
k についてソートされていることを要求しないとします.
k について重複は無いものとします.
t へのデータの挿入・検索・更新・削除は次のように書けます.
lut.hs
import Data.List ins (k,v) t = (k, v):t lup key [] = Nothing lup key ((k, v):ts) | key == k = Just v | otherwise = lup key ts upd (k, v) t = (\(l, r) -> l ++ (k, v):tail r) $ break ((k == ) . fst) t del k t = (\(l, r) -> l ++ (tail r)) $ break ((k ==) . fst) t
使ってみましょう.
ghci のコマンドライン引数に lup.hs を渡すか, 起動後に :l でロードします.
% ghci GHCi, version 6.10.4: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> :l lut.hs [1 of 1] Compiling Main ( lut.hs, interpreted ) Ok, modules loaded: Main. *Main>
とりあえず最初のバージョンのテーブル t を作り, ins で新エントリを挿入してみます.
*Main> let t = [(1, "foo"), (3, "baz"), (2, "bar")] *Main> t [(1,"foo"),(3,"baz"),(2,"bar")] *Main> ins (4, "qux") t [(4,"qux"),(1,"foo"),(3,"baz"),(2,"bar")]
いいですね.
ここで t は変更されないので, 変数の非破壊性についてはまたの機会に述べるとして, とりあえず別の変数に代入します.
*Main> let t2 = ins (4, "qux") t *Main> t2 [(4,"qux"),(1,"foo"),(3,"baz"),(2,"bar")]
Haskell には, Maybe モナドという, 値があるなら Just 値, 値が無いなら Nothing という, エラー処理は上位のコードに任せましょうな統一的な多相型があります.
lup k t は, テーブル t に, キー k であるエントリが見つからなければ Nothing を, 見つかればその値を v として Just v を返します.
*Main> lup 3 t2 Just "baz" *Main> lup 5 t2 Nothing
Maybe なんちゃら型を受け取った上位のコードはどうするかというと, 返り値が Nothing ならばエラー処理をして, そうでないなら fromJust で値を取り出すとか, さらに上位にエラー処理を任せるよう, 別の Maybe 型を返すようにしたりするわけですが, ここではコード片の試験なので, Nothing かどうかチェックせず fromJust を適用して, 実行時例外に任せます.
*Main> :m +Maybe
「:m +」はソースコード中の import 文のようなものです. fromJust が使えるように Maybe モジュールをスコープに追加します.
*Main Maybe> fromJust $ lup 3 t2 "baz" *Main Maybe> fromJust $ lup 5 t2 "*** Exception: Maybe.fromJust: Nothing
更新と削除もやってみます.
*Main Maybe> upd (3, "quux") t2 [(4,"qux"),(1,"foo"),(3,"quux"),(2,"bar")] *Main Maybe> del 3 t2 [(4,"qux"),(1,"foo"),(2,"bar")]
いいようです.
挿入
(k, v) を t に挿入したリストを返す関数は, 元のリストの先頭に要素を追加するだけです.
ins (k,v) t = (k, v):t
今回は, わざわざ関数に名前を付けましたが, t が特定の構造を保つことを要請するようなデータ構造でなければ, 右辺をそのまま書いた方が速いですね.
検索
k が key であるペアを検索してあれば Just v をなければ Nothing を返す関数は
lup key [] = Nothing lup key ((k, v):ts) | key == k = Just v | otherwise = lup key ts
と書けます. 今回はわざわざ書きましたが, 標準ライブラリ Prelude に含まれる lookup でまったく同じことができますので, 特に理由がなければ, 標準の lookup を使えばよいでしょう.
更新
k をキーとする要素の値を v で置き換えます.
upd (k, v) t = (\(l, r) -> l ++ (k, v):tail r) $ break ((k == ) . fst) t
break f t は, 「ある型の値を引数にとって Bool 値を返す関数 f」と「f が受け取れる型のリスト t」を引数にとり, t の要素に対して先頭から順に f を適用し, 初めて True を返した要素で t を分割します. f を満たさない間のリストを l, f を最初に満たした要素以降のリストを r とすると, (l, r) というペアで返します.
(\(l, r) -> l ++ (k, v):tail r) は無名関数で, (l, r) というペアとして引数を受け取り, r の最初の要素を取り除いたものの先頭に (k, v) を追加し, l の後ろに連結します.
t2 = [(4,"qux"),(1,"foo"),(3,"baz"),(2,"bar")] upd (3, "quux") t2
に対しては
((3 ==) . fst) (4, "qux") = False ((3 ==) . fst) (1, "foo") = False ((3 ==) . fst) (3, "baz") = True break ((3 ==) . fst) t2 = ( [(4,"qux"),(1,"foo",)], [(3,"baz"), (2,"bar")] ) (\(l, r) -> l ++ (k, v):tail r) ( [(4,"qux"),(1,"foo",)], [(3,"baz"), (2,"bar")] ) = [(4,"qux"),(1,"foo",)] ++ (3, "quux"):tail [(3,"baz"), (2,"bar")]) = [(4,"qux"),(1,"foo"),(3,"quux"),(2,"bar")]
といった感じに評価されます.
削除
k をキーとする要素を t から削除する関数 del は
del k t = (\(l, r) -> l ++ (tail r)) $ break ((k ==) . fst) t
と書けます. 更新のコードとだいたい同じです.
List モジュールの deleteBy を使って
del2 k t = deleteBy (\x y -> fst x == fst y) (k, []) t
と書いてもいいです. (k, []) と fst が一致するようなペアをリスト t から削除します.
*1: Haskell でいう「クラス」は, 一般的には「抽象型」もしくは「抽象クラス」と呼ばれるものの一種で, 実装すべき関数を規定するもの. Java でいう「インターフェイス」, ML でいう「シグネチャ」. C++ は多重継承できるから要らない? 型無し(弱い型付け)言語には関係ない?
Haskell でいう「型」が, オブジェクト指向でいうところの「クラス」に相当すると思ってよい.
紛らわしいですね.
Eq クラスを実装する型は (==) 関数で同値比較できなければならない.