typeclassopedia.scala

package foo

import scala.language.higherKinds

trait Semigroup[M] extends Any {
  def mAppend(x: M, y: M): M
}

trait Monoid[M] extends Semigroup[M] {
  def zero: M
}


/** The Functor type class is used for types that can be mapped over. Instances of
  * Functor should satisfy the following laws:
  *
  * - identity law: `map(id) === id`
  * - composition law: `map(f andThen g) === map(f) andThen map(g)`
  *
  * @tparam F an instance
  * @author Carlo Micieli
  * @since 0.1
  */
trait Functor[F[_]] extends Any {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

/** Class of data structures that can be folded to a summary value.
  * @author Carlo Micieli
  * @since 0.1
  */
trait Foldable[T[_]] extends Any {

  /** Combine the elements of a structure using a monoid.
    */
  def fold[M](tm: T[M])(implicit m: Monoid[M]): M

  /** Map each element of the structure to a monoid, and combine the results.
    */
  def foldMap[M: Monoid, A](fa: T[A])(f: A => M): M

  /** Right-associative fold of a structure.
    */
  def foldRight[A, B](fa: T[A])(b: B)(f: (A, B) => B): B

  /** List of elements of a structure, from left to right.
    */
  def toList[A](ta: T[A]): List[A]
}

/** Class of data structures that can be traversed from left to right, performing an
  * action on each element.
  * @author Carlo Micieli
  * @since 0.1
  */
trait Traversable[T[_]] extends Functor[T] with Foldable[T] {
  /** Map each element of a structure to an action, evaluate these actions from left
    * to right, and collect the results. For a version that ignores the results
    * see [[traverse]].
    */
  def traverse[F[_]: Applicative, A, B](ta: T[A])(f: A => F[B]): F[T[B]]
}

trait Applicative[F[_]] extends Functor[F] {
  /** Abstracts over constructors, providing a way to create
    * a new context from a plain value.
    * @param a the value to wrap in a monadic context
    * @return a new context
    */
  def pure[A](a: A): F[A]
}

/** A '''monad''' is a mechanism for ''sequencing computations''.
  *
  * The monadic behavior is formally captured in two operations:
  * - `pure`: `A => F[A]`
  * - `flatMap`: `(F[A], A) => F[B]`
  *
  * `pure` provides a way to create a new monadic context from a plain value,
  * `flatMap` provides the sequencing step.
  *
  * A lawful Monad instance must obey a set of laws.
  * - left identity: `pure(a).flatMap(f) === f(a)`
  * - right identity: `m.flatMap(pure) === m`
  * - associavitity: `m.flatMap(f).flatMap(g) === m.flatMap(x => f(x).flatMap(g))`
  */
trait Monad[F[_]] extends Applicative[F] {
  /** Provides a sequencing step, extracting the value from a
    * context and generating the next context in the sequence.
    *
    * @param fa a monadic context
    * @param f a function to generate the next context
    * @return a new monadic context
    */
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

  /**
    *
    */
  def map[A, B](fa: F[A])(f: A => B): F[B] = {
    flatMap(fa)(a => pure(f(a)))
  }
}
/*
type Id[A] = A

object Identity extends Monad[Id] {
  def pure[A](a: A): Id[A] = a
  def flatMap[A, B](fa: Id[A])(f: A => Id[B]): Id[B] = f(fa)
}
*/