Zipper - 関数的 (非破壊的) なデータ構造の更新
PLT Scheme の新しいバージョンからリストが immutable になる (set-car! とか append! とかが使えなくなる) ことは随分前にアナウンスされていて知ってはいたんですが、何の対策もしないままリリースを迎えてしまいました (バージョン 4 のアナウンスメント)。
個人的には、連想リストをよく使うので key, value ペアの value を変更するのに set-cdr! は必須だったんです。
とは言え、開発陣の長年の経験から「コンスに対するミューテーションは悪」というテーゼが導かれたわけで、ユーザーとしては大人しく従わなければなりません。
もちろんいくつか対処方法があっての事です。例えば box というコンテナを value の位置に置き、その中にデータを置いて再設定 (set-box!) する、という方法が有力な代替案です。
ただ、box は何となく面倒そうなので別な方法を検討してみたところ、ML とか Haskell の世界でよく研究されている zipper というデータ構造が目に止まりました。
Zipper とは、ツリー等の複雑なデータ構造にカーソル (現在フォーカスしている場所) を取り付けて、構造内を行き来できるようにするものです。その様子がジッパーの開け閉めに似ている、というのが名前の由来だそうです *1。
模式的に言うと、次のフラットなリストに対し、
(a b c)
zipper はこのような、元のデータ構造に常に一つだけ穴のあいた状態として表象することができます:
(a b []) (a [] c) ([] b c)
(穴として表していますが、情報が失われているわけではありません)
なおこの時、後者は元の3要素の集合を微分したもの (3つの2要素の集合) と考えることができます。つまり、zipper は元のデータ構造の導関数である、と言うことができるわけです (!!)。
そして、zipper を使うと、構造の任意の場所にアクセスして、副作用無しにデータを変更することができるらしいんです。
実装の仕方には色々バリエーションがあるんですが、今回は Oleg 氏によるジェネリックな zipper の実装を借りることにしました。
対象となるデータ構造の型に依存せず、構造の要素を列挙する関数さえ用意すれば良い、というとても簡単なものです。
ただ、部分継続というちょっと難しいものを使っているので、先に部分継続の使い方をさらっと説明してみましょう。
reset/shift という構文のペアを用います。reset で部分継続の始点 (プロンプト) を設定し、shift でその間を切り取ります。(shift k ...) とすると、k にその部分継続が関数として入ります。
まず、k を使わない例:
(reset (for-each (lambda (x) (shift k x)) '(1 2 3))) ; => 1
1 が返っている点に注意してください。shift を評価した時点でプロンプトの位置まで脱出が起こり、x が返されるのです。
for-each の中から外へ値を取り出すことができる、ということです。
このことを利用して、仮に for-each 関数のみが与えられた場合に、そこから map や fold 関数などを作ることができます:
(reset (for-each (lambda (x) (shift k (cons x (k #f)))) '(1 2 3)) '()) ; => (1 2 3)
(さっきと違って for-each の後に空リストを置いていることに注目してください)
部分継続を使わない例と比較してみましょう:
(let ((acc '())) (for-each (lambda (x) (set! acc (cons x acc))) '(1 2 3)) (reverse acc)) ; => (1 2 3)
set! と reverse を使っているのが何とも残念な感じですよね。
フィルタリングはこうです:
(reset (for-each (lambda (x) (when (odd? x) (shift k (cons x (k #f))))) '(1 2 3)) '()) ; => (1 3)
そして、切り取った k を、すぐに適用せずに外に取り出すことで、列挙を遅延することも可能になるわけです。
このことを踏まえて、zipper の実装をご覧ください:
;; Taken from: http://okmij.org/ftp/Scheme/zipper-in-scheme.txt (define-struct zipper (node k) #:transparent) (define (zipper-next zipper (node #f)) ((zipper-k zipper) node)) (define ((enum->zipper enum) zippee) (reset (enum (lambda (node) (shift k (make-zipper node k))) zippee)))
(PLT Scheme の define 構文の拡張仕様を使っています)
zipper-next は zipper (カーソル) を先に進める関数です。第2引数を与えると、先に進める前に現在のカーソル位置のデータを変更します。
enum->zipper は列挙関数から zipper を作るための関数です。どんなデータ構造であっても enum さえ定義してプラグイン的にこの関数に与えれば zipper を作ることができます。
ただし、enum は for-each のようなものではなく、map のように値を返す関数である必要があります。
続き:
(define (traverse-zipper f zipper) (if (zipper? zipper) (traverse-zipper f (zipper-next zipper (f zipper))) zipper)) (define (zip-up zipper) (traverse-zipper (lambda (_) #f) zipper)) (define (nth-zipper n zipper) (do ((i 0 (add1 i)) (zipper zipper (zipper-next zipper))) ((and (= i n) (if (zipper? zipper) #t (error 'nth-zipper "too few nodes"))) zipper) #f))
ついでに、
(define (fold-zipper kons knil zipper) (reset (traverse-zipper (lambda (zipper) (shift k (kons zipper (k #f)))) zipper) knil)) (define (find-zipper p? zipper) (let/ec return (fold-zipper (lambda (zipper _) (and (p? (zipper-node zipper)) (return zipper))) #f zipper))) (define (filter-zipper p? zipper) (fold-zipper (lambda (zipper acc) (if (p? (zipper-node zipper)) (cons zipper acc) acc)) '() zipper))
以上に基づいて、フラット・リストの zipper を定義します:
(define (linearly handler lst) (cond ((null? lst) lst) ((handler (car lst)) => (lambda (x) (cons x (linearly handler (cdr lst))))) (else (let* ((t (cdr lst)) (t1 (linearly handler t))) (if (eq? t t1) lst (cons (car lst) t1)))))) (define list->zipper (enum->zipper linearly))
linearly は map 関数みたいなものです。が、(handler (car lst)) の結果が #f の場合は値を変更せず次の要素に進む、という挙動が map とは異なります。あと、handler を適用した結果が全て #f だった場合は cons が一切呼ばれないようになっています。つまり、
(let ((l '(1 2 3))) (eq? l (linearly (lambda (_) #f) l)))
の結果は #t となり、linearly は l と同一 (ポインタが同じ) のオブジェクトを返していることが分かります。
さて、zipper の利用例として、2つのリストの3番目の要素を入れ替える、というのをやってみましょう:
(let ((x3 (nth-zipper 2 (list->zipper '(1 2 3 4 5)))) (y3 (nth-zipper 2 (list->zipper '(a b c d e))))) (map zip-up (list (zipper-next x3 (zipper-node y3)) (zipper-next y3 (zipper-node x3))))) ; => ((1 2 c 4 5) ; (a b 3 d e))
zipper というものがデータ構造のどこか1つの場所を指すものである、ということがこの例から良く分かるんじゃないでしょうか？
次に、何に役立つかは分かりませんが、
(map zip-up (map (lambda (zipper) (zipper-next zipper 'changed)) (filter-zipper (lambda (x) (memq x '(a e))) (list->zipper '(a b c d e))))) ; => ((changed b c d e) (a b c d changed))
同じ構造の複数の編集バージョンを得たりすることもできます。
何にしても破壊的な操作は一切行われませんので、変更を元に戻したければ元データをそのまま使えば良いわけです。
そして、当初の目的であった、連想リストを変更する関数はこのように書けました:
(define (modify-alist f al) (traverse-zipper (match-lambda ((struct zipper ((cons k v) _)) (cond ((f k v) => (lambda (new-v) (cons k new-v))) (else #f)))) (list->zipper al)))
(PLT Scheme のパターンマッチ構文を使っています)
利用例:
(modify-alist (lambda (k v) (case k ((Passwd) "password") ((Email) "mail@address") (else #f))) form-data)
ウェブ・ページから連想リストとして抽出したログイン・フォームに、アカウントとパスワードを埋めているところです。
補足:
コンスが immutable になったことに関連して、じゃぁ循環リストとか構造共有ができなくなるかと言うと、そうではありません。
PLT Scheme には以前から shared という、構造共有のための構文があるんです:
http://docs.plt-scheme.org/reference/shared.html
例:
(define onetwo (shared ((a (cons 1 b)) (b (cons 2 a))) a))
1 と 2 が交互に繰り返される無限リストです。
> onetwo #0=(1 2 . #0#) > (take onetwo 4) (1 2 1 2)
これとは別に、旧来のミュータブルなコンスは mcons というコンストラクタで作ることができます:
http://docs.plt-scheme.org/reference/mpairs.html
set-mcdr! や mappend! 等でミューテーションができるんですが、一方で car, map, take など、コンスを対象とする関数の引数になることはできません。したがって、mcons で作られたオブジェクトは mcons を専門に扱う関数群の中で隔離されて生きる必要があります (例: キューを実装するモジュール等)。
