Non empty data structures

[Chris Marshall]

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

[Tomas Mikula]

Is there any benefit to define them via OneAnd, rather than have dedicated implementations?

Regards,

Tomas

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at https://groups.google.com/group/scalaz.
For more options, visit https://groups.google.com/d/optout.

[Chris Marshall]

You get all the instances (traverse, foldable etc etc) from OneAnd. If OneAnd is not used for this, what is the point of it?

The main negative I see is that you allow the possibility that someone create an incorrect instance directly (eg OneAnd(1, ISet.singleton(1))) and then pass it to you as a NonEmptySet (which appears to be of size 2)

Chris

[Tomas Mikula]

On Tue, Jun 7, 2016 at 4:42 PM, Chris Marshall <oxbow...@gmail.com> wrote:

You get all the instances (traverse, foldable etc etc) from OneAnd.

Oh, OK. I actually had instances in mind and realized that you don't get monad instance for

    type NonEmptyList[A] = OneAnd[IList, A]

from the monad for IList. Then I looked at the code for OneAnd and see that you get the monad instance from MonadPlus[IList].

Tomas