gistfile1.scala

import scalaz._

// A right Kan extension of `F` along itself, constrained by `C`.
trait RCodensity[C[_], F[_], A] {
  def apply[R:C](k: A => F[R]): F[R]
}

object RCodensity {
  implicit def codensityMonad[C[_], F[_]]: Monad[({type f[x] = RCodensity[C,F,x]})#f] =
      new Monad[({type f[x] = RCodensity[C,F,x]})#f] {
        def point[A](a: => A) = new RCodensity[C,F,A] {
          def apply[R:C](k: A => F[R]) = k(a)
        }
        def bind[A,B](ma: RCodensity[C,F,A])(f: A => RCodensity[C,F,B]) = 
          new RCodensity[C,F,B] {
            def apply[R:C](k: B => F[R]) = ma(a => f(a)(k))
          }
      }
}

object SetMonad {
  // This is a monad for sets that require ordering
  type SetM[A] = RCodensity[Order, ISet, A]

  import scalaz.syntax.monad._

  def liftSet[A](s: ISet[A]): SetM[A] = new SetM[A] {
    def apply[R:Order](k: A => ISet[R]) =
      flatMap(s)(k)
  }

  def runSet[A:Order](s: SetM[A]): ISet[A] = s(ISet.singleton)

  def optimize[A:Order](s: SetM[A]): SetM[A] =
    liftSet(runSet(s))

  import scalaz.syntax.traverse._
  import scalaz.std.list._
  import scalaz.std.option._
  import scalaz.std.anyVal._

  def flatMap[A,B:Order](s: ISet[A])(f: A => ISet[B]): ISet[B] =
    s.foldLeft(ISet.empty[B])((bs, a) => bs union f(a))

  // Just to prove that this works
  Some(ISet.fromList(List(1, 2, 3)), ISet.fromList(List(4, 5, 6))).traverse(liftSet)
}