λ Tony’s blog λ » Blog Archive » Funky Scala Bifunctor

Funky Scala Bifunctor

A co-variant binary functor (aka bifunctor) is any type constructor with a kind * -> * -> * that can satisfy identity and composition when mapping on either type variable. A couple of examples of bifunctors in the Scala library are

Tuple2
Either

Note that Function1 is not a bifunctor, evident by the fact that it is contra-variant in its first type variable. It is notable that Tuple2 represents conjunction while Either represents the disjunction of two theorems under the Curry-Howard Isomorphism (Function1 represents implication).


A bifunctor often combines the two possible mappings into a function called bimap with the signature (Scala-ish syntax):
F[A, B] => (A => C) => (B => D) => F[C, D]

Recall that identity and composition laws must satisfy in the implementation.
Consider now an implementation of bimap for both Tuple2 and  Either:

trait Bifunctor[F[+_, +_]] {
  def bimap[A, B, C, D](fa: F[A, B], f: A => C, g: B => D): F[C, D]
}
 
object Bifunctor {
  implicit def Tuple2Bifunctor = new Bifunctor[Tuple2] {
    def bimap[A, B, C, D](fa: (A, B), f: A => C, g: B => D) = 
      (f(fa._1), g(fa._2))
  }
 
  implicit def EitherBifunctor = new Bifunctor[Either] {
    def bimap[A, B, C, D](fa: Either[A, B], f: A => C, g: B => D) = 
      fa match {
        case Left(a) => Left(f(a))
        case Right(b) => Right(g(b))
      }
  }
}

These implementations are quite easy to understand, but they are not so pretty to use. This is an unfortunate consequence of a number of factors about Scala, including:

Higher-kinds are never inferred
Functions cannot be used in infix position

In Scala, methods that end with a colon (:) can have their arguments swapped when not using dot notation. For example, the following two lines are equivalent:

obj.::(arg) 
arg :: obj

This is evident when using scala.List and the cons (::) method.
We might wrap up our Bifunctor implementation similarly and create some nice syntax for mapping on the bifunctor. For example, let us define three methods on any Bifunctor value:

<-: for mapping on one side
:-> for mapping on the other side
<-:-> for mapping on both sides


trait BifunctorW[F[+_, +_], A, B] {
  val value: F[A, B]
  val bifunctor: Bifunctor[F]
 
  def <-:->[C, D](f: A => C, g: B => D) = bifunctor.bimap(value, f, g)
 
  def <-:[C](f: A => C) = bifunctor.bimap(value, f, identity[B])
 
  def :->[D](g: B => D) = bifunctor.bimap(value, identity[A], g)
}
 
object BifunctorW {
  // a somewhat verbose but handy trick
  // for partially applying type variables.
  def bifunctor[F[+_, +_]] = new BifunctorApply[F] {
    def apply[A, B](v: F[A, B])(implicit b: Bifunctor[F]) = 
        new BifunctorW[F, A, B] {
      val value = v
      val bifunctor = b
    }
  }
 
  trait BifunctorApply[F[+_, +_]] {
    def apply[A, B](v: F[A, B])(implicit b: Bifunctor[F]): BifunctorW[F, A, B]
  }
 
  implicit def Tuple2Bifunctor[A, B](v: (A, B)) = 
    bifunctor[Tuple2](v)
 
  implicit def Either2Bifunctor[A, B](v: Either[A, B]) = 
    bifunctor[Either](v)
}

So we’ve wrapped a value and its Bifunctor implementation. So how does it look when we use it? Like this!

object Main {
  def main(args: Array[String]) {
    import BifunctorW._
 
    val x: Either[Int, String] = Left(7)
    val y = ("hello", 42)
 
    val f = (n: Int) => n + 1
    val g = (s: String) => s.reverse
    val h = (s: String) => s.toUpperCase
    val i = (n: Int) => n * 2
 
   // Pretty neat eh?
    val p = f <-: x :-> g
    val q = h <-: y :-> i
 
    // $ scala Main
    // Left(8)
    // (HELLO,84)
    println(p)
    println(q)
  }
}

And I think that’s an elegant use of a sometimes baroque (when trying for advanced concepts) language 

				
				
					
						This entry was posted
						 
						on Saturday, February 14th, 2009 at 5:16 pm						and is filed under Programming.
						You can follow any responses to this entry through the RSS 2.0 feed. 

													You can leave a response, or trackback from your own site.



	


	4 Responses to “Funky Scala Bifunctor” 

	

	
		
			Daniel Spiewak Says:
						


			February 15th, 2009 at 3:11 am 

			Actually, higher-kinds in Scala are *always* inferred (see the “Toward Higher Kinds…” paper, Odersky et al).  It is merely the types themselves which are not reconstructed.  Your own source code shows this:
trait Bifunctor[F[+_, +_]] {
I don’t see any kind declaration here.  Scala *infers* that F is of kind * => * => * (or perhaps more correctly, (*, *) => *).  In fact, there is no way (in Scala) to ever declare that a type is of one kind or another, you have to trust the compiler to figure it out every time.
Therein lies the problem, as it means that you have to be painfully explicit about some declarations (such as Bifunctor).  A language with a more universal type inference/reconstruction would be able to see that we’re instantiating the F type constructor within the declaration for the bimap method, thus it must be of a certain kind.

		

	
	
		
			Tony Morris Says:
						


			February 15th, 2009 at 6:15 am 

			“I don’t see any kind declaration here.”
There is one  

// this contains a kind declaration
Bifunctor[F[_, _]]

Consider Haskell:

-- no kind declaration though with GHC extensions it is possible
class Bifunctor f

Nevertheless, this is not what I meant. Rather, type constructors of a higher-kind are never inferred.
While Scala’s type constructors are uncurried, this is not too bothersome in this example, however, it certainly can be. There is a neat trick that allows you to partially apply type variables.
For example

trait PartialType[T[_, _], A] {
  type Apply[B] = T[A, B]
 
  type Flip[B] = T[B, A]
}

This allows you to declared type constructors such as:

Bifunctor#Apply[Int]
// or
Bifunctor#Flip[String]


		

	
	
		
			Daniel Spiewak Says:
						


			February 17th, 2009 at 4:31 am 

			> this contains a kind declaration
I guess it depends on what you see as a kind declaration.  To me, a kind declaration has to be something of the following form:
Bifunctor :: * => * => *
(shamelessly borrowing from Haskell and formal kind notation)
I would see this as an *explicit* kind annotation, where as Bifunctor[F[_, _]] is perhaps more of an *implicit* notational form.  I suppose that technically, they’re both a way of declaring kind, at some level.  The difference would be that the explicit notation is actually defining the kind, whereas Scala’s implicit notation is implying a kind by being extremely explicit about the type.
I was aware of the partially-applied type constructors idea — I read Mitch’s blog whenever I need convincing that I know a lot less than I think I do.    It is definitely a neat trick, though I can’t see myself ever using it for any real-world application.  One possible exception would be a DSL which type-checks some advanced concept.  Thus, a DSL which is correct (or rather, *runnable*) by construction.  However, given how horribly explicit Scala’s type system can be, I doubt the syntax would ever be accepted.

		

	
	
		
			Tony Morris Says:
						


			February 17th, 2009 at 6:50 am 

			A kind declaration simply declares the kind of type constructor. F[_, _] clearly declares the kind. Contrast this to Haskell where the kind is inferred. This is because Haskell infers kinds, while Scala cannot.
As for using partially-applied type constructor arguments, I do it several times a day on a commercial project without blinking an eye.

		

	
	
	

 


Leave a Reply






Name (required)


Mail (will not be published) (required)


Website