Iterators in Val

Collection.val

/// A type representing a collection of values.
public trait Collection {

  /// The type of the `Self`'s elements.
  type Element

  /// The type of a position in `Self`.
  type Index: Equatable

  /// Returns `self`'s first position.
  fun first_index() -> Index

  /// Returns `self`'s "past the end" position.
  fun end_index() -> Index

  /// Returns the position after `index` in `self`.
  ///
  /// - Requires: `index` is a valid index in the collection other than `end_index()`.
  fun index_after(_ index: Index) -> Index

  /// Projects the element at `index` in `self`.
  ///
  /// - Requires: `index` is a valid index in the collection other than `end_index()`.
  subscript(_ index: Index) : Element { let }

}

Iterator.val

/// A forward iterator in a collection.
public type Iterator<Base: Collection, base_access: let> {

  /// A projection of the base collection.
  var base: remote base_access Base

  /// The position of `self` in `base`.
  var position: Base.Index

  /// Creates an iterator projecting the elements of `base` from `position`.
  public init(_ base: base_access Base, at position: Base.Index) {
    self.base = base
    self.position = position
  }

  /// Projects the element currently pointed by `self`.
  public subscript() : Base.Element {
    let { base[index] }
  }

  /// Advances `self`.
  public fun advances() inout {
    position = base.index_after(position)
  }

}

extension Iterator where base_access: inout {

  public subscript() : Base.Element {
    inout { &base[index] }
  }

}

extension Iterator where base_access: sink {

  public subscript() : Base.Element {
    sink { &base[index] }
  }

}

Vector.val

public type Vector<Element> {

  /// A pointer to the start `self`'s storage.
  var storage: MutablePointer<Element>
  
  /// The number of elements `self`.
  var _count: MutablePointer<Element>

  /// The capacity of the vector.
  var _capacity: Int

  /// Creates an empty vector.
  public init() {
    storage = .null
    _count = 0
    _capacity = 0
  }

  /// Returns the number of elements in `self`.
  public fun count() -> Int { _count.copy() }

  /// Returns the number of elements that can be stored in `self` before allocating new storage.
  public fun capacity() -> Int { _capacity.count() }

}

public conformance Vector: Collection {

  public typealias Index = Int

  public fun first_index() -> Int { 0 }

  public fun end_index() -> Int { count() }

  fun index_after(_ index: Index) -> Index { index + 1 }

  subscript(_ index: Index) : Element {
    let {
      precondition((index >= 0) && (index < count()), "index is out of bounds")
      yield unsafe storage[index]
    }
  }

}

Your Vector's missing deinit I think. But anyway, wouldn't we implement that using Array?

Yes. I used Vector to make the correspondence with C++'s std::vector clear.

Also I think our arrays should not store three words but have their header laid out before the out-of-line storage (like Swift, AFAIK).

Yes; all I meant was that if you are going to implement something called Vector with C++ std::vector semantics, you should use Val.Array to do it, so you don't have to worry about things like the missing deinit. Nothing in the standard mandates any particular data layout for std::vector.

Oh, didn't know that. So yep, agreed completely.