180 lines
5.0 KiB
Scala
180 lines
5.0 KiB
Scala
package green.thisfieldwas.embracingnondeterminism.data
|
|
|
|
/** A singly-linked list specialization optimized for constant-time
|
|
* concatenation. This list, or "Chain", has a non-zero length which makes it
|
|
* especially useful for cases where there is always at least one of some piece
|
|
* of data.
|
|
*
|
|
* In the context of validation: as failures occur they must be gathered in a
|
|
* way that is computationally cheap. Concatenation using this structure is a
|
|
* constant-time operation, so large graphs of validation functions may fail
|
|
* quickly without burdening the system with potentially large numbers of error
|
|
* cases should they be produced in quantity. As validation failure implies a
|
|
* non-zero presence of errors, this Chain structure represents one or more
|
|
* values indicating reasons for failure.
|
|
*
|
|
* @tparam A
|
|
* The type of the values held within the chain.
|
|
*/
|
|
trait NonEmptyChain[+A] {
|
|
|
|
import NonEmptyChain._
|
|
|
|
/** The first value in the chain.
|
|
*
|
|
* @return
|
|
* The value.
|
|
*/
|
|
def head: A
|
|
|
|
/** All but the first value in the chain, if the chain has more than one
|
|
* value.
|
|
*
|
|
* @return
|
|
* The rest of the chain
|
|
*/
|
|
def tail: Option[NonEmptyChain[A]]
|
|
|
|
/** The length of the chain, which is always non-zero.
|
|
*
|
|
* @return
|
|
* The length of the chain.
|
|
*/
|
|
def length: Int
|
|
|
|
/** Conses a value to the start of the chain.
|
|
*
|
|
* @param newHead
|
|
* The new start of the chain.
|
|
* @tparam B
|
|
* The type of the head.
|
|
* @return
|
|
* The new chain.
|
|
*/
|
|
def cons[B >: A](newHead: B): NonEmptyChain[B] = prepend(Singleton(newHead))
|
|
|
|
/** Prepends a chain to the start of this one.
|
|
*
|
|
* @param prefix
|
|
* The chain to prepend.
|
|
* @tparam B
|
|
* The type of the chain.
|
|
* @return
|
|
* The new chain.
|
|
*/
|
|
def prepend[B >: A](prefix: NonEmptyChain[B]): NonEmptyChain[B] = prefix.append(this)
|
|
|
|
/** Appends a chain to the end of this one.
|
|
*
|
|
* @param suffix
|
|
* The chain to append.
|
|
* @tparam B
|
|
* The type of the chain.
|
|
* @return
|
|
* The new chain.
|
|
*/
|
|
def append[B >: A](suffix: NonEmptyChain[B]): NonEmptyChain[B] = Append(this, suffix)
|
|
|
|
/** Converts the chain to a Scala Seq.
|
|
*
|
|
* @return
|
|
* The values in a Seq.
|
|
*/
|
|
def toSeq: Seq[A] = head +: tail.fold(Seq[A]())(_.toSeq)
|
|
|
|
override def equals(obj: Any): Boolean =
|
|
if (!obj.isInstanceOf[NonEmptyChain[Any]]) {
|
|
false
|
|
} else {
|
|
val other = obj.asInstanceOf[NonEmptyChain[Any]]
|
|
toSeq == other.toSeq
|
|
}
|
|
|
|
override def hashCode(): Int =
|
|
toSeq.foldLeft(7)((hash, value) => 31 * hash + value.hashCode())
|
|
}
|
|
|
|
object NonEmptyChain {
|
|
|
|
import green.thisfieldwas.embracingnondeterminism.syntax.functor._
|
|
|
|
/** Creates a `NonEmptyChain` using idiomatic syntax:
|
|
*
|
|
* {{{
|
|
* NonEmptyChain(1, 2, 3, ...)
|
|
* }}}
|
|
*
|
|
* @param value
|
|
* The first, and required, value of the chain.
|
|
* @param rest
|
|
* The rest, and optional, values of the chain.
|
|
* @tparam A
|
|
* The type of the values.
|
|
* @return
|
|
* The new chain.
|
|
*/
|
|
def apply[A](value: A, rest: A*): NonEmptyChain[A] =
|
|
rest.map[NonEmptyChain[A]](Singleton(_)).foldLeft[NonEmptyChain[A]](Singleton(value))(_ append _)
|
|
|
|
/** Unapplies the chain for pattern matching. Allows idiomatic syntax:
|
|
*
|
|
* {{{
|
|
* nec match {
|
|
* case NonEmptyChain(1, 2, 3) => ???
|
|
* }
|
|
* }}}
|
|
*
|
|
* @param chain
|
|
* The chain to unapply.
|
|
* @tparam A
|
|
* The type of values in the chain.
|
|
* @return
|
|
* A Some containing the Seq of values in the chain.
|
|
*/
|
|
def unapply[A](chain: NonEmptyChain[A]): scala.Option[Seq[A]] =
|
|
scala.Some(chain.toSeq)
|
|
|
|
/** Represents the singleton case of the chain, where only one value exists.
|
|
*
|
|
* @param head
|
|
* The single value.
|
|
* @tparam A
|
|
* The type of the values held within the chain.
|
|
*/
|
|
case class Singleton[+A](head: A) extends NonEmptyChain[A] {
|
|
|
|
override def tail: Option[NonEmptyChain[A]] = None
|
|
|
|
override def length: Int = 1
|
|
}
|
|
|
|
/** The concatenation case of the chain. This represents the linkage between
|
|
* two chains and is a constant-time encoding of the operation.
|
|
*
|
|
* @param prefix
|
|
* The left-hand side of the concatenated chain.
|
|
* @param suffix
|
|
* The right-hand side of the concatenated chain.
|
|
* @tparam A
|
|
* The type of the values held within the chain.
|
|
*/
|
|
case class Append[+A](prefix: NonEmptyChain[A], suffix: NonEmptyChain[A]) extends NonEmptyChain[A] {
|
|
|
|
override def head: A = prefix.head
|
|
|
|
override def tail: Option[NonEmptyChain[A]] = prefix.tail.map(suffix.prepend).orElse(Some(suffix))
|
|
|
|
override def length: Int = prefix.length + suffix.length
|
|
}
|
|
|
|
/** The Semigroup instance of the NonEmptyChain. This is a simple proxy over
|
|
* the append() operation.
|
|
*
|
|
* @tparam A
|
|
* The type of the values held by the chain.
|
|
* @return
|
|
* The Semigroup instance.
|
|
*/
|
|
implicit def nonEmptyChainSemigroup[A]: Semigroup[NonEmptyChain[A]] = _ append _
|
|
}
|