functional.scala

import scala.annotation.tailrec

sealed trait Option[+U] {
  def foldLeft[B](z: B)(f: (B, U) => B): B
  def map[V](f: U => V): Option[V]
  def flatMap[V](f: U => Option[V]): Option[V]
}

final case object None extends Option[Nothing] {
  override def foldLeft[B](z: B)(f: (B, Nothing) => B): B     = z
  override def map[V](f: Nothing => V): Option[V]             = None
  override def flatMap[V](f: Nothing => Option[V]): Option[V] = None
}

final case class Some[+U](v: U) extends Option[U] {
  override def foldLeft[B](z: B)(f: (B, U) => B): B     = f(z, v)
  override def map[V](f: U => V): Option[V]             = Some(f(v))
  override def flatMap[V](f: U => Option[V]): Option[V] = f(v)
}

sealed trait List[+U] {
  @tailrec
  def foldLeft[B](z: B)(f: (B, U) => B): B = this match {
    case Nil              => z
    case Cons(head, tail) => tail.foldLeft(f(z, head))(f)
  }
  def reverse: List[U]
  def map[V](f: U => V): List[V]
  def flatMap[V](f: U => List[V]): List[V]
}

final case object Nil extends List[Nothing] {
  override def reverse: List[Nothing]                     = Nil
  override def map[V](f: Nothing => V): List[V]           = Nil
  override def flatMap[V](f: Nothing => List[V]): List[V] = Nil
}

final case class Cons[+U](head: U, tail: List[U]) extends List[U] {
  override def reverse: List[U]           = foldLeft(Nil: List[U])((left, i) => Cons(i, left))
  override def map[V](f: U => V): List[V] = foldLeft(Nil: List[V])((left, i) => Cons(f(i), left)).reverse
  override def flatMap[V](f: U => List[V]): List[V] =
    map(f).foldLeft(Nil: List[V])((left, l1) => l1.foldLeft(left.reverse)((l2, i2) => Cons(i2, l2))).reverse
}

trait Try[+U] {
  def foldLeft[B](z: B)(f: (B, U) => B): B
  def map[V](f: U => V): Try[V]
  def flatMap[V](f: U => Try[V]): Try[V]
}

final case class Failure(e: Throwable) extends Try[Nothing] {
  override def foldLeft[B](z: B)(f: (B, Nothing) => B): B = z
  override def map[V](f: Nothing => V): Try[V]            = Failure(e)
  override def flatMap[V](f: Nothing => Try[V]): Try[V]   = Failure(e)
}

final case class Success[+U](v: U) extends Try[U] {
  override def foldLeft[B](z: B)(f: (B, U) => B): B = f(z, v)
  override def map[V](f: U => V): Try[V]            = Success(f(v))
  override def flatMap[V](f: U => Try[V]): Try[V]   = f(v)
}

object Try {
  def apply[U](f: () => U): Try[U] = try { Success(f()) } catch { case e: Throwable => Failure(e) }
}