Generic programming & Rotten Bananas in Scala involving functional dependencies

Question

So just to contextualize this for the uninitiated (not necessarily excluding myself), functors are a grade A context/mapping abstraction. In Scalanese:

trait FunctorStr[F[_]] {
    def map[A, B](f: A => B): F[A] => F[B]
 }

lots of things are functors blah blah, now if you are interested in generic programming and DSL crafting as a design pattern functors come up a lot. So, in keeping with the theme of extending intuition, lets get down to it. Half way through comonad.com's Rotten Bananas we are introduced to class Cata

given in Haskellese:

class Cata f t | t -> f where
  cata:: (f a -> a) -> t -> a

now this Class is near the beginning of the fun for us the reader, but for me the scala implementer ... Cata is the beginning of our trouble

this functional dependency t -> f does it mean "f is uniquely determined by t" ? if you asked Miles Sabin in 2011 the fundep pattern is totally realizable in scala and put simply involves initiating an implicit search via an implicit parameter section and witnessing types to resolve the search but I can't say I get it so well as to instantly translate t -> f to scala

I'm seeing it in scala as something like

abstract class Cata[F[_], T](implicit e: ???) {
   def cata[A]: (F[A] => A) => T => A
}

trait CataFunctor[F[_]] extends FunctorStr[({type l[x] = Cata[F, x]})#l] {
   def map[A, B](f: A => B): Cata[F, A] => Cata[F, B]
}

Quoting the article:

given cata and fmap one can go through and build up a whole host of other recursion schemes, paramorphisms, zygomorphisms, histomorphisms, generalized catamorphisms, ...; the menagerie is quite forbidding and these can be used to tear apart covariant functors with reckless abandon. With the power of a paramorphism you rederive the notion of general recursion, and so you can basically write any recursive function you want. (On the coalgebra side of the house there are anamorphisms, apomorphisms, and all sorts of other beasts for effectively generating covariant functors)

This is the power I seek.

I'm trying to work this out and would really like some help? Now I've the InvariantFunctor Implemented in scalaz so I know that this isn't a fools errand.

Can I get a nudge in the right direction here? I'm down for as much detail as possible so like, go nuts.

Answer 1

Reading the linked post it looks like you need:

trait CataDep[T, F[_]]

abstract class Cata[F[_], T](implicit e: CataDep[T, F]) {
   def cata[A]: (F[A] => A) => T => A
}