FoldableHMW.scala

package lesson7

import cats.{Endo, Monoid, MonoidK}
import cats.instances.function._
import cats.syntax.monoid._
import lesson7.Foldable._
import cats.syntax.option._

trait Foldable[F[_]] {

  // p.1
  def foldMap[A, B : Monoid](fa: F[A])(f: A => B): B =
    foldr(fa)(Monoid[B].empty)((a, b) => f(a) |+| b)

  def foldr[A, B](fa: F[A])(z: B)(f: (A, B) => B): B =
    foldMap(fa)(a => (b: B) => f(a, b)).apply(z)

  def foldl[A, B](fa: F[A])(z: B)(f: (B, A) => B): B =
    foldMap(fa)(a => Dual((b: B) => f(b, a))).unwrap(z)

  def foldr1[A, B](fa: F[A])(z: B)(f: (A, B) => B): B =
    foldl(fa)((b: B) => b)((g, a) => b => g(f(a, b)))(z)

  def foldl1[A, B](fa: F[A])(z: B)(f: (B, A) => B): B =
    foldr(fa)((b: B) => b)((a, g) => b => g(f(b, a)))(z)

  // p.2
  def headOption[A](fa: F[A]): Option[A] = foldr(fa)(none[A])((a, _) => a.some)
  def lastOption[A](fa: F[A]): Option[A] = foldl(fa)(none[A])((_, a) => a.some)
  def length[A](fa: F[A]): Int = foldr(fa)(0)((_, b) => b + 1)
  def exists[A](fa: F[A])(p: A => Boolean): Boolean = foldr(fa)(false)((a, b) => p(a) || b)
  def forall[A](fa: F[A])(p: A => Boolean): Boolean = foldr(fa)(true)((a, b) => p(a) && b)

  // p.3
  def foldrN[A, B](fa: F[A])(n: Int)(z: B)(f: (A, B) => B): B =
    foldr(fa)((_: Int, v: B) => v) { (a, g) =>
      { (i, v) =>
        if (i <= 0) v else g(i - 1, f(a, v))
      }
    }(n, z)

  // p.4
  def foldr2[A, B](fa: F[A])(z: B)(f: (A, => B) => B): B =
    foldr(fa)(z)(f(_, _))

  def foldr2N[A, B](fa: F[A])(n: Int)(z: B)(f: (A, B) => B): B =
    foldr2(fa)((_: Int, v: B) => v) { (a, g) =>
      { (i, v) =>
        if (i <= 0) v else g(i - 1, f(a, v))
      }
    }(n, z)
}

object Foldable {

  case class Dual[A](unwrap: A)

  object Dual {
    implicit def catsMonoidForDual[A : Monoid]: Monoid[Dual[A]] = new Monoid[Dual[A]] {
      def empty: Dual[A] = Dual(Monoid[A].empty)
      def combine(x: Dual[A], y: Dual[A]): Dual[A] = Dual(y.unwrap |+| x.unwrap)
    }
  }

  implicit def catsMonoidForEndo[A]: Monoid[Endo[A]] = MonoidK[Endo].algebra[A]

  implicit val foldableForList: Foldable[List] = new Foldable[List] {
    override def foldMap[A, B: Monoid](fa: List[A])(f: A => B): B =
      fa.foldRight(Monoid[B].empty)((a, b) => f(a) |+| b)
  }

  implicit val foldableForStream: Foldable[Stream] = new Foldable[Stream] {
    override def foldr2[A, B](fa: Stream[A])(z: B)(f: (A, => B) => B): B =
      if (fa.isEmpty) z else f(fa.head, foldr2(fa.tail)(z)(f))
  }
}

object Application extends App {

  val lst = List(1,2,4)

  println("foldr " + foldableForList.foldr(lst)("Z")(_ + _))
  println("foldl " + foldableForList.foldl(lst)("Z")(_ + _))
  println("foldr1 " + foldableForList.foldr1(lst)("Z")(_ + _))
  println("foldl1 " + foldableForList.foldl1(lst)("Z")(_ + _))

  println("headOption " + foldableForList.headOption(lst))
  println("headOptionEmpty " + foldableForList.headOption(Nil))
  println("lastOption " + foldableForList.lastOption(lst))
  println("lastOptionEmpty " + foldableForList.lastOption(Nil))
  println("length " + foldableForList.length(lst))
  println("lengthEmpty " + foldableForList.length(Nil))
  println("exist T " + foldableForList.exists(lst)(_ == 2))
  println("exist F " + foldableForList.exists(lst)(_ == 3))
  println("existEmpty " + foldableForList.exists(Nil)(_ == 1))
  println("forall T " + foldableForList.forall(lst)(_ != 3))
  println("forall F " + foldableForList.forall(lst)(_ == 3))
  println("forallEmpty " + foldableForList.forall(Nil)(_ == 1))

  println("foldrN " + foldableForList.foldrN(lst)(2)(0)(_ + _))

  println("foldr2N " + foldableForStream.foldr2N(Stream.from(1))(1000)(0)(_ + _))
}