monoids.scala

import scala.util.matching._

trait Monoid[A] {
  def op(a1: A, a2: A): A
  def zero: A

  def productMonoid[A,B](a: Monoid[A], b: Monoid[B]): Monoid[(A,B)] =
    new Monoid[(A, B)] {
      override def op(a1: (A, B), a2: (A, B)): (A, B) = (a.op(a1._1, a2._1), b.op(a1._2, a2._2))
      override def zero: (A, B) = (a.zero, b.zero)
    }
}
sealed trait WC
case class Stub(chars: String) extends WC
case class Part(lStub: String, words: Int, rStub: String) extends WC

object Monoid {
  sealed trait Ordered
  case class Range(a: Int, b: Int) extends Ordered
  case object Unordered extends Ordered
  case object Mempty extends Ordered

  def orderungMonoid: Monoid[Ordered] = new Monoid[Ordered] {
    def zero: Ordered = Mempty
    def op(a: Ordered, b: Ordered): Ordered = (a, b) match {
      case (Range(la, ha), Range(lb, hb)) if ha <= lb => Range(la, hb)
      case (Mempty, i) => i
      case (i, Mempty) => i
      case _ => Unordered
    }
  }

  def isOrdered(v: IndexedSeq[Int]): Boolean = {
    foldMapV(v, orderungMonoid)(a => Range(a, a)) match {
      case Unordered => false
      case _ => true
    }
  }

  def concatenate[A](as: List[A], m: Monoid[A]): A =
    foldMap(as, m)(a => a)

  def foldMap[A,B](as: List[A], m: Monoid[B])(f: A => B): B =
    as.foldLeft(m.zero)((b, a) => m.op(b, f(a)))

  def foldLeft[A, B](as: List[A], z: B)(op: (B, A) => B): B = {
    foldMap(as, Monoids.endoMonoid[B])(a => b => op(b, a))(z)
  }

  def foldMapV[A,B](v: IndexedSeq[A], m: Monoid[B])(f: A => B): B = {
    if (v.isEmpty) {
      return m.zero
    }
    if (v.length == 1) {
      return f(v.head)
    }
    val (a, b) = v.splitAt(v.length / 2)
    m.op(foldMapV(a, m)(f), foldMapV(b, m)(f))
  }

  def countWords(s: String): Int = {
    val words = new Regex("\\w+")

    def foldMapWc(s: String): WC = {
      if (s.length < 3) {
        val matches = words.findAllMatchIn(s).toArray
        var wordsCount = matches.length

        val lStub = if (matches.head.start == 0) {
          wordsCount -= 1
          matches.head.toString()
        } else {
          ""
        }

        val rStub = if (matches.last.end == s.length) {
          wordsCount -= 1
          matches.last.toString()
        } else {
          ""
        }

        Part(lStub, wordsCount, rStub)
      } else {
        val (a, b) = s.splitAt(s.length / 2)
        Monoids.wcMonoid.op(foldMapWc(a), foldMapWc(b))
      }
    }

    val monoid = foldMapWc(s)

    monoid match {
      case Stub(x) if words.matches(x) => 1
      case Part(lStub, count, rStub) =>
        val lWords = if (words.matches(lStub)) 1 else 0
        val rWords = if (words.matches(rStub)) 1 else 0
        lWords + count + rWords
    }
  }



  def functionMonoid[A,B](m: Monoid[B]): Monoid[A => B] =
    new Monoid[A => B] {
      override def op(a1: A => B, a2: A => B): A => B = a => m.op(a1(a), a2(a))
      override def zero: A => B = _ => m.zero
    }

  def mapMergeMonoid[K,V](V: Monoid[V]): Monoid[Map[K, V]] =
    new Monoid[Map[K, V]] {
      def zero = Map[K,V]()
      def op(a: Map[K, V], b: Map[K, V]) =
        (a.keySet ++ b.keySet).foldLeft(zero) { (acc,k) =>
          acc.updated(k, V.op(a.getOrElse(k, V.zero),
            b.getOrElse(k, V.zero)))
        }
    }

  def bag[A](as: IndexedSeq[A]): Map[A, Int] = {
    val mapMonoid = mapMergeMonoid[A, Int](Monoids.intAddition)
    Monoid.foldMapV(as, mapMonoid)(x => Map((x, 1)))
  }
}

object Monoids {
  val stringMonoid: Monoid[String] = new Monoid[String] {
    override def op(a1: String, a2: String): String = a1 + a2
    val zero = ""
  }

  val andMonoid: Monoid[Boolean] = new Monoid[Boolean] {
    override def op(a1: Boolean, a2: Boolean): Boolean = a1 && a2
    val zero = true
  }

  val intAddition: Monoid[Int] = new Monoid[Int] {
    override def op(a1: Int, a2: Int): Int = a1 + a2
    val zero = 0
  }

  val intMultiplication: Monoid[Int] = new Monoid[Int] {
    override def op(a1: Int, a2: Int): Int = a1 * a2
    val zero = 1
  }

  def optionMonoid[A]: Monoid[Option[A]] =
    new Monoid[Option[A]] {
      override def op(a1: Option[A], a2: Option[A]): Option[A] = a1.orElse(a2)
      override def zero: Option[A] = None
    }

  def endoMonoid[A]: Monoid[A => A] =
    new Monoid[A => A] {
      override def op(a1: A => A, a2: A => A): A => A = a => a1(a2(a))
      override def zero: A => A = a => a
    }

  val wcMonoid: Monoid[WC] = new Monoid[WC] {
    override def op(a1: WC, a2: WC): WC = (a1, a2) match {
      case (Stub(x), Stub(y)) => Stub(x + y)
      case (Stub(x), Part(lStub, words, rStub)) => Part(x + lStub, words, rStub)
      case (Part(lStub, words, rStub), Stub(x)) => Part(lStub, words, rStub + x)
      case (Part(lStub1, words1, rStub1), Part(lStub2, words2, rStub2)) => {
        val regex = new Regex("\\w+")
        val stubWords = if (regex.matches(rStub1) || regex.matches(lStub2)) 1 else 0
        Part(lStub1, words1 + words2 + stubWords, rStub2)
      }
    }
    override def zero: WC = Stub("")
  }
}

trait Foldable[F[_]] {
  def foldLeft[A,B](as: F[A])(z: B)(f: (B,A) => B): B
  def foldMap[A,B](as: F[A])(f: A => B)(mb: Monoid[B]): B = foldLeft(as)(mb.zero)((b, a) => mb.op(b, f(a)))
  def concatenate[A](as: F[A])(m: Monoid[A]): A =
    foldLeft(as)(m.zero)(m.op)

  def toList[A](fa: F[A]): List[A] =
    foldLeft(fa)(List(): List[A])(_ :+ _)
}

object Foo {
  sealed trait List[+A]
  case object Nil extends List[Nothing]
  case class Cons[+A](head: A, tail: List[A]) extends List[A]

  sealed trait Tree[+A]
  case class Leaf[A](value: A) extends Tree[A]
  case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

  implicit val foldableList = new Foldable[List] {
    def foldLeft[A,B](as: List[A])(z: B)(f: (B,A) => B): B =
      as match {
        case Nil => z
        case Cons(x, xs) => foldLeft(xs)(f(z, x))(f)
      }
  }

  implicit val foldableIndexedSeq = new Foldable[IndexedSeq] {
    def foldLeft[A,B](as: IndexedSeq[A])(z: B)(f: (B,A) => B): B =
      as.headOption match {
        case None => z
        case Some(x) => foldLeft(as.tail)(f(z, x))(f)
      }
  }

  implicit val streamIndexedSeq = new Foldable[LazyList] {
    def foldLeft[A,B](as: LazyList[A])(z: B)(f: (B,A) => B): B =
      (as.headOption, as.tail) match {
        case (None, _) => z
        case (Some(x), xs) => foldLeft(xs)(f(z, x))(f)
      }
  }

  implicit val foldableTree = new Foldable[Tree] {
    def foldLeft[A,B](as: Tree[A])(z: B)(f: (B,A) => B): B =
      as match {
        case Leaf(a) => f(z, a)
        case Branch(xs, ys) => foldLeft(xs)(foldLeft(ys)(z)(f))(f)
      }
  }

  implicit val foldableOption = new Foldable[Option] {
    def foldLeft[A,B](as: Option[A])(z: B)(f: (B,A) => B): B =
      as match {
        case None => z
        case Some(x) => f(z, x)
      }
  }
}

object Main extends App {
  println(Monoids.stringMonoid.op("Hello", "World"))
  println(Monoids.intAddition.op(1, 2))
  println(Monoids.optionMonoid.op(Some(10), Monoids.optionMonoid.zero))
  println(Monoids.optionMonoid.op(Monoids.optionMonoid.zero, Some(10)))
  println(Monoids.optionMonoid.op(Monoids.optionMonoid.zero, None))
  println(Monoid.isOrdered(IndexedSeq(1,2,3)))
  println(Monoid.isOrdered(IndexedSeq(1,3,2)))
  println(Monoids.wcMonoid.op(Part("he", 1, "he"), Part("llo", 1, "")))
  println(Monoids.wcMonoid.op(Part("he", 1, ""), Part(" ", 1, "")))
  println(Monoid.countWords("hello world kitty"))

  println(Foo.foldableIndexedSeq.toList(IndexedSeq(1,2,3)))
  println(Monoid.bag(Vector("a", "rose", "is", "a", "rose")))
}