Функциональная Жемчужина: Реализация трассировки в JavaScript

Question

Росс Патерсон: " Стрелки и вычисления" trace функция (на стр. 11):

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

trace Функция полезна для модуляции шага магической обратной связи в круговых программах. Например, рассмотрим знаменитый Ричард Берд 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)

Во всяком случае, мне было интересно, как реализовать trace функция в JavaScript, так что мы можем реализовать repmin следующее:

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)];
    }
});

Для того, чтобы реализовать trace нам нужна местная рекурсия, как это предусмотрено letrec так что мы можем написать что-то вроде:

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

Я изначально думал о создании c Обещание. Однако это меняет семантику trace, Итак, вы можете придумать способ реализации trace в JavaScript без изменения его семантики?

Answer 1

На самом деле, вам нужно только ленивый анализ, потому что назначения в JavaScript похожи letrec, Ленивые оценки, как правило, осуществляются с использованием thunks. Следовательно, вы можете реализовать trace следующее:

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

Используя это определение trace, 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)];
    }
});

Тем не менее, вы можете сделать ваши конструкторы данных ленивыми, используя геттеры:

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;
    };
}

Надеюсь, это поможет.