Функциональная Pearl: Реализация след в JavaScript

Question

Росс Патерсон: Arrows and Computation вводит trace функцию (на странице 11):

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

trace функция полезна для модульности волшебного шага в обратной 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) 

во всяком случае, мне было интересно, как реализовать функцию 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)]; 
    } 
}); 

в Orde г реализовать 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; 
 
    }; 
 
}

Надежда, что помогает.