slouc

* `Foldable` folds things that form a `Monoid`; `fold` needs an identity and a binary op, and `Monoid` has both.
* `Reducible` reduces things that form a `Semigroup`; `reduce` only needs the binary op.
* Collections that can be empty (e.g. `List`) are `Foldable`. `fold` deals with emptiness by requiring an identity element.
* Collections that cannot be empty (e.g. `NonEmptyList`) are not only `Foldable`, but also `Reducible`. `reduce` is not good at dealing with emptiness (standard Scala's `reduce` blows up), but with non-empty collections that's not a problem.

Note: Folding a non-empty collection of elements that form a `Monoid` will use the `head` of collection as a starting element, and not `Monoid`'s identity.

slouc

import cats._
import cats.implicits._

def foo1[A, B: Semigroup, F[_]: Traverse: Reducible, G[_]: Applicative](
  fa: F[A],
  fun: A => G[B]
): G[B] =
  Traverse[F].traverse(fa)(fun).map(Reducible[F].reduce[B])

// foo2 doesn't need F to be Traverse, but needs G to be FlatMap

slouc

import cats.Functor // scalaz would work as well

// Non recursive data structure
sealed trait ExpressionF[A]

case class ValueF[A](v: Int) extends ExpressionF[A]
case class AddF[A](e1: A, e2: A) extends ExpressionF[A]
case class MultF[A](e1: A, e2: A) extends ExpressionF[A]

// Functor instance for it

slouc

import scalaz._
import Scalaz._
import scalaz.{Applicative, \/}

def selectA[F[_]: Applicative, A, B](s: F[A \/ B])(f: => F[A => B]): F[B] =
  (s |@| f)(_.leftMap(_).merge)

def selectM[F[_]: Monad, A, B](s: F[A \/ B])(f: => F[A => B]): F[B] =
  s flatMap {
    case -\/(a) => f.map(_(a))

slouc

import cats._

abstract class Yoneda[F[_]: Functor, A] { self =>

  def apply[B](f: A => B): F[B]

  def run: F[A] = apply(identity)

  def map[B](f: A => B): Yoneda[F, B] = new Yoneda[F, B] {
    def apply[C](g: B => C): F[C] = self.apply(f andThen g)

slouc

// add scalacOptions += "-Ypartial-unification" to build.sbt

import scala.reflect.runtime._, universe._
import scala.language.higherKinds

def checkUnification[F[_], A: TypeTag](fa: => F[A]) = s"${typeOf[A]}"

assert(checkUnification(e) == "String")
assert(checkUnification(f) == "List[Int]")

slouc

import cats._
import cats.implicits._

// F[A] can fold A if F is a Foldable and A is a Monoid
def folding[F[_]: Foldable, A: Monoid](fa: F[A]): A =
  implicitly[Foldable[F]].fold(fa)

// Option[A] is a Monoid if A is a Semigroup
def foldingOption[A: Semigroup](a: A): Option[A] =
  folding(List(Option(a))) // List is Foldable

slouc

case class Money(amount: Int)

// contramap: B => A => F[A] => F[B]
val contramapFn: Money => Int = (money) => money.amount
implicit val moneyOrd: Ordering[Money] = Ordering.by(contramapFn)

import scala.math.Ordered._
println(Money(13) < Money(20)) // true

slouc

def Y[A](func: (A => A) => (A => A)): (A => A) =
  func(Y(func))(_)

def factorial: Int => Int =
  Y {
    (f: Int => Int) =>
      (n: Int) =>
        if (n <= 0) 1 else n * f(n - 1)
  }

slouc

import scalaz.Monad
import scalaz._

sealed trait Free[F[_], A] {

  def pure(a: A): Free[F, A] = Free.Pure(a)

  def lift(f: F[A]): Free[F, A] = Free.Suspend(f)

  def flatMap[B](f: A => F[B]): Free[F, B] = Free.Bind[F, A, B](this, f)