Scalaz instancing typeclass and case class

Question

This problem is pretty hard to explain. I try to implement a kind of Arrow, call it MyArr, which extends the Arrow trait from scalaz. However, MyArr is also a kind of Algbraic Data Type, so I make a few case classes out of if, and wrote down code like this(minimal example):

package org.timeless

import scalaz._
import Scalaz._
import std.option._, std.list._

sealed trait MyArr[A,B] extends Arrow[MyArr] {
  def id[A]: MyArr[A,A] = SId()
  def compose[A,B,C](s1: MyArr[B,C], s2: MyArr[A,B]): MyArr[A,C] =
    SRight(s2, s1)
  def arr[A,B](f: A=>B): MyArr[A,B] = SPure(f)
  def first[A,B,C](s: MyArr[A,B]): MyArr[(A,C),(B,C)] = SPar(s, SId())
}

case class SId[A] () extends MyArr[A,A]()
case class SRight[M[_],A,B,C](s1: MyArr[A,B], s2: MyArr[B,C]) extends MyArr[A,C]
case class SPure[A,B](f: A=>B) extends MyArr[A,B]
case class SPar[M[_],A,B,C,D](s1: MyArr[A,B], s2: MyArr[C,D]) extends MyArr[(A,C),(B,D)]

object MyArr {
  val b = SId[Int]()
  val c = SId[Int]()
  // val a: MyArr[Int,Int] = id[Int] // Error
  // val d = c compose b // Error
  // val d = b >>> c // Error
  val d = b >>> (b,c) // ??? Arguments
}

As easily seen, the id function is actually the constructor of SId, etc. The classes themselves compile fine, but I don't see any way to actually use it as an Arrow. I actually came from Haskell programming, so I might be doing it totally wrong, but equivalent code in Haskell should be like this(with GADTs):

data MyArr a b where
  SId :: MyArr a b
  SRight :: MyArr a b -> MyArr b c -> MyArr a c
  SPure :: (a -> b) -> MyArr a b
  SPar :: MyArr a b -> MyArr c d -> MyArr (a,c) (b,d)

instance Category MyArr where
  id = SId
  (.) = SRight

instance Arrow MyArr where
  arr = SPure
  first s = SPar s SId

Answer 1

Typeclasses in Scala

Typeclasses in Scala are not built into the language like in Haskell. They are just a design pattern and are usually implemented with the help of implicit arguments:

def pure[M[_], T](
  implicit monad: Monad[M] // Fetching a monad instance for type M
): M[T] = 
  monad.pure[T]            // Using methods of the monad instance

You don't have to extend the typeclass trait to provide a typeclass instance for some ADT. The typeclass instance has to be defined somewhere as an implicit val, implicit def, implicit object, etc. Then you can import the relevant instance into scope before using it.

There is also a way to supply the typeclass instance automatically, without having to import it explicitly. To do that the instance should be declared in the companion object of either the typeclass class/trait or ADT class/trait, or one of their parent classes/traits; or in a package object in which one of those is defined. You can read more on the topic of implicit resolution in this answer: Where does Scala look for implicits?

Defining a typeclass instance

So to get back to your problem, you can define your ADT like this:

sealed trait MyArr[A,B]
case class SId[A] () extends MyArr[A,A]()
case class SRight[M[_],A,B,C](s1: MyArr[A,B], s2: MyArr[B,C]) extends MyArr[A,C]
case class SPure[A,B](f: A=>B) extends MyArr[A,B]
case class SPar[M[_],A,B,C,D](s1: MyArr[A,B], s2: MyArr[C,D]) extends MyArr[(A,C),(B,D)]

And provide the Arrow instance in the companion object of MyArr:

object MyArr {
  implicit val arrow: Arrow[MyArr] = new Arrow[MyArr] {
    def id[A]: MyArr[A,A] = SId()
    def compose[A,B,C](s1: MyArr[B,C], s2: MyArr[A,B]): MyArr[A,C] =
    SRight(s2, s1)
    def arr[A,B](f: A=>B): MyArr[A,B] = SPure(f)
    def first[A,B,C](s: MyArr[A,B]): MyArr[(A,C),(B,C)] = SPar(s, SId())
  }

  def apply[T]: MyArr[T, T] = arrow.id[T]
}

Using the typeclass instance

I believe it's not possible to provide a generic id function (or return, pure, etc.) in Scala due to some limitations of Scala's type inference.

Instead you can use the MyArr.apply method defined above:

val a: MyArr[Int,Int] = MyArr[Int]

As the ADT doesn't extend the typeclass, it doesn't inherit its methods like compose or >>>. They can be provided separately using the 'Pimp My Library' pattern.

Indeed, the >>> method in scalaz comes from the ComposeOps class, which is defined like this:

final class ComposeOps[F[_, _],A, B] private[syntax]
  (self: F[A, B])
  (val F: Compose[F]) 
  extends Ops[F[A, B]]

And there is an implicit conversion defined from some type F[_, _] to this class ComposeOps, if there as a Compose instance available for F:

implicit def ToComposeOps[F[_, _],A, B](v: F[A, B])(implicit F0: Compose[F])

This conversion is imported with import Scalaz._, and that's why this line works now:

val d = b >>> c

But there is no extension in scalaz that provides a compose method on ADTs with an Arrow instance, so this line still gives an error:

val e = c compose b

To make it work, you can provide an extension yourself. A simple example could look like this:

// implicit class is equivalent to a normal class 
// with an implicit conversion to this class
implicit class ArrowOps[T[_, _], A, B](f: T[A, B])(implicit arrow: Arrow[T]) {
  def compose[C](g: T[C, A]): T[C, B] = arrow.compose(f, g)
}