ALGOBIT

Haskell です.

前回の簡易KVSに, ファイルからのロード, セーブを追加. 操作を破壊的にしたもの.

kvs.hs : ソース

import System.IO
import Data.List
import Data.IORef

-- print an IORef object
p r = readIORef r

-- display contents of a file
cat fn = do
	h <- openFile fn ReadMode
	hGetContents h >>= putStr
	hClose h

-- to bind variable, use like 'r <- load filename'
-- r will be the type of IORef [(Int,String)]
load myRead fn = do
	h <- openFile fn ReadMode
	c <- hGetContents h
	newIORef $ myRead c

save fn r = do
	h <- openFile fn WriteMode
	c <- readIORef r
	hPrint h c
	hClose h

new = newIORef []

ins e r = modifyIORef r (e:)
lup k r = do
	t <- readIORef r
	return (lookup k t)
upd (k,v) r = modifyIORef r
	((\(l, r) -> l ++ (k, v):tail r) . break ((k ==) . fst))
del k r = modifyIORef r ((\(l, r) -> l ++ (tail r)) . break ((k ==) . fst))

「IORef a 型の値」(a は任意の型) を第一引数, 「a 型の値を引数にとって a 型の値を返す関数」を第二引数に modifyIORef を呼び出すと, IORef で参照される値が変更されます.
ので, 前回との違いは,

del k t = (\(l, r) -> l ++ (tail r)) $ break ((k ==) . fst)

のように引数 t を変更した新しいテーブルを返すように書いていた関数を以下のように書き換えます.
すなわち, 左辺で, t を newIORef を使って, IORef 型にした変数 r を使います.
右辺では第一引数を r として, 第二引数を元の関数の右辺として, modifyIORef を呼び出します.

del k r = modifyIORef r ((\(l, r) -> l ++ (tail r)) . break ((k ==) . fst))

test.kvs : テスト用ファイル

[(1, "foo"),
 (2, "bar"),
 (3, "baz")]

使ってみます.

% 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 kvs.hs              -- 上記ソースをロードします.
[1 of 1] Compiling Main             ( kvs.hs, interpreted )
Ok, modules loaded: Main.
*Main> cat "test.kvs"           -- ファイルの中身を確認
[(1, "foo"),
 (2, "bar"),
 (3, "baz")]
*Main> r <- load (read::String -> [(Int,String)]) "test.kvs"
                                -- test.kvs の中身を [(Int,String)] として解釈し, r に束縛
*Main> p r
[(1,"foo"),(2,"bar"),(3,"baz")]
*Main> ins (4,"qux") r          -- (4, "qux") を挿入
*Main> p r
[(4,"qux"),(1,"foo"),(2,"bar"),(3,"baz")]
*Main> lup 2 r                  -- キーが 2 であるエントリを検索
Just "bar"
*Main> lup 5                    -- キーが 5 であるエントリを検索
                                -- Nothing が返されたときの対処をしていないので
<interactive>:1:0:              -- 実行時例外
    No instance for (Show (IORef [(t, b)] -> IO (Maybe b)))
      arising from a use of `print' at <interactive>:1:0-4
    Possible fix:
      add an instance declaration for
      (Show (IORef [(t, b)] -> IO (Maybe b)))
    In a stmt of a 'do' expression: print it
*Main> upd (2,"quux") r         -- キーが 2 であるエントリの値を "quux" に変更
*Main> p r
[(4,"qux"),(1,"foo"),(2,"quux"),(3,"baz")]
*Main> del 1 r                  -- キーが 1 であるエントリを削除
*Main> p r
[(4,"qux"),(2,"quux"),(3,"baz")]
*Main> save "test2.kvs" r       -- "test2.kvs" に保存
*Main> cat "test2.kvs"          -- "test2.kvs" の中身を確認
[(4,"qux"),(2,"quux"),(3,"baz")]

追記: 2010.11.26
これ KVS って言わないよな… タイトルから来た方すいません.

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 クラスを実装する型は (==) 関数で同値比較できなければならない.

なんとなく覚え書き的に.
とりあえず順列.

import Data.List (delete)
perms [] = [[]]
perms xs = [ h:t | h <- xs, t <- perms (delete h xs) ]

perms は, 引数に与えられたリストが空ならば空のリストをだだ一つ持つリストを返す.
引数に与えられたリストが空でないなら, そのリストを xs とする.
xs から順番に要素を取り出し, これを h とする.
xs から h を (あれば) 削除したリストに対して perms を呼び出した結果の各要素を順番に取り出し t とする.
t の先頭に h を付加したもののリストが結果である.

要素三つの場合で評価がどんな風に行われるか手で書いて確認してみます.

perms [2, 3, 5] = [ h:t | h <- [2,3,5], t <- perms (delete h xs) ]
 = [[2:t | t <- perms (delete 2 [2,3,5]) ],
    [3:t | t <- perms (delete 3 [2,3,5]) ],
    [5:t | t <- perms (delete 5 [2,3,5]) ]]
 = [[2:t | t <- perms [3,5]],
    [3:t | t <- perms [2,5]],
    [5:t | t <- perms [2,3]]]

ところで,

perms [3,5] = [ h:t | h <- [3,5], t <- perms (delete h xs) ]
 = [[3:t | t <- perms (delete 3 [3,5])], [5:t | t <- perms (delete 5 [3,5])]]
 = [[3:t | t <- perms 5], [5:t | t <- perms [3]]]

ところで

perms [3] = [3:t | t <- perms (delete 3 [3])]
 = [3:t | t <- perms []]
 = [3:[]]
 = [[3]]

perms [] は [[]] すなわち空のリストをただ一つ含むリストですから, その全ての要素を順に t に代入するということは, t が空のリストの場合だけです. 空リスト [] の先頭に 3 を追加した結果は 3 だけを要素とするリストです.
同様に perms [5] = [[5]] です.
perms [3,5] の評価の続き,

 = [[3:t | t <- perms 5], [5:t | t <- perms [3]]]
 = [3:[5], 5:[3]]
 = [[3,5], [5,3]]

同様に

perms [2,5] = [[2,5], [5,2]]
perms [2,3] = [[2,3], [3,2]]

です.
perms [2,3,5] の評価に戻ると

 = [[2:t | t <- perms [3,5]],
   [3:t | t <- perms [2,5]],
   [5:t | t <- perms [2,3]]]
= [2:[3,5], 2:[5,3], 3:[2,5], 3:[5,2], 5:[2,3], 5:[3,2]]
= [[2,3,5], [2,5,3], [3,2,5], [3,5,2], [5,2,3], [5,3,2]]

ghci で :l して動作確認.

*Main> perms "abcd"
["abcd","abdc","acbd","acdb","adbc","adcb","bacd","badc","bcad","bcda","bdac","bdc
a","cabd","cadb","cbad","cbda","cdab","cdba","dabc","dacb","dbac","dbca","dcab","d
cba"]
*Main> perms [2, 3, 5, 7]
[[2,3,5,7],[2,3,7,5],[2,5,3,7],[2,5,7,3],[2,7,3,5],[2,7,5,3],[3,2,5,7],[3,2,7,5],[
3,5,2,7],[3,5,7,2],[3,7,2,5],[3,7,5,2],[5,2,3,7],[5,2,7,3],[5,3,2,7],[5,3,7,2],[5,
7,2,3],[5,7,3,2],[7,2,3,5],[7,2,5,3],[7,3,2,5],[7,3,5,2],[7,5,2,3],[7,5,3,2]]

いいですね.

数値に対して数値のリストで返したいので

*Main> map (read::String->Int) $ perms $ show 23579
[23579,23597,23759,23795,23957,23975,25379,25397,25739,25793,25937,25973,27359,273
95,27539,27593,27935,27953,29357,29375,29537,29573,29735,29753,32579,32597,32759,3
2795,32957,32975,35279,35297,35729,35792,35927,35972,37259,37295,37529,37592,37925
,37952,39257,39275,39527,39572,39725,39752,52379,52397,52739,52793,52937,52973,532
79,53297,53729,53792,53927,53972,57239,57293,57329,57392,57923,57932,59237,59273,5
9327,59372,59723,59732,72359,72395,72539,72593,72935,72953,73259,73295,73529,73592
,73925,73952,75239,75293,75329,75392,75923,75932,79235,79253,79325,79352,79523,795
32,92357,92375,92537,92573,92735,92753,93257,93275,93527,93572,93725,93752,95237,9
5273,95327,95372,95723,95732,97235,97253,97325,97352,97523,97532]

show で文字列 (文字のリスト) に変換, perms で文字を並べ替えた文字列のリストにして, (read::String->Int) で文字列から Int に変換する操作を map で全ての要素に適用.

追記:
「Haskell 順列」で検索するといろいろ出てくる.

import Data.List
perms [] = [[]]
perms xs = concat [ map (x:) $ perms (delete x xs) | x <- xs]

の方が変数一個少ない.

追記2:
Data.List に permutations が既定義だった…

Prelude> :module Data.List
Prelude Data.List> permutations [2,3,5]
[[2,3,5],[3,2,5],[5,3,2],[3,5,2],[5,2,3],[2,5,3]]

辞書順にならないらしい.