機能パール：JavaScriptでトレースを実装

Question

ロスパターソン：Arrows and Computationは（11ページ）trace機能が導入されています

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

trace機能はcircular programsで魔法のフィードバックステップをモジュール化するのに便利です。例えば、リチャード・バードの有名なrepminの木の最小リーフ値を見つける関数とは、すべてのリーフ値を最小リーフ値に置き換えた同じツリーを作成します.1回のパスでレイジー評価とローカル再帰（letrecによって提供される）：オードで

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

を：

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) 

とにかく、私は次のように我々はrepminを実装することができるようなJavaScriptでtrace機能を実装する方法を思っていました私はもともとc約束することを考え

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

：R traceを実装するために、我々は、我々のような何かを書くことができるようにletrecによって提供されるように局所的な再帰を必要とします。ただし、それは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関数を定義する必要があります。