代码之家 › 专栏 › 技术社区 › Aadit M Shah

函数珍珠:在JavaScript中实现跟踪

tying-the-knot lazy-evaluation functional-programming haskell javascript

Aadit M Shah · 技术社区 · 8 年前

罗斯·帕特森: Arrows and Computation 介绍 trace 功能(第11页):

trace :: ((a, c) -> (b, c)) -> a -> b
trace f a = let (b, c) = f (a, c) in b

这个 查出 函数对于模块化魔术反馈步骤非常有用 circular programs 例如,考虑理查德·伯德的著名 repmin 函数,用于查找树的最小叶值和创建一个相同的树,每个叶值都被最小叶值替换,通过巧妙地使用延迟求值和局部递归(如 letrec ):

data Tree = Leaf Int | Node Tree Tree deriving Show

repmin :: Tree -> Tree
repmin = trace repmin'

repmin' :: (Tree, Int) -> (Tree, Int)
-- put the minimum value m into the leaf and return the old value n as the minimum
repmin' (Leaf n, m) = (Leaf m, n)
-- copy the minimum value m into both the left and right subtrees and
-- set the minimum value m to the minimum of both the left and right subtrees
repmin' (Node l r, m) = let (l', lmin) = repmin' l m in
                        let (r', rmin) = repmin' r m in
                        (Node l' r', lmin `min` rmin)

无论如何,我想知道如何实现 查出 JavaScript中的函数,以便我们可以实现 雷普明 如下:

function Leaf(value) {
    this.value = value;
}

function Node(left, right) {
    this.left  = left;
    this.right = right;
}

var repmin = trace(function repmin(tree, min) {
    switch (tree.constructor) {
    case Leaf:
        return [new Leaf(min), tree.value];
    case Node:
        var [left,  lmin] = repmin(tree.left,  min);
        var [right, rmin] = repmin(tree.right, min);
        return [new Node(left, right), Math.min(lmin, rmin)];
    }
});

为了实施 查出 我们需要局部递归,如 莱特雷克 这样我们就可以写下这样的东西:

function trace(f) {
    return function (a) {
        var [b, c] = f(a, c);
        return b;
    };
}

我本来想做的 c 承诺。然而,这改变了 查出 .那么,你能想出一种方法来实现 查出 在JavaScript中不改变其语义?

1 回复 | 直到 8 年前

Aadit M Shah 8 年前

实际上,您只需要延迟求值,因为JavaScript中的赋值如下 letrec thunks trace 如下:

function trace(f) {
    return function (a) {
        var [b, c] = f(a, () => c);
        return b;
    };
}

使用以下定义: 查出 这个 repmin 功能可以保持不变:

var repmin = trace(function repmin(tree, min) {
    switch (tree.constructor) {
    case Leaf:
        return [new Leaf(min), tree.value];
    case Node:
        var [left,  lmin] = repmin(tree.left,  min);
        var [right, rmin] = repmin(tree.right, min);
        return [new Node(left, right), Math.min(lmin, rmin)];
    }
});

但是,您可能希望使用getter使数据构造函数变得懒惰:

function Leaf(value) {
    Object.defineProperty(this, "value", descOf(value));
}

function Node(left, right) {
    Object.defineProperty(this, "left",  descOf(left));
    Object.defineProperty(this, "right", descOf(right));
}

function descOf(value) {
    var desc = { enumerable: true };
    var prop = typeof value === "function" &&
        value.length === 0 ? "get" : "value";
    desc[prop] = value;
    return desc;
}

总而言之:

var tree = new Node(new Node(new Leaf(1), new Leaf(2)),
                    new Node(new Leaf(3), new Leaf(4)));

console.log("Input: ", show(tree));

console.log("Output:", show(repmin(tree)));

function show(tree) {
    switch (tree.constructor) {
    case Leaf: return "Leaf(" + tree.value + ")";
    case Node: return "Node(" + show(tree.left) + ", " + show(tree.right) + ")";
    }
}

<script>
function trace(f) {
    return function (a) {
        var [b, c] = f(a, () => c);
        return b;
    };
}

var repmin = trace(function repmin(tree, min) {
    switch (tree.constructor) {
    case Leaf:
        return [new Leaf(min), tree.value];
    case Node:
        var [left,  lmin] = repmin(tree.left,  min);
        var [right, rmin] = repmin(tree.right, min);
        return [new Node(left, right), Math.min(lmin, rmin)];
    }
});

function Leaf(value) {
    Object.defineProperty(this, "value", descOf(value));
}

function Node(left, right) {
    Object.defineProperty(this, "left",  descOf(left));
    Object.defineProperty(this, "right", descOf(right));
}

function descOf(value) {
    var desc = { enumerable: true };
    var prop = typeof value === "function" &&
        value.length === 0 ? "get" : "value";
    desc[prop] = value;
    return desc;
}
</script>

唯一的问题是,您将无法编写以下函数:

var sqr = trace((x, y) => [y * y, x]);

这是因为 * mul 功能:

var sqr = trace((x, y) => [mul(y, y), x]);

console.log(evaluate(sqr(10)));

function mul(a, b) {
    return function () {
        return evaluate(a) * evaluate(b);
    };
}

function evaluate(value) {
    return typeof value === "function" &&
        value.length === 0 ? value() : value;
}

function trace(f) {
    return function (a) {
        var [b, c] = f(a, () => c);
        return b;
    };
}

希望这有帮助。