JavaScriptでSICPを勉強する その4
「JavaScriptでSICPを勉強する その4」です。
2.1.3 データとは何か (p.51)
schemeではcar, cdr, consという3つの演算子が非常に重要な役割を果たしています。consを使って2つのオブジェクトを糊づけでき、そのオブジェクトはcar, cdrを使って取り出すことができます。schemeでのcar, cdr, consの実装を見てみましょう。
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q)))
どうやらconsは関数を返す関数で、car, cdrで関数適用で値を取り出しているようです。JavaScriptでも実装しましょう。
function cons(x, y) { return function (m) { return m(x, y); } } function car(z) { return z( function(p, q){return p;} ); } function cdr(z) { return z( function(p, q){return q;} ); }
JavaScriptでもちゃんと動いているか確認してみます。
var x = cons(1, cons(2, 3)); // => function (m) { return m(x, y);} car(x); // => 1 cdr(x); // => function (m) { return m(x, y);} car(cdr(x)); // => 2
ちゃんと動いているように見えます。SchemeだけでなくJavaScriptでcar, cdr, consを実装することで少しは理解が深まったかもしれません。
2.2.1 並びの表現 (p.55)
car, cdr consができたので次はデータの並びlistを表現してみましょう。schemeでのlistは次のようになっています。
(list <a_1> <a_2> ... <a_n>) ;は (cons <a_1> (cons <a_2> (cons ... (cons <a_n> nil))) ;と等価です
どうやらlistはconsが入れ子になっているだけのようです。JavaSciptで配列を受け取りそれをconsを入れ子にして返す関数listとlistを配列に戻す関数toArrayをつくってみます。
function list(a, k){ if( k === undefined ) k = a.length; if( k == 0 ) return null; return cons(a[k], list(a, k-1)); } function toArray(a, res){ if( res === undefined ) res = []; if( typeof(a) == "function" ) res.push( car(a) ); if( cdr(a) == null ) return res; else return toArray(cdr(a), res); }
再帰で実現できました。listでは最初の関数呼び出しのときに配列の長さをkに代入し再帰呼び出しをする度にkの値がひとつずつ小さくなっていきます。schemeではリストの末尾にnilという値で終わりを表していますが、JavaScriptではnullで終わりを表すことにしましょう。
リスト演算 (p.57)
JavaSciriptでschemeと同じ表現でlistが実現できたので次はリストに対する演算を実装してみましょう。まずはlistの長さを返すlengthを実装します。
scheme
(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)))))
function length(items) { if( null == items ) return 0; else return 1 + length(cdr(items)); } var x = list([1, 2, 3, 4]); var y = list([]); // 空のリスト length(x); // => 4 length(y); // => 0
次はリストを連結するappendを実装してみましょう。
scheme
(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2))))
function append(list1, list2) { if( null == list1 ) return list2; else return cons(car(list1), append(cdr(list1), list2)); } var x = list([1, 2, 3, 4]); var y = list([5, [6, 7]]); var z = append(x, y); // => 4 toArray(z); // => [1, 2, 3, 4, 5, [6, 7]]
car, cdr, consはデータを表現するのに非常に強力であることがわかりました。次回はリストの写像のおはなしで「JavaScriptでSICPを勉強する その5」です。