#### 180 lines 5.0 KiB Scala Raw Permalink Blame History

 ```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 _ ``` ```} ```