embracing-nondeterminism-code/src/main/scala/green/thisfieldwas/embracingnondeterminism/data/List.scala

259 lines
7.4 KiB
Scala

package green.thisfieldwas.embracingnondeterminism.data
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 listFunctor: Functor[List] = new Functor[List] {
/** Given a structure `F[A]` and function `f: A => B`, if the structure is
* in the desired case, then apply the function such that `F[A] => F[B]`.
* If the structure `F[A]` is in the undesired case, then propagate the
* undesired case as `F[B]`.
*
* @param fa
* The instance of the structure to apply the function to.
* @param f
* The function to apply, if the structure is in the desired case.
* @tparam A
* The type of instances contained within the structure.
* @tparam B
* The type to map the instances into.
* @return
* The resulting structure.
*/
override def map[A, B](fa: List[A])(f: A => B): List[B] =
fa.foldLeft(List[B]())((fb, a) => f(a) :: fb).reverse
}
}