Scalaz has OneAnd - we can implement a series of non empty structures such as a NonEmptySet or a NonEmptyHeap as simple type aliases:
type NonEmptySet[A] = OneAnd[ISet, A]
type NonEmptyHeap[A] = OneAnd[Heap, A]
We construct type constructors on a module: e.g.
object NonEmptySet {
def singleton[A](a: A): NonEmptySet[A] = OneAnd(a, ISet.empty)
def apply[A: Order](a: A, as: A*) = fromSet(ISet.fromList(as.toList)).fold(singleton(a))(_ insert a)
def fromSet[A: Order](set: ISet[A]): Option[NonEmptySet[A]] = set.minView map { case (h, t) => OneAnd(h, t) }
}
We can construct syntax for it
class NonEmptySetOps[A](val self: NonEmptySet[A]) {
def insert(a: A)(implicit O: Order[A]): NonEmptySet[A] =
if (a lte self.head) OneAnd(a, self.tail insert self.head)
else OneAnd(self.head, self.tail insert a)
...
}
We can do similarly with heap. These are really useful - are they considerations for addition into scalaz? Should they be bespoke data structures of their own (rather than hijack OneAnd)?
Chris