おたっく's blog

プログラミングなど技術的なことを中心に書きます。

JavaScriptでSICPを勉強する その4

JavaScriptSICPを勉強する その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)))))

JavaScript

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))))

JavaScript

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はデータを表現するのに非常に強力であることがわかりました。次回はリストの写像のおはなしで「JavaScriptSICPを勉強する その5」です。