ALGOBIT > 離散的な気まぐれ

2011/04/18

Node.js なら TCP エコーサーバが５行！

Filed under: 離散的な気まぐれ — タグ: , , , — Kohyama @ 13:41

サーバサイドスクリプトをいろいろ試しているところです.

Gauche でエコーサーバ
に続き, Node.js 版 TCPエコーサーバものせておきます.
Node.js は JavaScript の処理系です.

?
1
2
3
4
5
var net = require('net');
var server = net.createServer(function (stream) {
    stream.on('data', function (data) { stream.write(data); });
    stream.on('end', function () { stream.end(); }); });
server.listen(1111, 'localhost');

５行！
なんということでしょう.

エコーサーバとしてだけならば,本家にもっと短い例が載ってますが, データを処理するサーバの雛形なので, 送られてきたデータがコード内で変数として見えている最小のコードとしました.

node.js はインストールされているとします.
上記のソースをファイルに保存したら, 第一引数に保存したファイルのパスを指定して, node (Windows なら node.exe) を実行します.

UNIX 系ならば, #!/usr/bin/env node という行を先頭に追加し, chmod +x してあげれば直接実行できます.

2011/04/15

Interactive CUI in web pages

Filed under: 離散的な気まぐれ — タグ: — Kohyama @ 20:30

いくつかの用途（オレオレスクリプトの実行環境をWEBページ上に配置するとか）で, WEBページ上にシェルっぽい環境が欲しかったので, 対話部分だけ分離して実装しました.

readline, rlwrap, jLine の JavaScript 版みたいなもんです.

プロンプト prompt> に対して入力を編集して Return キーを押すと,
入力文字列を [ と ] で挟んで出力します.

編集中の行内のカーソルの移動に ←, →, Home, End, Ctrl-f, Ctrl-b, Ctrl-a および Ctrl-e が使えます.
入力履歴を ↑, ↓, Ctrl-p および Ctrl-n で移動できます.
Backspace もしくは Ctrl-h でカーソルの前の文字を削除し, カーソルを一文字前に戻します.
Delete もしくは Ctrl-d でカーソル位置の文字を削除します.
Ctrl-k でカーソル位置より後ろを削除します.

同じことをするのにあなたが書くべき JavaScript は 7行.
格納するための HTML ファイル全体で 11行です. 

<html><head><title>jsReadLine Demo</title>
<script type="text/javascript" src="ReadLine.js"></script>
<script type="text/javascript">
window.onload = function() {
    var rl = new Algobit.ReadLine(80, 24);
    var b = document.getElementsByTagName('body')[0];
    b.appendChild(rl.textarea);
    rl.print("prompt> ");
    rl.gets = function(s) { rl.print("[" + s + "]\nprompt> "); };
}
</script></head><body></body></html>

ソースとか詳しい説明はこちら: github.com/kohyama/jsReadLine

次回！ jsReadLine を使ったオレオレスクリプトの REPL!

2011/04/07

scheme で TCP エコーサーバ

Filed under: 離散的な気まぐれ — タグ: , , , , — Kohyama @ 13:01

scheme で TCP のサーバを書く際の雛形としてエコーサーバとしてコードをまとめてみた.
ほとんど処理系依存, UNIX系OS + Gauche じゃないと動きません.
daemon のところは Gauche クックブック / デーモンプロセスを作成する をほぼそのまま使わせていただきました.
Gauche ユーザリファレンス の C と Scheme の関数の対応 あたりを激しく参照しました.
chmod +x して実行すると, 制御端末を切り離し, 1111 番ポートの TCP 接続を待ちます.
telnet localhost 1111 などで接続すると, 改行の入力を待って, 改行までに入力されたテキストに改行を付けてそのまま返します.
止めるときは ps などで親の（一番若い） pid を調べて kill します.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/env gosh
(use gauche.net)
(set-signal-handler! SIGCHLD (lambda _
                               (guard (e ((<system-error> e)))
                                      (while (< 0 (sys-waitpid -1))))))
(set-signal-handler! SIGTERM (lambda _ (sys-kill 0 SIGTERM)))
 
(define (daemon)
  (when (positive? (sys-fork))
        (sys-exit 0))
  (sys-setsid)
  (sys-chdir "/")
  (sys-umask 0)
  (call-with-input-file "/dev/null"
                        (cut port-fd-dup! (standard-input-port) <> ))
  (call-with-output-file "/dev/null"
                         (lambda (out)
                           (port-fd-dup! (standard-output-port) out)
                           (port-fd-dup! (standard-error-port) out))))
 
(define (prog cs)
  (let ((iport (socket-input-port cs))
        (oport (socket-output-port cs)))
    (let loop ((line (read-line iport)))
      (cond
        ((eof-object? line) (socket-close cs))
        (else
          (display (string-append line "\r\n") oport)
          (loop (read-line iport)))))))
 
(define (main args)
  (daemon)
  (let1 s (make-server-socket 'inet 1111 :reuse-addr? #t)
        (let loop ((cs (socket-accept s)))
          (let ((pid (sys-fork)))
            (cond
              ((= pid 0)   ; child
               (set-signal-handler! SIGTERM #t) ; reset
               (prog cs)
               (sys-exit 0))
              (else        ; parent
                (socket-close cs)
                (loop (socket-accept s))))))))

以下はほぼ等価な C のプログラムです.
というか, 過去に C で書いた TCP サーバから最低限のコードをエコーサーバとして下のように整理し, これを Gauche に置き換えたのが上のプログラムです.
UNIX 系の OS でないと動きません.
syslog は省いてます.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <sys/types.h>    /* read */
#include <sys/socket.h>   /* accept, bind, getsockname, listen, socket */
#include <sys/uio.h>  /* read */
#include <sys/wait.h> /* waitpid */
#include <arpa/inet.h>    /* htons */
#include <errno.h>        /* errno */
#include <fcntl.h>        /* open */
#include <signal.h>       /* kill, sigaction */
#include <stdio.h>        /* BUFSIZ */
#include <stdlib.h>       /* daemon, exit */
#include <unistd.h>       /* _exit, close, dup, fork, read, write */
 
static void
reapchild(int signo)
{
    while (waitpid(-1, NULL, WNOHANG) > 0)
        ;
}
 
static void
parent_exit(int signo)
{
    kill(0, SIGTERM);
    exit(0);
}
 
static int
prog(int s)
{
    int n;
    char buf[BUFSIZ];
 
    while (0 < (n = read(s, buf, BUFSIZ)))
        write(s, buf, n);
}
 
int
main(int argc, char *argv[])
{
    int addrlen, cs, pid, s;
    struct sockaddr_in addr;
    int port = 1111;
    struct sigaction sa;
 
    daemon(1, 1);
    chdir("/");
    close(0);
    close(1);
    close(2);
    open("/dev/null", O_RDWR);
    dup(0);
    dup(0);
 
    sa.sa_handler = reapchild;
    sigaction(SIGCHLD, &sa, NULL);
    sa.sa_handler = parent_exit;
    sigaction(SIGTERM, &sa, NULL);
 
    if ((s = socket(AF_INET, SOCK_STREAM, 0)) < 0)
        exit(1);
 
    addr.sin_family = AF_INET;
    addr.sin_addr.s_addr = INADDR_ANY;
    addr.sin_port = htons((unsigned short)port);
    addrlen = sizeof(addr);
    if (bind(s, (struct sockaddr *)&addr, addrlen) < 0)
        exit(1);
 
    if (getsockname(s, (struct sockaddr *)&addr, &addrlen))
        exit(1);
 
    listen(s, 5);
    for (; ; ) {
        if ((cs = accept(s, (struct sockaddr *)&addr, &addrlen)) < 0) {
            if (errno == EINTR)
                continue;
            exit(1);
        }
        switch (fork()) {
        case -1:
            exit(1);
        case 0:
            sa.sa_handler = SIG_DFL;
            sigaction(SIGTERM, &sa, NULL);
            close(s);
            prog(cs);
            _exit(0);
        }
        close(cs);
    }
}
プログラミングGauche
Kahuaプロジェクト
オライリージャパン
発売日：2008-03-14
ブクログでレビューを見る»

UNIX Cプログラミング (NUTSSHELL HANDBOOKS)
デビッド・A. クリ
アスキー
発売日：1991-07
ブクログでレビューを見る»

実際に役に立つプログラムは直接なり間接なり OS と対話しなければならない.
とくに UNIX オペレーティングシステムを記述するために生まれた C 言語は, より上位のプログラミング環境の下位で OS と直接対話する基盤である.
システムコールプログラミングへようこそ.

2010/12/10

ぷログラミング

Filed under: 離散的な気まぐれ — タグ: , , — Kohyama @ 14:38

昨日 pgcafe の忘年会に参加して参りました.

pgcafe がコラボレーションのきっかけになっていますという常連皆さんのまとめ発表に混じり, ひとり自分勝手に最近興味のある関数プログラミングについて語ってきました. すいません.

私が最近になってはまっているというだけで, 関数プログラミング自体は新しい話題という訳ではないので, 既に知っている方か, 特に興味のない方が大半だと思うのですが, もしかしたら私の発表で興味を持ってくださった方もいないとも限りませんので一応資料載せておきます.

あわてて作った資料のため「ぷログラミング」と誤植していたのですが, 意外にかわいいのでそのまま修正せずにおきます.

関数ぷログラミング紹介

準備・持ち寄りしてくださった皆さんありがとうございました.
夜から参加で手伝えずいただくばかりでごちそうさまでした.

そして今年一年ありがとうございました.
来年は昼間は行けそうにありませんが, オンラインで, 二次会やイベントで, 参加できればと思っています.

追記: Haskell では構文をプログラムから書き換えるようなことはできるかというご質問ありました. Haskell ではできません. LISP ではできます. → LISPならば容易にできます. Haskell でも LISP ほど容易ではないけれどもできます.([2010.12.11] eagletmt さん情報により修正)
プログラムソースの構文が, プログラムが扱うデータと同じ構文になっていることを「同図像性」というのですが, LISP (といっても特定しきれませんが) はこの特徴を持っており, 構文を再定義することができます.
同図像性は関数プログラミングの特色というわけではないと思います.
逆に, 関数プログラミングの特色でないもので Haskell が持っている機能をリストしてしまってあるかもしれません. あしからず.

2010/12/02

第二双対定理（foldr と foldl の関係）

Filed under: 離散的な気まぐれ — タグ: , — Kohyama @ 06:00

第二双対定理

演算子 ⊕, ⊗ および a は全ての x, y, z について, つぎの関係を満たすものとする.

x ⊕ (y ⊗ z) = (x ⊕ y) ⊗ z
x ⊕ a = a ⊗ x

つまり, ⊕ と ⊗ はたがいに結合的であり, ⊕ の右側に a があることと ⊗ の左側に a があることが等しいということである.
これらの条件のもとで, 任意の有限リスト xs に対して,

foldr (⊕) a xs = foldl (⊗) a xs

が成り立つ.

出典: 「関数プログラミング」p.72

だそうだ.

xs の要素を x1, x2, x3, … xn
とすると

foldr (⊕) a xs ⇒ x1 ⊕ (x2 ⊕ (x3 ⊕ … (xn ⊕ a) … ))
foldl (⊗) a xs ⇒…(((a ⊗ x1) ⊗ x2) ⊗ x3) … ⊗ xn

であり, 上の条件化ではこの二つは等しいからだ.

GHCi で, Haskell における reverse の再実装をしてみよう.

?
Prelude> :{
Prelude| let revr = foldr postfix []
Prelude| where postfix a xs = xs ++ [a]
Prelude| :}
Prelude> revr [1, 2, 3, 4]
[4,3,2,1]
Prelude> :{
Prelude| let revl = foldl prefix []
Prelude| where prefix xs a = [a] ++ xs
Prelude| :}
Prelude> revl [1, 2, 3, 4]
[4,3,2,1]

a `postfix` xs はリスト xs の後に, a だけからなるリストを連結したリスト.
xs `prefix` a は a だけからなるリストの前に, リスト xs を連結したリスト.

x `postfix` (y `prefix` z) と (x `postfix` y) `prefix` z は等しい.
x `postfix` [] と [] `prefix` x は等しい.

ので, revr と revl は（数学的には）等しい.

ふむ… わかったようなわからんような.

関数プログラミング
R. バード,P. ワドラー
近代科学社
発売日：1991-04
ブクログでレビューを見る»

学部時代, 本著の翻訳者である武市先生の授業の教科書でした.
当時（1997年だったかな）C言語で計測値に対する解析計算をするプログラムを書くのに精一杯だった私にとっては, 実用性の無い数学論に見えましたが, Haskell や他の関数型言語を齧った現在読むと, とても系統的に関数型言語についてまとめられていることが分かります.
翻訳も, 翻訳であることを意識させない滑らかさです. 元の英語を括弧書きする頻度も抜群です.

動く様を見ないでも, 理論からその世界を想像できる方は, いきなりこれを読んでもよいでしょう.
実際に動かしてみないと分からない私のような人は, なんらかの関数型言語のチュートリアルを終えた後に読むと理解が系統立ってくるので良いと思います.

カリー化

Filed under: 離散的な気まぐれ — タグ: , , — Kohyama @ 02:21

「カリー化」は元々は, 複数引数を取る関数を, 「1つだけ引数を取り関数を返す関数」の連鎖で統一的に表現する記述方法の事を言う.
三つの引数を取りその和を返す関数 f を (ある型 a に対して)「(a, a, a) → a」という型を持つ関数「f (x, y, z) = x + y + z」と表現するか, 「a → (a → (a → a))」(あるいは ‘→’ は右結合であると約束して「a → a → a → a」) という型を持つ関数「f x y z = x + y + z」として表現するかの二つの表現方法について後者の事を「カリー化」された記述と呼ぶ.
実際の処理内容の違いを直接示す訳ではないし, なんらかの変換手続きの事でもない.

ところが, プログラミング言語を特定すると「書き方」が決められてくる. なんとなれば, プログラミング言語とは, ある処理をどう書くかを規定するものだからだ.

C言語で

?
int f(int x, int y, int z) { return x + y + z;}

という関数 f の定義があったとして「f(3) と書くと, 『二つ引数を取り, 3 とそれらの総和を取る関数』を意味する」というようなことはない. コンパイラが構文エラーを吐くか, コンパイラのエラーを無視して, スタックに 3 を積んで, 関数 f のアドレスへジャンプしても, スタックの不整合が起こるのみである.

Haskell や ML では, 内部構文がカリー化されている. Haskell で

?
f x y z = x + y + z

のように, 「三つの引数を取り, それらの総和を返す関数」f を定義をした場合, f 3 は「二つの引数を取り, 3 とそれらの総和を返す関数」であるし, f 3 4 は「一つの引数を取り, 3, 4 およびその引数の総和を返す関数」であり, f 3 4 5 は「3, 4, 5 の和を返す関数」である.
より正確に言うと, f は【引数を一つ取り x をその値に束縛し『引数を一つ取り y をその値に束縛し「引数を一つとり, x と y とその数の和を返す関数」を返す関数』を返す関数】であり,
Haskell での型宣言 f :: a -> a -> a-> a は, そのことを示している.
そもそも, 複数引数を取る関数が定義できているかのように記述できることの方が構文糖衣 (内部的には, もっと基本的な別の構文に変換されるような, コードを見やすくするために提供される書き方のバリエーション) なのである.

たとえば, 「二引数を取り値を返す関数」を要求する高階関数への引数として f 3 を渡すことができる. Haskell インタプリタ GHCi で確認してみよう.

?
Prelude> let f x y z = x + y + z   -- 3引数の和を返す関数 f を定義
Prelude> :t f                      -- f の型を確認
f :: (Num a) => a -> a -> a -> a   -- Num に属する任意の型 (仮に a とする) について
                                   --   a 型の引数を一つ取り,
                                   --     a 型の引数を一つ取り,
                                   --       a 型の引数を一つ取り a 型の値を返す関数
                                   --     を返す関数
                                   --   を返す関数
                                   -- 言い換えると,
                                   --   三つの引数を取り, 一つの値を返す関数.
                                   -- になっている.
 
Prelude> :t (f 3)                  -- f 3 の型を確認
(f 3) :: (Num t) => t -> t -> t    -- Num に属する任意の型 (仮に t とする) について
                                   --   t 型の引数を一つ取り,
                                   --     t 型の引数を一つ取り t 型の値を返す関数
                                   --   を返す関数
                                   -- 言い換えると,
                                   --   二つの引数を取り, 一つの値を返す関数.
                                   -- になっている.
 
Prelude> :t zipWith                -- zipWith の型を確認
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
                                   -- 任意三つの型 (仮に, a, b, c とする) について
                                   --   (a 型の引数を取り
                                   --      b 型の引数を取り c 型の値を返す関数
                                   --    を返す関数)
                                   --   を引数に取り
                                   --     a 型のリストを引数を取り
                                   --       b 型のリストを引数に取り c 型のリストを返す関数
                                   --     を返す関数
                                   --   を返す関数
                                   -- 言い換えると,
                                   --   (二つの引数を取り, 値を返す関数) と, 二つのリストを引数に取り,
                                   --   リストを返す関数.
                                   -- となっている.
 
Prelude> zipWith (f 3) [5, 7, 11, 13] [17, 19, 23, 29]
[25,29,37,45]                      -- 引数を二つ取る関数 (f 3) に
                                   -- 二つのリストの要素を順に与え,
                                   -- 返り値を順に要素とするリストを得た.

このように最初からいくつ目かまでの引数を適用し, 残りの引数を取るような関数をオブジェクトとして扱うことを「関数の部分適用」という.
カリー化表現を全面的に採用している言語では, 部分適用した関数を作るために特別な処理は必要ないが, そうでなくて且つ部分適用をサポートする言語では, 関数と最初の引数を与えると, 残りの引数を取る関数に変換することができる.
この関数の変換を行う関数が curry という名前であることが多いが, curry が行うのは関数部分適用であって, 「カリー化」ではない.

紛らわしいことには, Haskell にも curry という関数があり, これは, 一つのペアを引数に取る関数を二引数関数（実際には一引数を取る関数を返す一引数の関数）に変換する.

元の意味はともかく, 引数を部分適用した関数を作成する関数が curry という名前であることが多く, この curry 関数がしてくれる変換を「カリー化 (currying)」と呼ぶ人も多いので, 別にそれでもいいんではないかとは思う.

いずれにせよ, プログラマにとっては引数を部分適用した関数が作成できてオブジェクトとして扱えるかどうか, その処理はどう書くか, が関係するのみだ.
高階関数（関数を引数に取ったり, 関数を返したりする関数）があるような言語, とりわけ関数が第一級のオブジェクト（値も関数も同じように変数に束縛できる）であるような言語では, curry という名前の関数がこの変換を行ってくれる.

追記:
scala だと, _ を使った表記で, 引数を部分的に適用した関数を表現したり,

?
scala> def func1(x:Int, y:Int, z:Int):Int = x + y + z
func1: (Int,Int,Int)Int
scala> func1(3, _:Int, _:Int)
res1: (Int, Int) => Int = <function>

そもそもカリー化された状態で関数を記述し, 最初から任意個までの引数を適用した関数を表現したり (最後にアンダーバー ‘_’ が要るけど) できるようだ.

?
scala> def func2(x:Int)(y:Int)(z:Int):Int = x + y + z
func2: (Int)(Int)(Int)Int
scala> func2(3)_
res2: (Int) => (Int) => Int = <function>

また, Function.curried(func1 _) で func2 と同じ型の関数を, Function.uncurried(func2 _) で func1 と同じ型の関数を作れるらしい. この命名は適切に思える.

Haskell の例と同じことをやろうとしたが, zipWith が無いので, zip して map したが, それだと (Int, Int) のペア一つを取る関数を要求してしまう. func1 も func2 も直接渡せない. なんか良い例題ないかな…

?
scala> List(5, 7, 11, 13) zip List(17, 19, 23, 29) map func2(3)_
<console>:6: error: type mismatch;
 found   : (Int) => (Int) => Int
 required: ((Int, Int)) => ?
       List(5, 7, 11, 13) zip List(17, 19, 23, 29) map func2(3)_
                                                       ^

↓これでは部分適用の例題にならない…

?
scala> List(5, 7, 11, 13) zip List(17, 19, 23, 29) map {p => func2(3)(p._1)(p._2) }
res3: List[Int] = List(25, 29, 37, 45)

2010/11/21

簡易KVS mutable版

Filed under: 離散的な気まぐれ — タグ: — Kohyama @ 02:55

Haskell です.

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

kvs.hs : ソース

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
2
3
[(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 って言わないよな… タイトルから来た方すいません.

2010/11/20

GHCiで簡易KVS

Filed under: 離散的な気まぐれ — タグ: — Kohyama @ 03:48

Haskell です.

Eq k => [(k, v)] の形をしたリスト t について考えます.
k は Eq クラスを実装した型(*1)
v は任意の型です.
k についてソートされていることを要求しないとします.
k について重複は無いものとします.
t へのデータの挿入・検索・更新・削除は次のように書けます.

lut.hs

?
1
2
3
4
5
6
7
8
9
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 に挿入したリストを返す関数は, 元のリストの先頭に要素を追加するだけです.

?
3
ins (k,v) t = (k, v):t

今回は, わざわざ関数に名前を付けましたが, t が特定の構造を保つことを要請するようなデータ構造でなければ, 右辺をそのまま書いた方が速いですね.

検索
k が key であるペアを検索してあれば Just v をなければ Nothing を返す関数は

?
4
5
6
7
lup key [] = Nothing
lup key ((k, v):ts)
    | key == k = Just v
    | otherwise = lup key ts

と書けます. 今回はわざわざ書きましたが, 標準ライブラリ Prelude に含まれる lookup でまったく同じことができますので, 特に理由がなければ, 標準の lookup を使えばよいでしょう.

更新
k をキーとする要素の値を v で置き換えます.

?
8
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 は

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

と書けます. 更新のコードとだいたい同じです.
List モジュールの deleteBy を使って

?
10
del2 k t = deleteBy (\x y -> fst x == fst y) (k, []) t

と書いてもいいです. (k, []) と fst が一致するようなペアをリスト t から削除します.

*1: Haskell でいう「クラス」は, 一般的には「抽象型」もしくは「抽象クラス」と呼ばれるものの一種で, 実装すべき関数を規定するもの. Java でいう「インターフェイス」, ML でいう「シグネチャ」. C++ は多重継承できるから要らない? 型無し(弱い型付け)言語には関係ない?
Haskell でいう「型」が, オブジェクト指向でいうところの「クラス」に相当すると思ってよい.
紛らわしいですね.
Eq クラスを実装する型は (==) 関数で同値比較できなければならない.

2010/11/17

数値の桁並べ替え

Filed under: 離散的な気まぐれ — タグ: — Kohyama @ 05:56

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

?
1
2
3
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 順列」で検索するといろいろ出てくる.

?
1
2
3
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]]

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

2010/10/08

ハノイとバベルの塔 第八階 – 端末アニメ in Ruby

Filed under: 離散的な気まぐれ — タグ: , — Kohyama @ 02:53

第五回, 第六回 と同様の構造で書いてみます.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/ruby
 
def move(src, tmp, dst, n)
    if (n == 0)
        return
    end
    move(src, dst, tmp, n - 1)
    dst.push(src.pop())
    printAStep()
    move(tmp, src, dst, n - 1)
end
 
def printAStep()
    sleep($w/1000.0)
    print "\x1b[2J\x1b[2;1H"
    $N.times do |i|
        $pegs.each do |peg|
            if (peg.length < $N - i)
                print " " + $ws + "|" + $ws + " "
            else
                l = peg[$N - i - 1]
                print " " + $ws[l..-1] + $bar[0..(l - 1)] + "|" +
                    $bar[0..(l - 1)] + $ws[l..-1] + " "
            end
        end
        print "\n"
    end
    print $grnd + "\n"
end
 
$N = (0 < ARGV.length) ? ARGV[0].to_i : 3
$w = (1 < ARGV.length) ? ARGV[1].to_i : 500
$pegs = [[],[],[]]
$N.downto(1) do |i|
    $pegs[0].push(i)
end
 
$ws = " "*$N
$bar = "-"*$N
$grnd = "="*(6*$N + 9)
 
printAStep()
move($pegs[0], $pegs[1], $pegs[2], $N)

$N.times do |i| ... end のループに, 数値もオブジェクトであることや, ブロック（無名関数）を受け取る既定義メソッドなどに言語の特色が出ています.

手続き中で任意個の '-' からなる文字列を生成してもさほど遅くはならないと思うのですが, 言語毎の特色を見るために「$N個の '-' からなる文字列を作っておいて, 部分文字列を使う」ように書いています.

n個の '-' からなる文字列を "-"*n と書けるのは
* という演算子の機能を規定する言語の組み込み機能ではありません.
* も単なるメソッドであり, "-"*n の実態は "-".*(n) すなわち, 文字列 "-" のインスタンスメソッド * を引数 n で呼び出しているだけであり, クラスに適切なメソッドを定義することで実現されています.

部分文字列を取り出すときに, 配列の添字に負数が利用できるのも良いですね.

第五回, 第六回 で利用した「ランダムアクセスできるスタック」みたいな能力を「配列」が持っていることで記述量はずいぶん減っています.

初めてのRuby
Yugui
オライリージャパン
発売日：2008-06-26
ブクログでレビューを見る»

本書は対象読者の設定が明快です.
既にいくつかのプログラミング言語を実用していて, 他のプログラミング言語と Ruby が違うところだけ知りたい人向けです.
従ってページ数に対して情報量が多く感じました. お買い得.
多くの言語を操る著者さんの, 特定のプログラミング言語に偏った考え方や用語にならないようにという配慮が素敵です.
« Newer Posts — Older Posts »

Copyright © 2010 Yoshinori Kohyama All Rights Reserved.