/*

	Semigroup: nonempty set with an associaive binary operation
	           trait Semigroup[A] {
		         def add(x:A, y:A):A
		       }

	Monoid: sets equipped with a special element and a binary operator, so that
	        the special element acts as an identity for the binary operator,
	        and the binary operator is associative

			trait Monoid[A] {
		      def add(x:A, y:A):A
		      def unit:A
		    }
*/

trait FoldLeft[F[_]] {
	def foldLeft[A,B](xs: F[A], b:B, f: (B,A)=>B):B
}

object FoldLeft {
	implicit object FoldLeftList extends FoldLeft[List]{
		def foldLeft[A,B](xs:List[A], b:B, f: (B,A)=>B) = xs.foldLeft(b)(f)
	}
}

trait Monoid[A] {
	def mappend(a:A, b:A):A
	def mzero:A
}

object Monoid {

	implicit object StringMonoid extends Monoid[String] {
		def mappend(a:String, b:String):String = a + b
		def mzero:String = ""
	}

	implicit object IntMonoid extends Monoid[Int] {
		def mappend(a: Int, b: Int): Int = a + b
		def mzero:Int = 0
	}
}

import Monoid._
import FoldLeft._

object Main {

	// this sum function take a list of ints then applies the foldleft function
	// with the higher-order function that adds one item to the next
	def sum(xs: List[Int]): Int = xs.foldLeft(0) { (a,b) => a + b }

	def sumWithIntMonoid(xs: List[Int]):Int = xs.foldLeft(IntMonoid.mzero) { (a,b) => IntMonoid.mappend(a,b) }

	def sumWithAbstractMonoid[T](xs:List[T], m:Monoid[T]):T = xs.foldLeft(m.mzero) { (a,b) => m.mappend(a,b) }

	def sumWithAbstractMonoidImplicit[T](xs:List[T])(implicit m:Monoid[T]):T = xs.foldLeft(m.mzero) { (a,b) => m.mappend(a,b) }

	def sumUsingFoldLeftList[T](xs:List[T])(implicit m:Monoid[T]):T = FoldLeftList.foldLeft(xs, m.mzero, m.mappend)

	def sumWithAbstractFoldLeft[M[_], T](xs:M[T])(implicit m:Monoid[T], fl:FoldLeft[M]):T = fl.foldLeft(xs, m.mzero, m.mappend)

}