globulon

  sealed trait Tree[+A]
  final case class Node[A](a: A, left: Tree[A] = Leaf, right: Tree[A] = Leaf) extends Tree[A]
  case object Leaf extends Tree[Nothing]

  implicit object traversableTree extends Traverse[Tree] {
    def cons[T](v: T, l: Tree[T], r: Tree[T]): Tree[T] = Node(v, l, r)

    def traverse[M[_], T, U](source: Tree[T])(f: (T) ⇒ M[U])(implicit applicative: Applicative[M]): M[Tree[U]] = {
      source match {
        case Leaf ⇒ applicative(Leaf)

globulon

    println(traversableList.sequence(List[Option[Int]](Some(1), Some(2), Some(3))))
    println(traversableList.sequence(List[Option[Int]](Some(1), None, Some(3))))
    println(traversableTree.sequence(Node[Option[Int]](Some(5), Node(Some(3), Leaf, Node(Some(2))))))
    println(traversableTree.sequence(Node[Option[Int]](Some(5), Node(Some(3), Leaf, Node(None)))))

/**
[info] Running com.promindis.user.TraversableExample
Some(List(1, 2, 3))
None
Some(Node(5,Node(3,Leaf,Node(2,Leaf,Leaf)),Leaf))

globulon

trait Monoid[T] {
  def add(x: T, y: T): T

  def unit: T
}

globulon

  def toAccumulator[X, U](x: X, f: (X) ⇒ U, monoid: Monoid[U]) = State[X,U]((s: U) ⇒ (x, monoid.add(f(x), s)))

  def accumulate[A, T[_], U](source: T[A])(f: (A) ⇒ U)(implicit t: Traverse[T], monoid: Monoid[U]): State[T[A], U] = {
    type Projection[X] = State[X, U]
    implicit val A = stateApplicative[U]()
    t.traverse[Projection, A, A](source)((x: A) ⇒ toAccumulator(x, f, monoid))
  }

globulon

  implicit def stateApplicative[S]() = new Applicative[({type λ[α] = State[α,S]})#λ] {
    def map[T, P >: T, U](source: State[T, S])(f: P ⇒ U): State[U, S] = new State[U, S]((s: S) ⇒ {
      val (value, state) = source(s)
      (f(value), state)
    })

    def apply[T](data: T) = new State((s: S) ⇒ (data, s))

    def flatten[T](m: State[State[T, S], S]): State[T, S] = new State[T, S]((s: S) ⇒ {
      val (mp, sp) = m(s)

globulon

  object Any extends Monoid[Boolean] {
    def add(x: Boolean, y: Boolean) = x || y

    def unit = false
  }


val aTree: Tree[Int] = Node(5, Node(3, Node(1), Node(6)), Node(9, Node(8), Node(10)))
val result = accumulate(aTree)((x: Int) ⇒ (x > 8))(traversableTree, Any)
println(result(Any.unit)._2)

globulon

  implicit def toListMonoid[A] = new Monoid[List[A]] {
    def add(x: List[A], y: List[A]) = x ++ y

    def unit = List[A]()
  }

val result2 = accumulate(aTree)((x: Int) ⇒ if (x > 8) List(x) else Nil)
println(result2(toListMonoid.unit)._2)

//Produces List(9, 10)

globulon

  def reduce[A, T[_]](source: T[A])(implicit t: Traverse[T], monoid: Monoid[A])=
    accumulate(source)(identity).apply(monoid.unit)

  implicit object StringMonoid extends Monoid[String] {
    override def add(x: String, y: String) = x + y
    override def unit = ""
  }

 println(reduce(List("Thumper", "is", "a", "cute", "rabbit")))

globulon

  def toCollector[A, B, U](x: A, f: (A) ⇒ B, g: U ⇒ U) = State[B,U]((s: U) ⇒ (f(x), g(s)))

  def collect[A, B, T[_], U](source: T[A])(f: (A) ⇒ B, g: U ⇒ U)(implicit t: Traverse[T]): State[T[B], U] = {
    type Projection[X] = State[X, U]
    implicit val A = stateApplicative[U]()
    t.traverse[Projection, A, B](source)((x: A) ⇒ toCollector(x, f, g))
  }


 println((collect(List(10, 20, 30, 40))((a: Int) ⇒ 2 * a, (i: Int) ⇒ i + 1)).apply(0))

globulon

 def foldLeft[B](z: B)(l: Seq[A])(f: (B, A) => B): B