4

如何在 javascript 中构造函数和递归数据类型？

我希望能够做一些 ML 之类的事情：

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

前段时间我参加了一门函数式编程课程——出于某种随机原因，该课程是在 Scheme 中，我们通过制作 tubles 来构造数据类型，从数据类型的名称开始，然后是“有效负载”，这是在 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

我见过的一种方法是为代数数据类型的每种情况创建一个构造函数，并使用 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__”属性的标记和有效负载是对象中通常的实例属性。

我喜欢这种方法的一个原因是它非常“类型安全”。内部原型属性是不可编辑的，并且使用构造函数或对象（而不是符号或字符串）使其较少受到名称冲突的影响，无论是与不同类型还是与对象的属性。

另一个好处是，与依赖于鸭子类型不同，这种方法还可以无缝地与枚举和其他不同情况具有相同属性集的情况一起使用。

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 回答
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 回答