277 lines
7.9 KiB
Scala
277 lines
7.9 KiB
Scala
package green.thisfieldwas.embracingnondeterminism.data
|
|
|
|
import green.thisfieldwas.embracingnondeterminism.control.Applicative
|
|
import scala.annotation.tailrec
|
|
|
|
/** The `List` class encodes a dimension contextualized by the presence of an
|
|
* unknown number of instances of term `A`. The length of the `List` in
|
|
* practices is nondeterministic at runtime without specific knowledge of the
|
|
* inputs to the operation that produces it.
|
|
*
|
|
* This context is in the desired case if there are a non-zero number of
|
|
* instances of term `A` present within it. If the `List` is empty, it is in
|
|
* the undesired case.
|
|
*
|
|
* This `List` is modeled as a singly-linked list.
|
|
*
|
|
* @tparam A
|
|
* The type contained within the `List`.
|
|
*/
|
|
sealed trait List[+A] {
|
|
|
|
/** The first instance in the `List`, if the list is non-empty.
|
|
*
|
|
* @return
|
|
* The first instance.
|
|
* @throws NoSuchElementException
|
|
* if the list is empty.
|
|
*/
|
|
def head: A
|
|
|
|
/** The remainder of the `List`, which may be empty.
|
|
* @return
|
|
* The rest of the `List`.
|
|
* @throws NoSuchElementException
|
|
* if the list is empty.
|
|
*/
|
|
def tail: List[A]
|
|
|
|
/** Gets whether this `List` is empty.
|
|
*
|
|
* @return
|
|
* True if empty.
|
|
*/
|
|
def isEmpty: Boolean = this == Nil
|
|
|
|
/** Gets the length of the `List`. This is a linear-time operation.
|
|
*
|
|
* @return
|
|
* The length of the `List`.
|
|
*/
|
|
def length: Int = {
|
|
@tailrec
|
|
def recur(n: Int, current: List[A]): Int =
|
|
current match {
|
|
case _ :: tail => recur(n + 1, tail)
|
|
case _ => n
|
|
}
|
|
recur(0, this)
|
|
}
|
|
|
|
/** Conses an instance to the beginning of the `List`, making it the new
|
|
* `head` and this `List` becomes the `tail`. This is a constant-time
|
|
* operation.
|
|
*
|
|
* @param x
|
|
* The new head to cons.
|
|
* @tparam B
|
|
* The type of the head.
|
|
* @return
|
|
* The new `List`.
|
|
*/
|
|
def ::[B >: A](x: B): List[B] =
|
|
new ::[B](x, this)
|
|
|
|
/** Conses an instance to the beginning of the `List` and returns a
|
|
* `NonEmptyList`. This is a constant-time operation.
|
|
*
|
|
* @param x
|
|
* The new head to cons.
|
|
* @tparam B
|
|
* The type of the head.
|
|
* @return
|
|
* A new `NonEmptyList`.
|
|
*/
|
|
def |:[B >: A](x: B): NonEmptyList[B] = NonEmptyList(x, this)
|
|
|
|
/** Folds the `List` starting from the end using a seed value and a custom
|
|
* function to perform the fold. This is a linear-time operation.
|
|
*
|
|
* @param z
|
|
* The seed value.
|
|
* @param f
|
|
* The custom folding function.
|
|
* @tparam B
|
|
* The type of the folded value.
|
|
* @return
|
|
* The result of the fold.
|
|
*/
|
|
def foldRight[B](z: B)(f: (A, B) => B): B = reverse.foldLeft(z)((acc, head) => f(head, acc))
|
|
|
|
/** Folds the `List` starting from the beginning using a seed value and a
|
|
* custom function to perform the fold. This is a linear-time operation.
|
|
*
|
|
* @param z
|
|
* The seed value.
|
|
* @param f
|
|
* The custom folding function.
|
|
* @tparam B
|
|
* The type of the folded value.
|
|
* @return
|
|
* The result of the fold.
|
|
*/
|
|
def foldLeft[B](z: B)(f: (B, A) => B): B = {
|
|
@tailrec
|
|
def recur(acc: B, current: List[A]): B =
|
|
current match {
|
|
case head :: tail => recur(f(acc, head), tail)
|
|
case _ => acc
|
|
}
|
|
recur(z, this)
|
|
}
|
|
|
|
/** Reverses the order of instances in the `List`.
|
|
*
|
|
* @return
|
|
* The reversed `List`.
|
|
*/
|
|
def reverse: List[A] = foldLeft(List[A]())((tail, head) => head :: tail)
|
|
|
|
/** Zips this `List` with another `List`, creating a new `List` of pairs of
|
|
* instances from the first two `List`s. The new `List` will be as long as
|
|
* the shortest `List`.
|
|
*
|
|
* @param other
|
|
* The right-hand `List` to zip with.
|
|
* @tparam B
|
|
* The type of the instances held by the right-hand `List`.
|
|
* @return
|
|
* A `List` containing pairs of instances from both `List`s.
|
|
*/
|
|
def zip[B](other: List[B]): List[(A, B)] = {
|
|
@tailrec
|
|
def recur(acc: List[(A, B)], left: List[A], right: List[B]): List[(A, B)] =
|
|
(left, right) match {
|
|
case (leftHead :: leftTail, rightHead :: rightTail) => recur((leftHead, rightHead) :: acc, leftTail, rightTail)
|
|
case _ => acc.reverse
|
|
}
|
|
recur(List(), this, other)
|
|
}
|
|
|
|
/** Converts the `List` into a Scala `Seq`.
|
|
*
|
|
* @return
|
|
* A new Scala `Seq`.
|
|
*/
|
|
def toSeq: Seq[A] = foldRight(Seq[A]())(_ +: _)
|
|
|
|
override def equals(obj: Any): Boolean = {
|
|
if (!obj.isInstanceOf[List[Any]]) {
|
|
return false
|
|
}
|
|
val other = obj.asInstanceOf[List[Any]]
|
|
if (this.length != other.length) {
|
|
return false
|
|
}
|
|
this.zip(other).foldLeft(true) { (equals, pair) =>
|
|
pair match {
|
|
case (left, right) => equals && left == right
|
|
}
|
|
}
|
|
}
|
|
|
|
override def hashCode(): Int = foldLeft(7)((hash, head) => 31 * hash + head.hashCode())
|
|
}
|
|
|
|
/** Encodes a present instance within the `List`. This is referred to as a
|
|
* "cons" (short for "construct" or "construction" of a head and tail) and is
|
|
* considered the desired case of a `List` as it contains at least one instance
|
|
* of the `List`'s term `A`.
|
|
*
|
|
* @param head
|
|
* The instance held by the cons.
|
|
* @param tail
|
|
* The rest of the `List`, which may be empty.
|
|
* @tparam A
|
|
* The type contained within the `List`.
|
|
*/
|
|
case class ::[+A](head: A, tail: List[A]) extends List[A]
|
|
|
|
/** Encodes an empty `List`. This is considered the undesired case of a `List`
|
|
* as it contains no instances of the `List`'s term `A`.
|
|
*/
|
|
case object Nil extends List[Nothing] {
|
|
|
|
def head: Nothing = throw new NoSuchElementException("Nil.head")
|
|
|
|
def tail: Nothing = throw new NoSuchElementException("Nil.tail")
|
|
}
|
|
|
|
object List {
|
|
|
|
/** A smart constructor that allows for creating a `List` using the following
|
|
* idiomatic syntax:
|
|
*
|
|
* {{{
|
|
* List(1, 2, 3, 4, ...) // creates a non-empty List of Int's
|
|
* List[Int]() // creates an empty List of Int's
|
|
* }}}
|
|
*
|
|
* @param as
|
|
* The instances to construct the `List` from.
|
|
* @tparam A
|
|
* The type contained within the `List`.
|
|
* @return
|
|
* The new `List`.
|
|
*/
|
|
def apply[A](as: A*): List[A] =
|
|
if (as.isEmpty) Nil
|
|
else as.head :: apply(as.tail: _*)
|
|
|
|
/** Allows for idiomatic pattern matching syntax:
|
|
*
|
|
* {{{
|
|
* list match {
|
|
* case List(a, b, c) => ???
|
|
* }
|
|
* }}}
|
|
*
|
|
* @param as
|
|
* The `List` to unapply.
|
|
* @tparam A
|
|
* The type contained within the `List`.
|
|
* @return
|
|
* A present `Seq` of instances contained in this `List`.
|
|
*/
|
|
def unapplySeq[A](as: List[A]): scala.Option[Seq[A]] = scala.Some(as.toSeq)
|
|
|
|
implicit val listApplicative: Applicative[List] = new Applicative[List] {
|
|
|
|
/** Lifts the pure value of a computation into the context. This is an
|
|
* abstracted constructor for the `Applicative` and concretely for contexts
|
|
* `Option` it is `Some`, and for `Either` it is `Right`. It always creates
|
|
* a new context in the desired case.
|
|
*
|
|
* @param a
|
|
* The value to lift.
|
|
* @tparam A
|
|
* The type of the value.
|
|
* @return
|
|
* A new context in the desired case.
|
|
*/
|
|
override def pure[A](a: A): List[A] = List(a)
|
|
|
|
/** Pronounced "apply", this function takes an applicative functor of the
|
|
* form `F[A => B]` and applies it to the functor `F[A]`, giving the result
|
|
* of `F[B]`.
|
|
*
|
|
* @param ff
|
|
* The applicative functor, or lifted function.
|
|
* @param fa
|
|
* The argument context, or lifted argument.
|
|
* @tparam A
|
|
* The type of the argument.
|
|
* @tparam B
|
|
* The type of the result.
|
|
* @return
|
|
* The lifted result.
|
|
*/
|
|
override def ap[A, B](ff: List[A => B])(fa: List[A]): List[B] =
|
|
ff.foldLeft(List[B]()) { (outerResult, f) =>
|
|
fa.foldLeft(outerResult) { (innerResult, a) =>
|
|
f(a) :: innerResult
|
|
}
|
|
}.reverse
|
|
}
|
|
}
|