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次
}

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")
}

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
    }
  }
}

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,")
}

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

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

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")
}

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次
}

fn filter[T](xs : List[T], pred : (T) -> Bool) -> List[T] {
  match xs {
    Nil => Nil
    Cons(x, xs) if pred(x) => Cons(x, filter(xs, pred))
    Cons(_, xs) => filter(xs, pred)
  }
}

enum Filter {
  IsEven
  IsOdd
  IsPositive
  IsNegative
}

fn run(self : Filter, data : Int) -> Bool {
  match self {
    IsEven => data % 2 == 0
    IsOdd => data % 2 != 0
    IsPositive => data > 0
    IsNegative => data < 0
  }
}

fn filter_defunct(xs : List[Int], pred : Filter) -> List[Int] {
  match xs {
    Nil => Nil
    Cons(x, xs) if run(pred, x) => Cons(x, filter_defunct(xs, pred))
    Cons(_, xs) => filter_defunct(xs, pred)
  }
}

enum FilterExtend {
  //...
  IsLessThan(Int)
}

fn run_extend(self : FilterExtend, data : Int) -> Bool {
  match self {
    IsLessThan(n) => data < n
    //...
  }
}

enum FilterExtendCompose {
  //...
  And(FilterExtend, FilterExtend)
}

fn run_extend_compose(self : FilterExtendCompose, data : Int) -> Bool {
  match self {
    And(f1, f2) => run_extend(f1, data) && run_extend(f2, data)
    //...
  }
}

enum Tree[T] {
  Leaf(T)
  Node(T, Tree[T], Tree[T])
}

fn pre_order[T : Show](tree : Tree[T], f : (T) -> Unit) -> Unit {
  match tree {
    Leaf(x) => f(x)
    Node(x, left, right) => {
      f(x)
      pre_order(left, f)
      pre_order(right, f)
    }
  }
}

fn pre_order_cps[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  fn go {
    Leaf(x), k => k(f(x))
    Node(x, left, right), k => {
      f(x)
      go(left, fn { _ => go(right, k) })
    }
  }

  go(self, fn { x => x })
}

enum TreeCont[T] {
  Return
  Next(Tree[T], TreeCont[T])
}

fn pre_order_cps_defunct[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  fn run_cont {
    Next(tree, k) => go(tree, k)
    Return => ()
  }

  fn go {
    Leaf(x), k => {
      f(x)
      run_cont(k)
    }
    Node(x, left, right), k => {
      f(x)
      go(left, Next(right, k))
    }
  }

  go(self, Return)
}

fn pre_order_cps_defunct_loop[T : Show](
  self : Tree[T],
  f : (T) -> Unit
) -> Unit {
  loop self, Return {
    Leaf(x), k => {
      f(x)
      match k {
        Next(tree, k) => continue tree, k
        Return => ()
      }
    }
    Node(x, left, right), k => {
      f(x)
      continue left, Next(right, k)
    }
  }
}

fn pre_order_loop[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  let mut k = Return
  let mut t = self
  while true {
    match t {
      Leaf(x) => {
        f(x)
        match k {
          Next(tree, next) => {
            k = next
            t = tree
          }
          Return => break
        }
      }
      Node(x, left, right) => {
        f(x)
        k = Next(right, k)
        t = left
      }
    }
  }
}

fn pre_order_loop_stack[T : Show](self : Tree[T], f : (T) -> Unit) -> Unit {
  let k = []
  let mut t = self
  while true {
    match t {
      Leaf(x) => {
        f(x)
        match k.pop() {
          Some(tree) => t = tree
          None => break
        }
      }
      Node(x, left, right) => {
        f(x)
        k.push(right)
        t = left
      }
    }
  }
}

trait AddMonoid: Add + Zero {}
trait MulMonoid: Mul + One {}
trait Semiring: AddMonoid + MulMonoid {}

/-- A semigroup is a type with an associative `(*)`. -/
class Semigroup (G : Type u) extends Mul G where
  /-- Multiplication is associative -/
  protected mul_assoc : ∀ a b c : G, a * b * c = a * (b * c)

impl[A : Eq + Semiring] Mul for Polynomial[A] with op_mul(xs, ys)
impl[A : Eq + Semiring] Add for Polynomial[A] with op_add(xs, ys)

test "algebraic laws" {
    fn prop(a : Vector[Int], b) { a + b == b + a }
    fn prop(a : Vector[Int], b, c) { a + (b + c) == (a + b) + c }
    quick_check_fn!(fn {
        ((a : Vector[Int]), (b : Vector[Int])) => {
        guard a.length() == b.length() else { true }
        prop(a, b)
        }
    })
    quick_check_fn!(fn {
        ((a : Vector[Int]), (b : Vector[Int]), (c : Vector[Int])) => {
        guard a.length() == b.length() && b.length() == c.length() else { true }
        prop(a, b, c)
        }
    })
}