Treat Yourself to a Listy Tuple!

We don’t use tuples enough, and part of the reason is, they’re kind of ugly to use. I mean, using whatever._1 to access a value is kind of ugly.

shapeless to the rescue!

The opening sentence on the shapeless site is kind of off-putting: “shapeless is a type class and dependent type based generic programming library for Scala.” Ok, that doesn’t really tell me what’s in it for me… so I thought I’d write up a few examples.

Back to those tuples. Wouldn’t it be cool if you could treat tuples just like other collection types in Scala? For instance, if you could get the head and tail of a tuple?

import syntax.std.tuple._
(23, "foo", true).head
// res0: Int = 23

Nifty! You can use tail, drop, and take too, as you might expect. You can also append, prepend, and concatenate tuples much like you can other container types:

(23, "foo") ++ (true, 2.0)
// res1: (Int, String, Boolean, Double) = (23,foo,true,2.0)

And perhaps best of all, you can now map, flatMap, fold and otherwise chop, spindle, and manipulate your tuples:

import poly._

object option extends (Id ~> Option) {
  def apply[T](t: T) = Option(t)
}

(23, "foo", true) map option
// res2: (Option[Int], Option[String], Option[Boolean]) = (Some(23),Some(foo),Some(true))

Before we look at some of the really cool things this enables, here’s one more tuple-trick, thanks to singleton-typed literals:

val t = (23, "foo", true)
t(1)
// res0: String = foo

So yes, if you really hate it that much, you can now effectively be done with the ._1 syntax. But shapeless does a lot more than make working with tuples easier. For instance, it provides an implementation of extensible records. This makes it possible to create extensible records like this book:

import shapeless._ ; import syntax.singleton._ ; import record._

val book =
  ("author" ->> "Benjamin Pierce") ::
  ("title"  ->> "Types and Programming Languages") ::
  ("id"     ->>  262162091) ::
  ("price"  ->>  44.11) ::
  HNil

And then operate on the book:

book("title")   // Note result type ...
// res1: String = Types and Programming Languages

I’ll leave exploring shapeless’ extensible records to you (check out the GitHub Feature Overview page).

One more feature I feel compelled to mention, just because I love them, are lenses. The shapeless implementation supports boilerplate-free lens creation for arbitrary case classes. Unless you’re already married to Scalaz or Monacle, you’ll want to give the shapeless lens a try:

ageLens = lens[Person] >> 'age
age1 = ageLens.get(person)
// age1: Int = 37

Lenses are pretty cool once you get used to them. They lead to some marvelously readable, maintainable code. Check them out, along with shapeless’ typesafe case operator, cast. If you’ve ever been bitten by type erasure, this just might be the solution you’ve been looking for.

Once you get excited about shapeless you might want to pick up a copy of The Type Astronaut’s Guide to Shapeless. It’s free!

What is Functional Programming?

While looking for great Scala or Erlang programmers, one of the first things I ask is “what does functional programming mean to you?” Most of the time, the answer hovers around “programming with higher order functions,” or “programming with functions instead of objects.” Both are good language features that belong to functional languages. Neither answer is what I’m looking for.

The problem with both of these answers is that they hint at non-functional thinking. It’s still looking at programming through an imperative or object oriented perspective.

For example, let’s consider two different approaches to representing a Set of integers (an arbitrary collection of integer values). The imperative approach tends to make a list of values. Here’s a simple Set object that defines both an add and remove method:

object Set {
	val values: List[Int] = List()
	def add(q: Int) = q :: values :: Nil
	def remove(q: Int) = values.filter(_ != q)
}

At first glance this appears to tick all the boxes for a “functional language.” It uses immutable values. The functions are side-effect free (they don’t change values outside of their own scope).

When I hear the goal is “programming without side-effects,” I’m usually pretty happy. It’s a good layman’s definition of functional programming (for those of us that don’t remember it’s all about referential transparency). Avoiding side-effects tends to check most of the important functional boxes. If you can’t have side-effects, you usually lean toward immutability. You also write functions that don’t reach outside their own scope, so your functions always produce the same outputs given the same inputs. You avoid exceptions because, let’s face it, they’re just a way of making your problem someone else’s problem. And all of that combined tends to produce code that is referentially transparent.

But we’re still in imperative-land. If we really want to think in functional terms, we need to eschew imperative thinking entirely. We need to think like a mathematician. Mathematicians think very purely about functions in the mathematic sense. (It’s a shame that programming uses the term “function” instead of “method,” I think this leads to a lot of functional programming terminology confusion).

For example, a Set to a mathematician is simply a collection of values:

s = { 3 }
t = { 7, 9 }

Here we have two Sets, one representing the single-value set of 3, and the other, both 7 and 9. We can model the collection of both sets like so:

c = s ∪ t

This models the set c as the union of both s and t, so c is a set containing 3, 7 and 9.

In Scala, a pure functional approach to this might look like this:

type Set = Int => Boolean

In other words, a function taking an Int and returning a Boolean. Given a single integer value the function tells us if the value is in the set. You could then write a function that tests whether a given value exists within the Set:

def contains(s: Set, n: Int): Boolean = s(n)

In this function, given a Set s and an integer n, we see if the set is true for n.

You could represent a Set that contains many values by writing a function that combines two:

def union(s: Set, t: Set): Set = (x => s(x) || t(x))

Here we return a new Set that is composed to two different Sets, s logically or’d with t. This works because Scala is a functional language and is able to model programming functionally, meaning in a non-imperative way.

The native Scala Set class demonstrates this thinking. If you look at scala.collection.Set you’ll find it’s a trait defined as as a function that takes a value of type A and returns a Boolean:

trait Set[A] extends (A => Boolean)

Thinking functionally is not the same as thinking imperatively, or using an object oriented approach. It really is a fundamental shift in how we approach programming. It takes some time to adopt. The joy about Scala is that you can start from an object oriented background and move toward a more functional nature over time. The language allows you to blend features of both paradigms.

Elegance Can Be the Enemy of Efficiency

I’ve been auditing some of the advanced Scala courses offered by École Polytechnique Fédérale de Lausanne, and as always am curious about my own solutions compared against what other people come up with.

One of the things I love about Scala is its elegance. Once you understand the language, you can achieve some really complex things quickly and easily — and, elegantly. So, a problem posed in the coursework is to write a function that, given a character in a game field, returns the first index of that character in the field.

After writing my own solution, I Googled a few other solutions. Here’s one:

def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = {
   val ys = levelVector map (_ indexOf c)
   val x = ys indexWhere (_ >= 0)
   Pos(x, ys(x))
}

This is pretty elegant. In fact, I was first taken by how functional it looked — more functional than my own code. But there’s a problem. This elegant code is potentially very inefficient.

Let’s assume the game field is big. It consists of a Vector of Vectors, and the above code searches the entire game field. That is, even if the character matches the very first element in the field, all the rest of the elements will be scanned:

  1. ys maps over the entire Vector of Vector scanning for the index of c.
  2. x then scans the vector ys for a positive hit.
  3. Then the coordinate is returned from the points described by x and ys(x).

So the obvious problem here is our elegant, functional, good looking code could be terribly inefficient. Here’s my implementation:

def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = { 
   @tailrec def iterate(x: Int): Pos = levelVector(x).indexOf(c) match { 
      case y if y > -1 => Pos(x, y) 
      case _ => iterate(x + 1) 
   } 
   iterate(0) 
}

Ok, it’s not as pretty, it’s longer, but — it’s still functional by design. More important, it will look for the character using a linear search, and stops when it finds the character. It’s efficient:

  1. We start in the first Vector, checking for the index of the character.
  2. As soon as we find it, the function returns. Otherwise, it recurses and moves to the next Vector.

It’s not as pretty but it preserves efficient design. Just because we can write pretty, elegant code doesn’t mean we always should.

Incidentally, you could also achieve nearly the same efficiency using something like this:

val row = levelVector.indexWhere(_.contains(c))
val col = levelVector(row).indexOf(c)

Personally, I prefer to avoid any potential inefficiency — but, over-optimizing can also be a problem. It’s probably best to find a happy balance. Don’t ignore efficiency, but don’t spend all your time optimizing situations that, quite likely, don’t really need the effort.