14 files changed, 496 insertions, 22 deletions
diff --git a/std/magic/arrays.pk b/std/magic/arrays.pk
new file mode 100644
index 0000000..a0207c1
--- /dev/null
+++ b/std/magic/arrays.pk
@@ -0,0 +1,20 @@
+## std.arrays: The array[T, S] primitive and associated functions.
+## A stub module for documentation.
+
+## Primitive fixed-size arrays. Their size is statically known at compile-time.
+pub type array[T, S: static[uint]]
+
+## Array access. Returns None if i is out of range.
+pub func get[T, S: static[uint]](self: array[T, S], i: uint): T?
+## Array mutation.
+# todo: how do we detect range errors?
+pub func set[T, S: static[uint]](self: mut array[T, S], i: uint, val: T): T?
+## A helper function to get the length of an array.
+## Known to the compiler, and computed at compile-time.
+pub func len[T, S: static[uint]](self: array[T, S], i: uint): T?
+
+type ArrayIter[T, S: static[uint]] = struct
+  ...
+pub func iter[T, S: static[uint]](self: array[T, S]): ArrayIter[T, S]
+
+# todo: Eq, PartialEq, Ord, PartialOrd
diff --git a/std/magic/booleans.pk b/std/magic/booleans.pk
new file mode 100644
index 0000000..3c7e28e
--- /dev/null
+++ b/std/magic/booleans.pk
@@ -0,0 +1,42 @@
+## std.booleans: Booleans and related types. Mostly compiler magic.
+## A stub module for documentation.
+
+pub type unit = union[sole]
+pub type bool = union[false, true]
+
+# note: puck could resolve kleene.false vs bool.false...
+# this is probably not worth it compared to improved type inference
+# pub type Kleene = union[False, Maybe, True]
+
+## Boolean equality
+pub func ==(a: bool, b: bool): bool =
+  match a
+  of (true, true), (false, false): true
+  of (false, true), (true, false): false
+
+pub func !=(a: bool, b: bool): bool =
+  not a == b
+
+## Boolean negation
+pub func not(a: bool): bool =
+  match a
+  of true: false
+  of false: true
+
+## Boolean conjunction
+pub func and(a: bool, b: bool): bool =
+  match (a, b)
+  of (true, true): true
+  of _: false
+
+## Boolean disjunction
+pub func or(a: bool, b: bool): bool =
+  match (a, b)
+  of (false, false): false
+  of _: true
+
+## Boolean exclusive disjunction
+pub func xor(a: bool, b: bool): bool =
+  match (a, b)
+  of (true, true), (false, false): false
+  of (true, false), (false, true): true
diff --git a/std/magic/numbers.pk b/std/magic/numbers.pk
new file mode 100644
index 0000000..007f4b7
--- /dev/null
+++ b/std/magic/numbers.pk
@@ -0,0 +1,77 @@
+## std.numbers: Operations on numbers and such.
+## A stub module for documentation.
+# reference: https://en.wikipedia.org/wiki/IEEE_754
+
+## The default integer type. Size depends on architecture.
+pub type int
+## A signed 8-bit integer.
+pub type i8
+## A signed 16-bit integer.
+pub type i16
+## A signed 32-bit integer.
+pub type i32
+## A signed 64-bit integer.
+pub type i64
+## A signed 128-bit integer.
+pub type i128
+
+## The default unsigned integer type. Size depends on architecture.
+pub type uint
+## An unsigned 8-bit integer.
+pub type u8
+## An unsigned 16-bit integer.
+pub type u16
+## An unsigned 32-bit integer.
+pub type u32
+## An unsigned 64-bit integer.
+pub type u64
+## An unsigned 128-bit integer.
+pub type u128
+
+## A floating-point type. Takes up 64 bits by default.
+pub type float = f64
+## A 32-bit floating point type. Single precision.
+pub type f32
+## A 64-bit floating point type. Double precision.
+pub type f64
+## A 128-bit floating point type. Quadruple precision.
+pub type f128
+
+## A decimal type, according to IEEE 754. Takes up 64 bits by default.
+pub type decimal = dec64
+## A 64-bit decimal type.
+pub type dec64
+## A 128-bit decimal type.
+pub type dec128
+
+## 8-bit bytes.
+pub type byte = u8
+## 4-byte chars. These represent distinct Unicode characters.
+pub type char = distinct u32
+## An alias to `char`, to match with `str`.
+pub type chr = char
+
+## The IEEE floating point value of *Not a Number*.
+pub const NaN: f64 = 0x7FF7FFFFFFFFFFFF
+## The IEEE floating point value of positive infinity.
+pub const Inf: f64 = 0x7FF0000000000000
+## The IEEE floating point value of negative infinity.
+pub const NegInf: f64 = 0xFFF0000000000000
+
+# todo: type conversions
+
+pub func +[T](a: T, b: T): T
+pub func -[T](a: T, b: T): T
+pub func *[T](a: T, b: T): T
+pub func /[T](a: T, b: T): float
+pub func ^[T](a: T, b: T): T # todo: should be exp?
+
+pub func div[T](a: T, b: T): T
+pub func mod[T](a: T, b: T): T # fixme
+pub func rem[T](a: T, b: T): T
+
+pub func shl[T](a: T): T
+pub func shr[T](a: T): T
+
+pub func abs[T](a: T): T
+pub func neg[T](a: T): bool
diff --git a/std/pointers.pk b/std/magic/pointers.pk
index 1856ab1..e2a95cf 100644
--- a/std/pointers.pk
+++ b/std/magic/pointers.pk
@@ -1,3 +1,7 @@
 ## std.pointers: Pointer arithmetic. Unsafe.
 
+pub type ptr[T]
+pub type ref[T]
+pub type unique[T]
+
 # idk what goes here
diff --git a/std/prelude/clone.pk b/std/prelude/clone.pk
new file mode 100644
index 0000000..5b16b8b
--- /dev/null
+++ b/std/prelude/clone.pk
@@ -0,0 +1,28 @@
+## std.clone: Interfaces for explicitly Clonable types.
+## This module is imported by default.
+
+## The Clone interface. Any type implementing Clone is cloneable.
+## Data structures built with pointers and references are pretty much
+## the only things that are *not* implicitly clonable.
+pub type Clone = interface
+  clone(lent Self): Self # todo
+
+## Generic implementation of `clone` for structs.
+pub func clone[T: struct](self: T): T =
+  ...
+
+## Generic implementation of `clone` for tuples.
+pub func clone[T: tuple](self: T): T =
+  ...
+
+## Implementation of `clone` for arrays of any size.
+pub func clone[T, S: static[uint]](self: array[T, S]): array[T, S] =
+  ...
+
+## Implementation of `clone` for lists.
+pub func clone[T](self: list[T]): list[T] =
+  ...
+
+## Implementation of `clone` for strings.
+pub func clone(self: str): str =
+  ...
diff --git a/std/prelude/compare.pk b/std/prelude/compare.pk
new file mode 100644
index 0000000..b506761
--- /dev/null
+++ b/std/prelude/compare.pk
@@ -0,0 +1,30 @@
+## std.compare: Interfaces for comparable types.
+## reference: https://doc.rust-lang.org/std/cmp
+
+## The Eq interface
+pub type Eq = interface
+  ==(Self, Self): bool
+
+## A possible Equivalence interface.
+# equality, equivalence, isomorphism, homomorphism, congruence
+# pub type Equiv = interface
+#   ...
+
+pub type PartialOrd = interface
+  <(a: Self, b: Self): bool
+
+pub type Ord = interface
+  <(a: Self, b: Self): bool
+  ==(a: Self, b: Self): bool
+
+pub !=[T: Eq](a: T, b: T): bool =
+  not a == b
+
+pub func >[T: PartialOrd](a: T, b: T): bool =
+  b < a
+
+pub func <=[T: Ord](a: T, b: T): bool =
+  a < b or a == b
+
+pub func >=[T: Ord](a: T, b: T): bool =
+  a > b or a == b
diff --git a/std/prelude/convert.pk b/std/prelude/convert.pk
new file mode 100644
index 0000000..6abf543
--- /dev/null
+++ b/std/prelude/convert.pk
@@ -0,0 +1,23 @@
+## std.convert: Interfaces for type coersion and conversion.
+## This module is imported by default.
+
+## The Coerce interface is used for type conversion that will not fail.
+## Its associated methods, `from` and `into`, are used internally
+## by the compiler for implicit type conversion (coersion).
+pub type Coerce[T] = interface
+  from(T): Self
+  # into(Self): T
+
+## The `into` function is automatically implemented for all types that
+## implement `from`: that is, all types U that are convertable to T.
+pub func into[T, U: Coerce[T]](self: T): U =
+  from(self)
+
+## The Convert interface is used for type conversion that may fail.
+# We'll see what this breaks.
+pub type Convert[T] = interface
+  from(T): Self?!
+
+## A blanket implementation of a corresponding `into` function.
+pub func into[T, U: Convert[T]](self: T): U =
+  from(self)
diff --git a/std/prelude/format.pk b/std/prelude/format.pk
index 3adb68b..4f4746d 100644
--- a/std/prelude/format.pk
+++ b/std/prelude/format.pk
@@ -39,7 +39,7 @@ pub func dbg(self: tuple): str =
 
 ## An implementation of the Debug interface for all arrays and lists.
 pub func dbg[T: Debug](self: Iter[T]): str =
-  "[{}]".fmt(self.map(x => x.str).join(", "))
+  "[{}]".fmt(self.map(x => x.dbg).join(", "))
 
 ## The fmt macro. Builds a formatted string from its arguments.
 pub macro fmt(self: static[str], args: varargs[Display]): str =
diff --git a/std/prelude/io.pk b/std/prelude/io.pk
new file mode 100644
index 0000000..e621e01
--- /dev/null
+++ b/std/prelude/io.pk
@@ -0,0 +1,29 @@
+## std.io: Platform-independent I/O constructs.
+## This module is imported by default.
+
+pub type File = ...
+pub type FileMode = union[Read, Write, ReadWrite, Append]
+
+# todo: file destructors call `close`
+
+pub const stdout: File = ...
+pub const stdin: File = ...
+pub const stderr: File = ...
+
+pub func open(path: str, mode: FileMode): File =
+  ...
+
+pub func close(file: File) =
+  ...
+
+pub func write(file: File, values: varargs[str]) =
+  ...
+
+pub func read(file: File): str? =
+  ...
+
+pub func lines(file: File): Iter[str] =
+  ...
+
+pub func chars(file: File): Iter[chr] =
+  ...
diff --git a/std/prelude/iterators.pk b/std/prelude/iterators.pk
index 224460f..82137ee 100644
--- a/std/prelude/iterators.pk
+++ b/std/prelude/iterators.pk
@@ -1,38 +1,185 @@
 ## std.iterators: The Iter interface and associated functions.
 ## This module is imported by default.
+# reference: https://doc.rust-lang.org/std/iter/
+# reference: https://docs.rs/itertools/latest/itertools/
+
+use std.queue.ring
 
 ## The Iter interface. Any type implementing `next()` is iterable.
 pub type Iter[T] = interface
-  next(mut Self): Option[T]
+  next(mut Self): T? # should T be lent?
+
+## The IntoIter interface.
+## Any type implementing `iter()` may be converted to an iterable type.
+pub type IntoIter[T] = interface
+  iter(Self): Iter[T]
+
+## The Peek interface.
+## Any type implementing `Iter`, `peek`, and `peek_nth` is peekable.
+pub type Peek[T] = interface
+  next(mut Self): T?
+  peek(mut Self): T?
+  peek_nth(mut Self, int): T?
+
+## A concrete Peekable structure formed from a generic Iter type.
+## Implements the Peek interface. Can be formed with `.peekable()`
+type PeekImpl = struct
+  iter: ref Iter[T] # this is probably bad... heap allocated...
+  buf: Queue[T]
+
+## Convert any Iter into a peekable equivalent.
+# https://github.com/LukeMathWalker/multipeek/blob/main/src/lib.rs
+pub func peekable[T](iter: owned Iter[T]): PeekImpl[T] =
+  { iter, buf: ... } # todo: implement Queue, somewhere
+
+pub func next[T](self: mut PeekImpl[T]): T? =
+  match self.buf.pop()
+  of None:
+    self.iter.next()
+  of Some(val):
+    val
+pub func peek[T](self: mut PeekImpl[T]): T? =
+  match self.buf.peek()
+  of None:
+    self.buf.push(self.iter.next())
+    self.buf.peek()
+  of Some(val):
+    val
+pub func peek_nth[T](self: mut PeekImpl[T], i: uint): T? =
+  if self.buf.len > i:
+    self.buf.get(i)!
+  else:
+    for _ in self.buf.len .. i: # fixme
+      match self.buf.next()
+      of None:
+        return None
+      of Some(val):
+        self.buf.push(val)
+    self.buf.peek()
 
 # todo: useful functions for an iterator
 # https://doc.rust-lang.org/std/iter/trait.Iterator.html#provided-methods
 
-pub func advance_by[T](self: Iter[T], n: uint): Result[T, ...] =
+func advance_by[T](self: Iter[T], n: uint) =
   for i in 0 .. n:
     if self.next().is_none():
-      return Error(...)
-  Okay
+      return
 
 pub func get[T](self: Iter[T], at: uint): Option[T]
-  self.advance_by(at-1).ok?
+  self.advance_by(at-1).ok? # fixme
   self.next()
 
-# todo: implement iter[T](self: ...): Iter[T] funcs
-# todo: efficient functional methods
+## Returns true if every element in an Iter fulfills the conditional.
+pub func all[T](self: Iter[T], cond: T -> bool): bool =
+  for elem in self:
+    if not cond(elem):
+      return false
+  true
 
-## The Peek interface. Any type implementing `Iter`, `peek`, and `peek_nth` is peekable.
-pub type Peek[T] = interface
-  next(mut Self): Option[T]
-  peek(mut Self): Option[T]
-  peek_nth(mut Self, int): Option[T]
+## Returns true if any element in an Iter fulfills the conditional.
+pub func any[T](self: Iter[T], cond: T -> bool): bool =
+  for elem in self:
+    if cond(elem):
+      return true
+  false
 
-# todo: implement peek[T](self: Iter[T]): Peek[T]
-# todo: implement Peekable struct
-# https://github.com/LukeMathWalker/multipeek/blob/main/src/lib.rs
+## Returns true if an Iter contains the given element.
+pub func contains[T](self: Iter[T], val: T): bool =
+  self.any(elem => elem == val)
+
+## Returns the first element matching a condition, if it exists.
+pub func find[T](self: Iter[T], cond: T -> bool): T? =
+  for elem in self:
+    if cond(elem):
+      return Some(elem)
+  None
+
+## Returns the position of the first element matching a condition, if it exists.
+pub func position[T](self: Iter[T], cond: T -> bool): T? =
+  var i = 0
+  for elem in self:
+    if cond(elem):
+      return Some(i)
+    i += 1
+  None
+
+pub func fold[T, U](self: Iter[T], init: U, op: (U, T) -> U) =
+  var res = init
+  for elem in self:
+    res = res.op(elem)
+  res
+
+pub func reduce[T, U](self: Iter[T], op: (U, T) -> U): U? =
+  match self.next()
+  of None:
+    None
+  of Some(val):
+    var res = val
+    for elem in self:
+      res = op(res, elem)
+    Some(res)
+
+pub func count[T](self: Iter[T], element: T): uint =
+  self.fold(0, (elem, acc) => if elem == element: acc + 1 else: acc)
+
+pub func count[T](self: Iter[T]): uint =
+  self.fold(0, (elem, acc) => acc + 1)
+
+pub func last[T](self: Iter[T]): T =
+  var res = None
+  for elem in self:
+    res = elem
+  res
+
+pub func ==[T](first: Iter[T], second: Iter[T]): bool =
+  for (a, b) in :
+    if a != b:
+      return false
+  true
+
+type LazyIter = struct
+  ...
+
+pub func apply[T](self: mut LazyIter[T], fn: T -> T)
+pub func map[T, S](self: Iter[T], fn: T -> S): LazyIter[S]
+pub func foreach[T, S](self: Iter[T], fn: T -> S): LazyIter[T]
+
+pub func enumerate[T](self: LazyIter[T]): LazyIter[T] # todo: impl with map or similar
+
+pub func dedup[T](self: Iter[T], sorted = false): LazyIter[T]
+pub func filter[T](self: Iter[T], cond: T -> bool): LazyIter[T]
+
+## Takes (at most) the first `n` elements of an iterator.
+pub func take[T](self: Iter[T], n: uint): LazyIter[T]
+## Skips (at most) the first `n` elements of an iterator.
+pub func skip[T](self: Iter[T], n: uint): LazyIter[T]
+
+pub func repeat[T](self: Iter[T], n: uint): LazyIter[T] # cycle??
+pub func intersperse[T](self: Iter[T], item: T): LazyIter[T]
+pub func step[T](self: Iter[T], step: uint): LazyIter[T]
+pub func flatten[T](self: Iter[Iter[T]]): LazyIter[T]
+
+pub func chain[T](first: Iter[T], second: Iter[T]): LazyIter[T]
+
+pub func zip[T, U](first: Iter[T], second: Iter[U]): Iter[(T, U)]
+pub func unzip[T, U](self: Iter[(T, U)]): (Iter[T], Iter[U])
+
+# equivalent of collect. useful for type conversion
+pub func from[T](self: LazyIter[T]): list[T]
+pub func from(self: LazyIter[chr]): str
+
+pub type BoundIter[T] = interface
+  next(mut Self): T?
+  pop(mut Self): T?
+
+pub func rev[T](self: BoundIter[T]): BoundIter[T]
+
+pub type SizedIter[T] = interface
+  next(mut Self): T?
+  pop(mut Self): T?
+  len(Self): uint
+  get(mut Self): T?
 
-## We don't want a Countable. It's not terribly useful.
-# pub type Countable[T] = interface
-#   next(mut Self): Option[T]
-#   len(Self): uint
-#   get(Self, uint): Option[T]
+pub func max(self: Iter[Comparable[T]]): T
+pub func min(self: Iter[Comparable[T]]): T
+pub func sorted(self: Iter[Comparable[T]]): bool
diff --git a/std/prelude/lists.pk b/std/prelude/lists.pk
index 410cfed..1e8dee5 100644
--- a/std/prelude/lists.pk
+++ b/std/prelude/lists.pk
@@ -99,6 +99,10 @@ pub func remove[T](self: mut list[T], i: uint): T =
 pub func last[T](self: list[T]): lent T? =
   self.get(self.len - 1)
 
+# todo: many questions. owned? how does it not free?
+pub func iter[T](self: owned list[T]): ListIter[T] =
+  ...
+
 # todo: iteration...
 # todo: destructors...
 # todo: syntax for inlining + other pragmas... as a macro, perhaps?
diff --git a/std/prelude/ranges.pk b/std/prelude/ranges.pk
new file mode 100644
index 0000000..e3af8a4
--- /dev/null
+++ b/std/prelude/ranges.pk
@@ -0,0 +1,65 @@
+## std.ranges: Ranges of integers and other things. For iteration.
+## This module is imported by default.
+
+type Range[T] = struct
+  start: T
+  end: T
+
+type RangeInclusive[T] = struct
+  start: T
+  end: T
+  done: bool
+
+## Exclusive ranges. Useful for iteration.
+## Includes `from`, does not include `to`.
+pub func ..(from: int, to: int): Range[int] =
+  { from, to }
+
+## Inclusive ranges. Useful for ranges.
+## Includes `from` and `to`.
+pub func ..=(from: int, to: int): RangeInclusive[int] =
+  { from, to, done: false }
+
+# todo: implement for all types that can increment or smth idk
+pub func next[T: int](self: mut Range[T]): T? =
+  if self.start < self.end:
+    result = Some(self.start)
+    self.start += 1
+  else:
+    result = None
+
+# todo: We don't need a mutable Range here to peek.
+# How does this interact with interfaces?
+pub func peek[T: int](self: mut Range[T]): T? =
+  self.peek_nth(0)
+
+pub func peek_nth[T: int](self: mut Range[T], i: uint): T? =
+  let res = self.start + i
+  if res < self.end:
+    return Some(res)
+  else:
+    return None
+
+pub func next[T: int](self: mut RangeInclusive[T]): T? =
+  if self.done:
+    return None
+  elif self.start < self.end:
+    let res = self.start
+    self.start += 1
+    return Some(res)
+  elif self.start == self.end:
+    self.done = true
+    return Some(self.start)
+  else:
+    self.done = true
+    return None
+
+pub func peek[T: int](self: mut RangeInclusive[T]): T? =
+  self.peek_nth(0)
+
+pub func peek_nth[T: int](self: mut RangeInclusive[T], i: uint): T? =
+  let res = self.start + i
+  if res <= self.end:
+    return Some(res)
+  else:
+    return None
diff --git a/std/prelude/results.pk b/std/prelude/results.pk
index 1209b40..7dc5a11 100644
--- a/std/prelude/results.pk
+++ b/std/prelude/results.pk
@@ -110,6 +110,11 @@ pub macro ?[T, E](self: Result[T, E]) =
     of Okay(x): x
     of Error(e): return Error(e)
 
+## Syntactic sugar for dynamic `Result` type declarations.
+pub macro ?!(T: type) =
+  quote:
+    Result[`T`]
+
 ## Overloads the `==` operation for use on Results.
 pub func ==[T, E, F](a: Result[T, E], b: Result[T, F]): bool =
   match (a, b)
diff --git a/std/prelude/strings.pk b/std/prelude/strings.pk
index c2b0518..6abca31 100644
--- a/std/prelude/strings.pk
+++ b/std/prelude/strings.pk
@@ -89,7 +89,7 @@ pub func chars(self: str): list[chr] # todo: useful?
 pub func &(a: str, b: str): str =
   ...
 
-## Syntatic sugar for sring appending.
+## Syntatic sugar for string appending.
 pub func &=(a: mut str, b: owned str) =
   a.push(b)