1 迭代器是什么
在计算机编程中，迭代器是一个对象，它使程序员能够遍历容器，特别是列表。通常通过容器的接口提供各种类型的迭代器。虽然给定迭代器的接口和语义是固定的，但迭代器通常是根据容器实现的底层结构实现的，并且通常紧密耦合到容器以启用迭代器的操作语义。迭代器执行遍历并且还允许访问容器中的数据元素，但本身不执行迭代（即，并非没有采用该概念或使用术语的轻微自由）。迭代器在行为上类似于数据库游标。迭代器可以追溯到1974年的CLU编程语言。
2 为什么会需要迭代器？
- 便于数据流的控制，假定有一个数据流，这时如果有迭代器就可以很方便的操作这个数据流，当然也可以把迭代器理解为延时求值（lazy eval）啦
- 解耦算法和数据结构，比如你想找到树中符合条件的节点，传统的做法是使用一个查找算法，传入一个树对象和查找条件，遍历树进行匹配，而拥有迭代器之后，你只需不停的next直到迭代器末尾，大大增加了代码的可读性（毕竟是线性的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
select(node, condition,result) {
if (node) {
if(node.left !== '') {
select(node.left);
}
if (condition(node.value)) {
result.push(node.value);
}
if(node.right !== '') {
select(node.right);
}
}
}
|
1
2
3
4
5
6
7
8
|
select(treeIterator, condition， result) {
for(treeNode of treeIterator) {
if(condition(treeNode)) {
result.push(treeNode);
}
}
}
|
虽然线性的代码更可读，但我个人觉得递归的代码真的很美…我个人在可以递归的条件下是不会去写迭代的（除了效率限制），不过现在部分编译器支持Tail call optimization，虽然JavaScript没有，但是你可以将任何递归用黑魔法 Trampoline转化为形式上的尾递归~
3 实现迭代器
迭代器的本质是延迟求值或者说部分求值（令我想到了SICP的流模型），那么由于传统的程序执行比如递归，你是无法控制程序的控制流的，拿之前的递归遍历树的例子来看，你无法在它遍历到某个子树（这时这个子树的左右节点还存在）的情况下马上回到根节点的，这是因为受限于函数的调用栈，当然你可以通过cps变换来手动控制你的代码，这是另外一回事，这里暂不予展开。既然我们不能控制函数调用栈，那我们就一不做二不休的自己创建栈来模拟之前的遍历函数运行，这样代码就在我们的掌控下了（基于栈的程序控制其实体现着栈式虚拟机的思想，通过push和pop来控制”计算”，而CPS变换更多的体现的是续算（continuation）的传递，PL的魔法啦）
接下来我们可以看看，基于栈的非递归遍历实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
function inorder_tarverse_nonrecursive(node,condition,result) {
let stack = [];
while (true) {
while (node) {
stack.push(node);
node = node.left;
}
while (true) {
let top = stack.pop();
if (condition(top)) {
result.push(top.value);
}
if (top.right) {
node = top.right;
break;
}
if (stack.length === 0) {
break;
}
}
if (stack.length === 0) {
break;
}
}
}
|
这里给出递归实现以做对比
1
2
3
4
5
6
7
8
9
| function inorder_traverse(node,condition,result) {
if (node) {
inorder_traverse(node.left);
if (condition(node.value)) {
result.push(result);
};
inorder_traverse(node.right);
}
}
|
递归的调用栈和非递归模拟的程序栈对比
树：
非递归：
递归
可以看出非递归模拟递归的本质就在于程序控制流的模拟，这里的控制流并不是调用栈的模拟，而是计算顺序的模拟（体现在上面的例子中就是对节点值的访问顺序），非递归模拟代码就是用栈中的节点来模拟访问的次序
既然现在我们已经能够用栈来模拟控制流，这也意味着对程序的遍历的控制已经完全受制于我们（这里的完全受制是逻辑上的，屏蔽底层编译的细节），我们终于摆脱了了call stack :)
现在我们可以肆意的操控我们的遍历程序,接下来用闭包保存栈，每次next调用pop一次来实现迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| function makeTreeIterator(node){
let controlStack = [];
((function InorderIterator(currNode) {
while (currNode) {
controlStack.push(currNode);
currNode = currNode.left;
}
})(node))
return {
next: function(){
if (controlStack.length) {
let top = controlStack.pop();
if (top.right) {
let currNode = top.right;
while (currNode) {
controlStack.push(currNode);
currNode = currNode.left;
}
}
return {value: top.value, done: false};
} else {
return {done: true};
}
}
}
}
|
拉出迭代器遛遛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| let tree = {
value: 5,
left: {
value: 4,
left: '',
right: ''
},
right: {
value: 8,
left: {
value: 6,
left: '',
right: ''
},
right: ''
}
}
let test = makeTreeIterator(tree),result = [];
for(let i = test.next(); i.done !== true; i=test.next()) {
if (i.value < 5) {
result.push(i.value);
}
}
console.log(result);
|
还有一种实现迭代器的方法就是使用continuation来实现控制反转啦~
下一篇博客会去讲解如何用continuation来实现迭代器，这里先用ES6的generator来预热
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function* inOrder(node) {
let x;
if (node) {
for (x of inOrder(node.left)) {
yield x;
}
yield node.value;
for (x of inOrder(node.right)) {
yield x;
}
}
}
let test = inOrder(tree),result = [];
for(i of test) {
if (i < 5) {
result.push(i);
}
}
console.log(result);
|
4 小结
基于栈可以模拟控制流，这也是栈式虚拟机的思想，堆栈处理不愧是计算机领域强劲的技术，从迭代引申到控制流，看来“取指-执行”模型不仅仅用在CPU啊。
5 Reference
二叉树迭代器算法
What is an iterator?
Folder Iterator Continuation Token Recursive Loop
generators-iterators-control-and-continuations/