有多种方法可以递归地映射树:
const reduceTree = (f, node) => {
const go = ([x, xs]) => f(x, xs.map(go));
return go(node);
};
const mapTree = (f, node) =>
reduceTree((x, xs) => Node_(f(x), xs), node);
const Node_ = (x, xs) => ([x, xs]);
const Node = (x, ...xs) => ([x, xs]);
const tree = Node(1,
Node(2,
Node(3),
Node(4,
Node(5))),
Node(6),
Node(7,
Node(8),
Node(9),
Node(10),
Node(11)));
console.log(
mapTree(x => 2 * x, tree));
这实际上是一个优雅的解决方案,但它不是堆栈安全的。由于递归调用(xs.map(go)
)不在尾部位置,我不能回退到蹦床,并且以尾递归形式转换算法对我来说似乎微不足道。
执行此操作的常用方法可能是CPS转换,这会使计算模糊不清。也许有另一种方法来实现堆栈安全 - 例如使用发电机?是否有这种转变的一般规则,可以几乎机械的方式应用?
我主要对进行此转换的过程感兴趣,而不是最终结果。
从一个结构良好的相互递归对开始 -
// map :: (a -> b, Tree a) -> Tree b
const map = (f, [ v, children ]) =>
Node (f (v), ...mapAll (f, children))
// mapAll :: (a -> b, [ Tree a ]) -> [ Tree b ]
const mapAll = (f, nodes = []) =>
nodes .map (n => map (f, n))
我们首先删除了不可能允许尾部形式的热切Array.prototype.map
-
const map = (f, [ v, children ]) =>
Node (f (v), ...mapAll (f, children))
const mapAll = (f, [ node, ...more ]) =>
node === undefined
? []
: [ map (f, node), ...mapAll (f, more) ]
接下来添加CPS转换参数 -
const identity = x =>
x
const map = (f, [ v, children ], k = identity) =>
mapAll (f, children, newChilds => // tail
k (Node (f (v), ...newChilds))) // tail
const mapAll = (f, [ node, ...more ], k = identity) =>
node === undefined
? k ([]) // tail
: map (f, node, newNode => // tail
mapAll (f, more, moreChilds => // tail
k ([ newNode, ...moreChilds ]))) // tail
在下面的您自己的浏览器中验证结果
const Node = (x, ...xs) =>
[ x, xs ]
const identity = x =>
x
const map = (f, [ v, children ], k = identity) =>
mapAll (f, children, newChilds =>
k (Node (f (v), ...newChilds)))
const mapAll = (f, [ node, ...more ], k = identity) =>
node === undefined
? k ([])
: map (f, node, newNode =>
mapAll (f, more, moreChilds =>
k ([ newNode, ...moreChilds ])))
const tree =
Node
( 1
, Node
( 2
, Node (3)
, Node
( 4
, Node (5)
)
)
, Node (6)
, Node
( 7
, Node (8)
, Node (9)
, Node (10)
, Node (11)
)
)
console.log (map (x => x * 10, tree))
注意,CPS本身并不能使程序堆栈安全。这只是将代码放在您选择的蹦床上所需的形式。