asdasd.scala

object Main {

  /*
   * First thing first, we turn on a ("advanced") language feature via
   * `import scala.language.higherKinds`
   *
   * This is so that we can express higher-kinded types (HKTs) in generic
   * parameters.  Comes in handy for `Functor`, as all functors are HKTs, and
   * also for `Fix`, for similar reasons.
   *
   * saying F[_] is like saying (f :: * -> *) in Haskell.
   * similarly, F[_, _] is like (f :: * -> * -> *), and so on.
   *
   * The crucial difference is in the way the type arguments are applied:
   * in Haskell, we can partially apply the arguments, which means that
   * Either :: * -> * -> *
   * Either String :: * -> *
   * Either String Int :: Int
   *
   * In scala, we can't. This means that given a F[_, _], we have no way of
   * turning that into something that looks like G[_].
   *
   * ^
   * This is not entirely true, there is in fact one way of doing that, but
   * it's incredibly ugly, and messes up type inference really badly.
   * The keyword to search for is "type lambdas (in scala)".
   *
   */
  import scala.language.higherKinds

  // Functor type class
  //
  // for some reason, the scala people didn't think it was a good idea to
  // put this type class into the core library.
  //
  // at least everyone can roll their own functor class, which are all
  // incompatible with one another... </rant>
  trait Functor[F[_]] {
    def fmap[A, B](ab: A => B)(fa: F[A]) : F[B]
  }

// Numbers /////////////////////////////////////////////////////////////////////

  /*
   * data Nat a
   *   = Zero
   *   | Succ a
   *   deriving (Functor)
   */
  sealed trait Nat[A]

  case class Zero[A]() extends Nat[A]
  case class Succ[A](n: A) extends Nat[A]

  // scala doesn't derive Functor, so we have to do this manually
  implicit def natFunctor = new Functor[Nat] {
    def fmap[A, B](ab : A => B)(fa: Nat[A]) : Nat[B] =
      fa match {
         case Zero()  => Zero()
         case Succ(n) => Succ(ab(n))
      }
  }

// Fix-point constructor ///////////////////////////////////////////////////////

  /*
   * data Fix (f :: * -> *) = Mu { unFix :: f (Fix f) }
   */
  case class Fix[F[_]](unFix: F[Fix[F]])

// Catamorphisms ///////////////////////////////////////////////////////////////

  /*
   * cata :: Functor f => (f a -> a) -> Fix f -> a
   * cata phi = phi . fmap (cata phi) . unFix
   */
  def cata[F[_], A](phi: F[A] => A)(fix : Fix[F])(implicit functor : Functor[F]) : A =
    phi(functor.fmap(cata(phi))(fix.unFix))

// An example //////////////////////////////////////////////////////////////////

  val natty : Fix[Nat] =
    Fix(Succ(Fix(Succ(Fix(Succ(Fix(Zero())))))))

  def natPhi(n: Nat[Int]) : Int =
    n match {
      case Zero() => 0
      case Succ(x) => x + 1
    }

  def main(args: Array[String]) =
    // prints 3
    println(cata(natPhi)(natty))
}

/*
 * In the Haskell version, we also have lists:
 *
 * data List h a
 *   = Empty
 *   | Cons h
 *          a
 *   deriving (Show, Functor)
 *
 * with the following example:
 *
 * xs' :: Fix (List Int)
 * xs' = Mu (Cons 1 (Mu (Cons 2 (Mu (Cons 3 (Mu Empty))))))
 *
 * Question 1: can we write this in scala as simply as we could Nat?
 * Question 2: why not? (hint: think about the limitations of multi-arg HKTs in scala)
 *
 */