You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
303 lines
8.8 KiB
303 lines
8.8 KiB
package green.thisfieldwas.embracingnondeterminism.data




import green.thisfieldwas.embracingnondeterminism.control.Monad




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 nonzero 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 singlylinked list.


*


* @tparam A


* The type contained within the `List`.


*/


sealed trait List[+A] {




/** The first instance in the `List`, if the list is nonempty.


*


* @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 lineartime 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 constanttime


* 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 constanttime 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 lineartime 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 lineartime 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 righthand `List` to zip with.


* @tparam B


* The type of the instances held by the righthand `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 nonempty 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 listMonad: Monad[List] = new Monad[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




/** Flattens a nested context.


*


* Based on the states of the contexts, a few things may happen:


* 1. If the outer context is in the undesired case, then a flattened


* context in the undesired case is produced.


* 1. If the inner context is in the undesired case, then a flattened


* context in the undesired case is produced. 3. If both contexts are


* in the desired case, then a flattened context in the desired case


* is produced.


*


* @param ffa


* The nested context.


* @tparam A


* The term contained by the inner context.


* @return


* A flattened context containing term `A`.


*/


override def flatten[A](ffa: List[List[A]]): List[A] =


ffa


.foldLeft(List[A]()) { (outerResult, as) =>


as.foldLeft(outerResult) { (innerResult, a) =>


a :: innerResult


}


}


.reverse


}


}


