1 files changed, 167 insertions, 20 deletions
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