Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
362 lines (278 sloc) 12.9 KB

A useful F#-style |> operator for Scala

or, a perilous adventure with Functors

Or, how I did an absolutely useless thing almost entirely for fun.

Preface

Scala has a rich and expressive collections library, but composition of operations can be kind of a pain, especially if you'd ever gotten bit by the F# bug. Consider this Scala code:

def frobnicate(numbers: List[Int]) = items
  .map(_ * 10)
  .map(_ + 20)
  .filter(_ < 30)

Now take a look at the (very rough) F# equivalent:

[1..10]
  |> List.map(fun n -> n * 10)
  |> List.map(fun n -> n + 20)
  |> List.filter(fun n -> n < 30)

A couple of thoughts come to mind immediately:

  • In Scala, invoking collection operations requires an instance of the appropriate collection type. In other words, map, filter, flatMap, and other goodies are instances of collection classes.
  • In F#, collection operations are decoupled from individual instances. Because F# functions are curried by default, calling List.map with a single function argument produces yet another function of type a' list -> b' list. This is quite nifty, because chaining of successive collection operations can occur before an actual collection instance is obtained.

This pattern can definitely be emulated in Scala, for example:

scala> val go = ((_:List[Int]).map(_ * 10)) andThen ((_:List[Int]).map(_ + 20)) andThen ((_:List[Int]).filter(_ < 30))
go: List[Int] => List[Int] = <function1>

scala> go(1 :: 2 :: 3 :: Nil)
res0: List[Int] = List()

Ew! That's a whole lotta syntax. Those seemingly extraneous parens are all required, too! Otherwise, somewhere along the way my function composition turns into a partial function that takes a 3-tuple of List[Int].

Being a curious individual, I decided to take a stab at emulating F#'s nifty |> operator in Scala. My goals for this exploration can be summarized as a reprisal of the F# code snippet shown above:

val go =
  List.map[Int](_ * 10) |>
  List.map(_ + 20)      |>
  List.filter(_ < 30)
go((1 to 10).toList)    // => should return Nil

Time to get cracking. Giddy up!

The Collection

Let's look closer at the first line of go definition. Here, List is naturally the scala.collection.immutable.List companion object, .map[Int] is a non-existent method call on the List companion, and (_ * 10) is basic arithmetic. The keen observer knows that List's companion doesn't have a .map[A] method on it, so we'll have to bolt one on. This isn't especially difficult using Scala's implicit class facility:

scala> implicit class GiddyUp(cmp: List.type) {
     | def map[A, B](f: A => B) = (_:List[A]).map(f)
     | }
defined class GiddyUp

scala> List.map((_: Int) * 10)
res0: List[Int] => List[Int] = <function1>

Cool, we have a function! Let's also conjure up a |> operator:

scala>   implicit class Composer[A, B](f: A => B) {
     |     def |>[C](g: B => C): A => C = f andThen g
     |   }
defined class Composer

scala> List.map((_: Int) * 10) |> List.map(_ + 20)
res1: List[Int] => List[Int] = <function1>

Looks like we're halfway there. Unfortunately, my dream of specifying the [Int] type parameter to map must remain just a dream, because the map[A, B] I've previously defined in GiddyUp takes two type parameters, requiring me to either specify both, or let Scala's type inference pick both out of the provided function. This isn't what I wanted.

Also, supposing I put this pattern into practice, I might reasonably expect to gain this newfangled way of map-ing atop all available collection companions. This is also not to be, because GiddyUp's input type is very specifically pegged to List.type. I'd have to (quite tediously) write out similar implicit class-es for Set.type, ArrayBuffer.type, Iterator.type and so on. There must be a better way.

The Hammer

I've never lived on a farm, but even I know that the usual farmer's work ethic of "get up at 5am & work hard till sundown" does occasionally give way to an ingeniously applied roll of duct tape.

The duct tape, in this case, is just an abstraction. It's obvious that writing more and moar GiddyUp's will get repetitive fast, despite the fact that those class bodies look awful similar to each other. This calls for an abstraction, which - in my mind anyway - crystallized into something like:

// this is pseudo code, a.k.a. martial law (I do what I want)
implicit class GiddyUp2(cmp: <blarg>.type) {
  def map[A, B](f: A => B) = (_:<blarg>[A]).map(f)
}

Here <blarg> is the nebulous, parametrically unknown collection type. On the surface, it seems that this should work for things like Option and Iterator and Stream and pretty much anything else... But, like with any abstraction worth the name, GiddyUp2's usefulness is limited by our ability to bridge the gap from <blarg>.type (which is the syntactic construct atop which we'll hang our new collection operations) to GiddyUp2. Naturally, all this must also happen in a way that compiles. But how?

Fixer

We have to keep taking apart the problem as part of the "divide & conquer" approach, because it's still too big and nebulous to be solved easily. Let's concentrate on <blarg>: what are its characteristics?

  • We know it has a [A] type parameter.
  • We kind of hope it has a map method on it.
  • We're pretty sure it has a <blarg>.type companion object.

The third one is kinda obvious, but the first two seem somewhat actionable and worthy of further investigation. Can we use these two points to describe a <blarg> abstraction?

trait Blarg[A] {
  def map[B](f: A => B): Blarg[B]
}

This is astonishingly similar to a functor. In fact, the venerable cats library defines Functor as follows:

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
  // ... moar stuff here
}

So, the upshot of this is that we can replace our <blarg> with functor, because what we're trying to do here should be possible for all functors.

Bulletville

Let's rewrite our pimp (sorry, implicit class) to incorporate our previous revelation:

// pseudo code!!11!
implicit class GiddyUp3[F[_]: Functor](cmp: F.type) {
  def map = ???
}

This looks kind of dodgy. First, there ain't no way I'm going to arrive at F.type just from F[_] without some macro-fu. Second, assuming I even had a functor, I don't know what to do with it. Let's concentrate on figuring F.type first.

A functor is parametric only over the relevant type constructor (i.e. F[_]); nothing else seems to tie it back to any possible F.type which may or may not exist. After all, not every type has a companion.

What if we turned this upside down: given a F.type, can we possibly arrive at a F[_] as well as a Functor[F]? This could be quite fortuitous, especially considering that originally we've intended to call .map and such on the companion (i.e. List.map(...)).

I've sunk many brain cycles into this question, and eventually figured out that it doesn't matter whether or not there is an elegant, "one true way" of turning F[_]'s companion into a functor. The relevant insight here is that Functor[F] becomes useful way, WAY after the companion object has outlived its usefulness to our cause. This means that the problem can be further split as follows:

// I'm still not really writing Scala - this is pseudo code again
abstract class GiddyUp4[F[_]: Functor] {
  def map = implicitly[Functor[F]].map(...)
}

import cats.implicits._ // here live Functor instances
implicit class ListGiddyUp4(cmp: List.type) extends GiddyUp4[List]

So, GiddyUp4 becomes all about using the Functor[F] to "somehow" make a map-ing happen. Then, there is a implicit class that bridges the chasm between List.type and GiddyUp4[List:Functor]. It conveniently obtains an implicitly scoped Functor[List], kindly provided to us by the good folks who made cats.

What feels good about this is the ease with which new GiddyUp4's can be conjured up for other types. Inside cats.implicits there's a plethora of Functor instances for all sorts of types, including Option, Stream and more. Plus, Functor is very easy to implement for other collection-ish types, so we have at least a hope of making possible this grand unified vision of F#-esque collection operations in Scala. The trains will run on time as long as there's functors aplenty.

But how do we implement map?

Blind spot

Let's look back to the original code snippet that started off this snafu:

List.map[Int](_ * 10)

How does this look once ListGiddyUp4 has implicitly wrapped the erstwhile List.type & made it behave like a GiddyUp4?

val wrapped = new ListGiddyUp4(List.type)(Functor[List])
wrapped.map[Int](_ * 10)

Let's take a stab at writing a possible map now:

def map[A](f: A => ?): List[A] = ...

Wait a second. What's the ? over there? We don't have a output type for our f function that we expect to pass into map. Yet tacking a second type parameter B unto map will shatter our dream of not having to pass two type params at once. How do we unwed [A, B] to make our desired syntax possible?

This one's pretty simple: we turn a single call parametric over [A, B] into two subsequent calls: one with [A] and the other with [B]:

def map[A] = new {
  def apply[B](f: A => B): List[A] => List[B] = list => implicitly[Functor[List]].map(list)(f)
}

Now, List.map[Int](_ * 10) decomposes into:

val wrapped = new ListGiddyUp4(List.type)(Functor[List])
val anon = wrapped.map[Int]     // [A] is passed by caller
anon.apply(_ * 10)              // [B] is inferred from return type of `f`

Looks like we're getting somewhere. Let's clean this up and see what the code looks like then.

The Lord of War and Thunder

Here we go:

import cats.Functor, cats.implicits._

abstract class GiddyUp5[F[_]: Functor] {
  def map[A] = new {
    def apply[B](f: A => B): List[A] => List[B] = list => implicitly[Functor[List]].map(list)(f)
  }
}

implicit class ListGiddyUp5(cmp: List.type) extends GiddyUp5[List]

implicit class Composer[A, B](f: A => B) {
  def |>[C](g: B => C): A => C = f andThen g
}

And then...

import cats.Functor
import cats.implicits._
defined class GiddyUp5
defined class ListGiddyUp5
defined class Composer

scala> List.map[Int](_ * 10) |> List.map[Int](_ + 20)
res0: List[Int] => List[Int] = <function1>

scala> res0(1 :: 2 :: 3 :: Nil)
res1: List[Int] = List(30, 40, 50)

Hurrah! We're home free. We're able to invoke collection operations off the List companion object, chain them together, and then apply the resulting composed operation to an actual live List. Does this mean we're done?

Hatless

The above approach is a good first stab at making this workable, but presents a few issues:

  • Functor alone is unsufficiently rich to implement more than just map. Thankfully, we can use another type class to access other operations. For example, MonadFilter will let us have map, flatMap and filter in one convenient package. We can extend this further by using other type classes, or inventing our own, thus bringing the joy of F#-esque chainable operations to other "monadic" types.
  • There is way too much List-iness in GiddyUp5. This is easy to clean up.
  • Nothing at all was said about Either (or Xor, cats' equivalent) and Map. Abstracting over two type parameters isn't inherently more difficult than what we've done so far, however, useful container-ish types tend to come in biased and unbiased flavors, which makes providing a single, unified implementation rather awkward.

The Spoil

This repository - currections - provides a few goodies that represent a slightly cleaned up and expanded version of what I described above:

  • MonadicCompanion[M[_]: MonadFilter] is a descendant of GiddyUp5 that relies on MonadFilter for a somewhat wider spectrum of operations.
  • MonadicCompanion2[M[_, _]] clunkily achieves a similar thing for doubly parametric types, such as Xor and Either. As I write this, I'm having weird visions of building up a better MonadicCompanion2 using two MonadicCompanion's and some type lambdas.
  • The |> operator is provided as above.
  • As part of import currections._ you'll get enough implicit goo to enable F#-style collection-fu for a few common Scala types. The nostalgia for F# is so strong here that you'll run away screaming from this code and Scala.

The Toll

Obviously cats is really great. Seriously, you should use it for everything all the time.

I love how kind-projector obviates the need for me to type any greek letters. This is kind of a big deal for me, and makes me feel a lot less pretentious.

Section headings are the names of "Justified" episodes but are otherwise meaningless outside of my febrile mind.