external]

illusory0x0
2025-04-07

目前 MoonBit 社区有两个外部迭代器的实现， Yu-zh/iterator 和 FlammeShadow/iter。

本文提供一个由浅入深的教程，来帮助读者学习外部迭代器。

1. 内部迭代器和外部迭代器 [blog/iterator/internal-vs-external]

内部迭代器迭代过程是不可分割的。
外部迭代器迭代过程是可分割的。

Moonbit 标准库的 Iter[A] 是内部迭代器，没有办法把iter切分为(first : A?) 和 (rest : Iter[A])。

所以无法实现 fn uncons[A](xs : Iter[A]) -> (A, Iter[A])? 这样的接口。

也无法实现 fn next[A](self : Iter[A]) -> A? 这样的接口。

test "split internal iterator" {
  let xs = [1,2,3,4,5]
  let iter = xs.iter().drop(4)
  // 这里的 drop 只是修饰器，改变迭代的行为
  inspect!(xs.iter().last(), content="Some(5)")
  // 但是迭代过程还是 xs.iter()
  inspect!(iter.head(), content="Some(5)")
  // xs.iter().last() 仍然需要迭代5次
}

不可变外部迭代器可以很自然的实现uncons。

可变外部迭代器可以实现next。

2. 不可变外部迭代器和可变外部迭代器 [blog/iterator/immut-vs-mut]

不可变外部迭代器没有内部可变状态可以迭代多次。

可变外部迭代器只能迭代一次，虽然无法实现uncons, 但是迭代每个元素的过程仍是可分割的。

调用 next 方法后，可变外部迭代器的内部状态改变，变成剩余的迭代了。

3. 可变外部迭代器 [blog/iterator/mut-exiter]

可变外部迭代器，可以不断获取下一个元素的值，内部有一个可变的状态。

priv type ExIter[A] () -> A?

fn ExIter::next[A](self : ExIter[A]) -> A? {
  (self._)()
}

fn ExIter::from_array[A](xs : Array[A]) -> ExIter[A] {
  let mut i = 0 // i 是内部可变状态
  fn() {
    if i < xs.length() {
      let res = xs[i]
      i = i + 1
      Some(res)
    } else {
      None
    }
  }
}


test {
  let xs = [1, 2, 3, 4, 5]
  let iter = ExIter::from_array(xs)
  let mut sum = 0
  loop iter.next() {
    None => ()
    Some(x) => {
      sum += x
      continue iter.next()
    }
  }
  inspect!(sum, content="15")
}

ExIter::from_tree 是从 Tree::Tree::preorder_stack 改编而来， loop 变成 if 迭代过程可以切分，而不是一个整体。

比如 each 和eachi 这样的内部迭代器的方法，只能一下子迭代全部元素

读者可以再一次看外部迭代器的性质 [blog/iterator/internal-vs-external]

内部迭代器迭代过程是不可分割的。
外部迭代器迭代过程是可分割的。

Moonbit 标准库的 Iter[A] 是内部迭代器，没有办法把iter切分为(first : A?) 和 (rest : Iter[A])。

所以无法实现 fn uncons[A](xs : Iter[A]) -> (A, Iter[A])? 这样的接口。

也无法实现 fn next[A](self : Iter[A]) -> A? 这样的接口。

test "split internal iterator" {
  let xs = [1,2,3,4,5]
  let iter = xs.iter().drop(4)
  // 这里的 drop 只是修饰器，改变迭代的行为
  inspect!(xs.iter().last(), content="Some(5)")
  // 但是迭代过程还是 xs.iter()
  inspect!(iter.head(), content="Some(5)")
  // xs.iter().last() 仍然需要迭代5次
}

不可变外部迭代器可以很自然的实现uncons。

可变外部迭代器可以实现next。

fn ExIter::from_tree[A](root : Tree[A]) -> ExIter[A] {
  let stack = Array::new(capacity=4096) // stack 是内部可变状态
  stack.push(root)
  fn() {
    if not(stack.is_empty()) {
      let root = stack.unsafe_pop()
      match root {
        Nil => None
        Node(x, left, right) => {
          stack.push(right)
          stack.push(left)
          Some(x)
        }
      }
    } else {
      None
    }
  }
}

我们可以实现 zipWith 来同时迭代两个迭代器，但是和不可变迭代器比，ExIter只能迭代一次，迭代后就使用完所有的元素。这个和文件流的概念很相似。

fn ExIter::zipWith[A,B,C](self : ExIter[A], other : ExIter[B], f : (A,B) -> C) -> ExIter[C] {
  let xs = self
  let ys = other
  fn () {
    match (xs.next(),ys.next() ) {
      (Some(x),Some(y)) => {
        Some(f(x,y))
      }
      (_,_) => None
    }
  }
}

test "ExIter::zipWith" {
  let xs = ["apple", "orange", "watermetlon"]
  let ys = Tree::from_n(5)

  let xs = ExIter::from_array(xs)
  let ys = ExIter::from_tree(ys)

  let zs = xs.zipWith(ys,fn (x,y) { (x,y)})

  let b1 = StringBuilder::new()
  loop zs.next() {
    None => ()
    Some(x) => {
      b1.write_string("\{x},")
      continue zs.next()
    }
  }
  inspect!(b1, content=
    #|("apple", 0),("orange", 1),("watermetlon", 2),
  )
}

test "ExIter::from_tree" {
  let t2 = Tree::from_n(15)
  let iter = ExIter::from_tree(t2)
  let b1 = StringBuilder::new()
  loop iter.next() {
    None => ()
    Some(x) => {
      b1.write_string("\{x},")
      continue iter.next()
    }
  }
  inspect!(b1, content="0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,")
  let b2 = StringBuilder::new()
  t2.preorder(fn(x) { b2.write_string("\{x},") })
  inspect!(b2, content="0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,")
}

接下来我们来实现不可变外部迭代器

4. 不可变外部迭代器 [blog/iterator/immut-exiter]

不可变外部迭代器可以返回第一个元素和剩余的迭代过程

priv type ImmutExIter[A] () -> (A,ImmutExIter[A])?

fn ImmutExIter::uncons[A](self : ImmutExIter[A]) -> (A,ImmutExIter[A])? {
  (self._)()
}

这里从Array[A]构造不可变外部迭代器

fn ImmutExIter::from_array[A](xs : Array[A]) -> ImmutExIter[A] {
  fn aux(i) -> (A,ImmutExIter[A])? {
    if (i < xs.length()) {
      Some((xs[i],fn () { aux(i + 1) } ) )
    } else {
      None
    }
  }
  fn () {
    aux(0)
  }
}

测试一下迭代过程

test "ImmutExIter::from_array" {
  let xs = [1,2,3,4,5]
  let iter = ImmutExIter::from_array(xs)

  let buf = StringBuilder::new()

  loop iter.uncons() {
    None => ()
    Some((x,xs)) => {
      buf.write_object(x)
      continue xs.uncons()
    }
  }
  inspect!(buf, content="12345")
}

4.1. 实现树的不可变外部迭代器 [blog/iterator/immut-exiter-tree]

Blog 4.1.1. 前置知识 [blog/iterator/preorder-traversal]

illusory0x0
2025-04-07

二叉树的定义

priv enum Tree[A] {
  Nil
  Node(A, Tree[A], Tree[A])
}

先序遍历一棵树

fn Tree::preorder[A](self : Tree[A], f : (A) -> Unit) -> Unit {
  fn dfs(root) {
    match root {
      Nil => ()
      Node(x, left, right) => {
        f(x)
        dfs(left)
        dfs(right)
      }
    }
  }

  dfs(self)
}

我们把 Tree::preorder 改写为手动控制栈的过程 Tree::preorder_stack

fn Tree::preorder_stack[A](self : Tree[A], f : (A) -> Unit) -> Unit {
  let stack = Array::new(capacity=4096)
  stack.push(self)
  while not(stack.is_empty()) {
    let root = stack.unsafe_pop()
    match root {
      Nil => ()
      Node(x, left, right) => {
        f(x)
        stack.push(right) // 先进后出， 先被压入后处理
        stack.push(left) // 先处理左节点
      }
    }
  }
}

下面的部分是用来测试系统栈版本和手动控制栈版本的一致性。

fn Tree::from_n(n : Int) -> Tree[Int] {
  let mut i = 0
  fn dfs() {
    if i < n {
      let x = i
      i += 1
      let res = Node(x, dfs(), dfs())
      res
    } else {
      Nil
    }
  }

  dfs()
}

fn test_preorder(root : Tree[Int]) -> Unit! {
  let b1 = StringBuilder::new()
  let b2 = StringBuilder::new()
  root.preorder(fn(x) { b1.write_object(x) })
  root.preorder_stack(fn(x) { b2.write_object(x) })
  assert_eq!(b1.to_string(), b2.to_string())
}

test "preorder/preorder_stack" {
  let t1 = Node(
    1,
    Node(2, Nil, Nil),
    Node(3, Node(4, Nil, Nil), Node(5, Nil, Nil)),
  )
  let mut sum = 0
  t1.preorder(fn(x) { sum += x })
  inspect!(sum, content="15")
  let t2 = Tree::from_n(15)
  test_preorder!(t2)
}

4.1.2. 正文 [blog/iterator/immut-exiter-tree-content]

这里使用不可变单向链表作为栈，每次返回一个 ImmutExIter[A] 需要保存整个迭代上下文，

可变外部迭代器并不会保存，只能运行一次
不可变外部迭代器可以运行多次，但是需要额外保存迭代上下文

typealias Stack[A] = @immut/list.T[A]

fn ImmutExIter::from_tree[A](root : Tree[A]) -> ImmutExIter[A] {

  fn aux(stack : Stack[_]) -> (A,ImmutExIter[A])? {
    match stack {
      Nil => None
      Cons(root,rest_stack) => { // pop root from stack
        match root {
          Nil => None
          Node(x,left,right) => {
            let stack = Stack::Cons(left,Stack::Cons(right,rest_stack))
            // push right into stack
            // push left into stack
            Some((x,fn () { aux(stack)}))
          }
        }
      }
    }
  }
  fn () {
    aux(@immut/list.singleton(root))
  }
}

这里测试一下，不可变外部迭代器和 preorder 的一致性

test "ImmutExIter::from_tree" {
  let t2 = Tree::from_n(15)
  let iter = ImmutExIter::from_tree(t2)
  let b1 = StringBuilder::new()
  loop iter.uncons() {
    None => ()
    Some((x,rest)) => {
      b1.write_string("\{x},")
      continue rest.uncons()
    }
  }
  inspect!(b1, content="0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,")
  let b2 = StringBuilder::new()
  t2.preorder(fn(x) { b2.write_string("\{x},") })
  inspect!(b2, content="0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,")
}

接下来我们来实现 zipWith，这里和普通的List[A] 的 zipWith 别无二致

fn ImmutExIter::zipWith[A,B,C](self : ImmutExIter[A], other : ImmutExIter[B], f : (A,B) -> C) -> ImmutExIter[C] {
  let xs = self
  let ys = other

  match (xs.uncons(),ys.uncons()) {
    (Some((x,xs)),Some((y,ys))) => {
      fn () { Some((f(x,y),  ImmutExIter::zipWith(xs,ys,f)))}
    }
    (_,_) => {
      fn () { None }
    }
  }
}


test {
  let xs = ["apple", "orange", "watermetlon"]
  let ys = Tree::from_n(5)

  let xs = ImmutExIter::from_array(xs)
  let ys = ImmutExIter::from_tree(ys)

  let zs = xs.zipWith(ys,fn (x,y) { (x,y)})

  let b1 = StringBuilder::new()
  loop zs.uncons() {
    None => ()
    Some((x,rest)) => {
      b1.write_string("\{x},")
      continue rest.uncons()
    }
  }
  inspect!(b1, content=
    #|("apple", 0),("orange", 1),("watermetlon", 2),
  )
}

5. 参考资料 [blog/iterator/reference]

Why does the callback for Iter::new() need to return IterResult?

external iterator

internal iterator

zip n^2 complexity

Proposal: peekable iterator and pattern matching on iterators