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

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