4

javascriptで機能的および再帰的なデータ型を構築するにはどうすればよいですか?

私は何かMLのようなことができるようにしたいと思います:

datatype binary_node = Node of binary_node*binary_node 
                     | Lead of int

しばらく前に、私は関数型プログラミングのコースを受講しました。コースは、何らかのランダムな理由でSchemeで行われ、データ型の名前から始まり、次に「ペイロード」で始まるテーブルを作成してデータ型を構築しました。 Javascriptで関数型プログラミングスタイルのデータ型を行う方法は?

construct_node(n1,n2) -> 
    ("Node", n1, n2).

construct_leaf(int_value) ->
    ("Leaf", int_value).

次に、型チェッカー:

is_node(n) ->
    if (n[0] == "Node") ->
        is_binary_tree(n[1])  and is_binary_tree(n[2])
    else
        false
is_leaf(l) ->
    if(l[0] == "Leaf") ->
        is_integer(n[1])
    else 
        false
is_binary_tree(t) ->
    is_node(t) or is_leaf(t)

JavaScriptでこれを行う最も賢い方法は何ですか?

4

3 に答える 3

2

JavaScript は一般的にダック タイプの方法で使用されます。このように、特別なデータ型を定義する必要はありません。プロパティを持ちnode1、node2バイナリ ツリー ノードと見なされるオブジェクト。

var n = {
    node1: {
        node1: 456,
        node2: 789
    },
    node2: 1002
};

function isNode(x) {
    return x && isBinaryTree(x.node1) && isBinaryTree(x.node2);
}

function isLeaf(x) {
    return typeof x === 'number';
}

function isBinaryTree(x) {
    return isNode(x) || isLeaf(x);
}

上記の関数は、トラバーサル中のノードごとのケースの区別ではなく、ツリー全体の整合性を再帰的にチェックするためのものであることに注意してください。

于 2012-06-27T15:02:56.913 に答える
1

私はRoyという言語の作成者です。Roy は、静的型、代数データ型、およびパターン マッチングを備えた言語です。また、JavaScript にコンパイルされます。

あなたの例は次のようになります。

data Tree = Node Tree Tree | Leaf Number

Number は組み込みの JavaScript タイプです。

これで、ADT でパターン マッチを行うことができます。

let isNode n = match n
  case (Node a b) = true
  case (Leaf l) = false

let isLeaf l = match l
  case (Leaf l) = true
  case (Node a b) = false

JavaScript の出力は次のとおりです。

var Node = function(Tree_0, Tree_1) {
    if(!(this instanceof Node)) {
        return new Node(Tree_0, Tree_1);
    }
    this._0 = Tree_0;
    this._1 = Tree_1;
};
var Leaf = function(Number_0) {
    if(!(this instanceof Leaf)) {
        return new Leaf(Number_0);
    }
    this._0 = Number_0;
};
var isNode = function(n) {
    return (function() {
        if(n instanceof Node) {
            var a = n._0;
            var b = n._1;
            return true;
        } else if(n instanceof Leaf) {
            var l = n._0;
            return false;
        }
    })();
};
var isLeaf = function(l) {
    return (function() {
        if(l instanceof Leaf) {
            var l = l._0;
            return true;
        } else if(l instanceof Node) {
            var a = l._0;
            var b = l._1;
            return false;
        }
    })();
};
于 2012-06-28T07:59:00.083 に答える
1

私が見た方法の 1 つは、代数データ型の各ケースに対してコンストラクター関数を作成し、instanceof テストを使用して分岐を実装することです。たとえば、これはRoy 言語がパターン マッチングとタグ付き共用体を実装する方法です。

var Node = function(a, b){
    //protect against people forgetting to use "new" to call the constructor:
    if(!(this instanceof Node)){ return new Node(a, b) }

    //optionaly do extra type checking, if that is your thing:
    if(!(a instanceof Leaf)){ /*...*/ }
    if(!(b instanceof Leaf)){ /*...*/ }

    //save properties
    this.node1 = a;
    this.node2 = b;
};

var Leaf = function(value){
    /*...*/
    this.value = value;
};

このように、タグは内部の「__proto__」プロパティであり、ペイロードはオブジェクトの通常のインスタンス プロパティです。

私がこのアプローチを気に入っている理由は、それが非常に「型安全」だからです。内部プロトタイプ プロパティは編集できず、(シンボルや文字列の代わりに) コンストラクターまたはオブジェクトを使用すると、異なる型またはオブジェクトのプロパティとの名前の衝突が起こりにくくなります。

もう 1 つの良い点は、ダック タイピングに依存するのとは異なり、このアプローチは列挙型や、さまざまなケースが同じプロパティ セットを持つその他の状況でもシームレスに機能することです。

Javascript の悪い点は、LISP の場合と同様に、構造化のサポートが組み込まれていないため、次のようなカスタム マッチング関数を作成することをお勧めします。

var match_tree = function(x, cases){
    //just a helper function to make things pretty
    if(x instanceof Node){
        return cases.node.call(this, x.node1, x.node2);
    }else if(x instanceof Leaf){
        return cases.leaf.call(this, x.value);
    }else{
        throw new TypeError("pattern match failed");
    }
};

var sum_leaves = function(tree){
    return match_tree(tree, {
        node: function(val){ return val },
        leaf: function(left, right){
           return sum_leaves(left) + sum_leaves(right);
        }
    });
 };
于 2012-06-27T17:35:39.000 に答える