types.scala

/*
 * Copyright 2014–2016 SlamData Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package matryoshka

import scala.{Boolean, Int, Option}
import matryoshka.Recursive.ops._
import matryoshka.data._
import monocle._
import scalaz._, Scalaz._

object ttypes {
  type ->[+A, +B] = (A, B)
  type PairOf[+A] = A -> A
  type SumOf[+A]  = A \/ A

  trait Interpret[T[_[_]]] {
    type ^[Outer[_], Inner[_]] = Outer[T[Inner]]

    trait Transform[F[_], G[_]] {
      type FTF = F[T[F]]
      type GTG = G[T[G]]

      /** Bottom-up transforms. */
      type GAlgebraicM[W[_], M[_]]   = F[W ^ G] => M[G ^ G]
      type AlgebraicM[M[_]]          = F   ^ G  => M[G ^ G] // GAlgebraicM[Id, M]
      type GAlgebraic[W[_]]          = F[W ^ G] =>   G ^ G  // GAlgebraicM[W, Id]
      type Algebraic                 = F   ^ G  =>   G ^ G  // GAlgebraicM[Id, Id]

      /** Top-down transforms. */
      type GCoalgebraicM[N[_], M[_]] = F ^ F => M[G[N ^ F]]
      type CoalgebraicM[M[_]]        = F ^ F => M[G   ^ F ]  // GCoalgebraicM[Id, M]
      type GCoalgebraic[N[_]]        = F ^ F =>   G[N ^ F]   // GCoalgebraicM[N, Id]
      type Coalgebraic               = F ^ F =>   G   ^ F    // GCoalgebraicM[Id, Id]
    }

    type GTransformM[W[_], M[_], F[_], G[_]] = GAlgebraicTransformM[T, W, M, F, G]
    type GTransform[W[_], F[_], G[_]]        = GAlgebraicTransform[T, W, F, G]

    def substitute[F[_]](original: T[F], replacement: T[F])(implicit T: Equal[T[F]]): T[F] => SumOf[T[F]] =
      find[F](_ ≟ original)(_).leftMap(_ => replacement)

    def find[F[_]](f: T[F] => Boolean): T[F] => SumOf[T[F]] =
      tf => if (f(tf)) tf.left else tf.right
  }

  trait RecursiveT[T[_[_]]] extends Interpret[T] {
    implicit def recursive: Recursive[T]

    def count[F[_]: Functor: Foldable](form: T[F]): GAlgebra[T[F] -> ?, F, Int] =
      e => e.foldRight(if (e ∘ (_._1) == form.project) 1 else 0)(_._2 + _)

    def distApo[F[_]: Functor]: DistributiveLaw[T[F] \/ ?, F] =
      distGApo(_.project)

    def zipTuple[F[_]: Functor: Zip]: Coalgebra[F, PairOf[T[F]]] =
      p => Zip[F].zip(p._1.project, p._2.project)

    def alignThese[F[_]: Align]: ElgotCoalgebra[T[F] \/ ?, F, T[F] \&/ T[F]] =
      _.fold(_.left, _.left, (a, b) => a.project.align(b.project).right)

    def mergeTuple[F[_]: Functor: Merge]: CoalgebraM[Option, F, PairOf[T[F]]] =
      p => Merge[F].merge(p._1.project, p._2.project)
  }

  trait CorecursiveT[T[_[_]]] extends Interpret[T] {
    implicit def corecursive: Corecursive[T]

    def distPara[F[_]: Functor]: DistributiveLaw[F, T[F] -> ?] =
      distZygo(_.embed)

    def attrSelf[F[_]: Functor]: Algebra[F, Cofree[F, T[F]]] =
      attributeAlgebra(_.embed)

    def transformToAlgebra[W[_], M[_]: Functor, F[_], G[_]: Functor](
      self: GTransformM[W, M, F, G]):
        GAlgebraM[W, M, F, T[G]] =
      self(_) ∘ (_.embed)
  }
  trait BirecursiveT[T[_[_]]] extends RecursiveT[T] with CorecursiveT[T] {
    def recCorecIso[F[_]: Functor]                                  = AlgebraIso[F, T[F]](_.embed)(_.project)
    def lambekIso[F[_]: Functor]                                    = AlgebraIso[F, T[F]](colambek)(lambek)
    def foldIso[F[_]: Functor, A](alg: AlgebraIso[F, A])            = Iso[T[F], A](_ cata alg.get)(_ ana alg.reverseGet)
    def foldPrism[F[_]: Traverse, A](alg: AlgebraPrism[F, A])       = Prism[T[F], A](recursive.cataM(_)(alg.getOption))(_ ana alg.reverseGet)
    def unfoldPrism[F[_]: Traverse, A](coalg: CoalgebraPrism[F, A]) = Prism[A, T[F]](_ anaM coalg.getOption)(_ cata coalg.reverseGet)
  }

  object FixT extends BirecursiveT[Fix] {
    implicit def recursive   = Fix.recursive
    implicit def corecursive = Fix.corecursive
  }
  object MuT extends BirecursiveT[Mu] {
    implicit def recursive   = Mu.recursive
    implicit def corecursive = Mu.corecursive
  }
  object NuT extends BirecursiveT[Nu] {
    implicit def recursive   = Nu.recursive
    implicit def corecursive = Nu.corecursive
  }
}