λ Tony’s blog λ

A core part of Haskell’s type system is that of type-classes. If you have never used type-classes, then there is a pretty good description in Yet Another Haskell Tutorial (YAHT). Haskell type-classes have been likened to Java/C# interfaces or Scala traits, but there are some significant differences.

With Scala’s implicit definitions (defs), it is possible to come pretty close to emulating Haskell’s type-classes. This ability can make writing certain constructs very simple and also, extremely flexible. Imagine you were asked to write a function that found the maximum value in a List of values. In Scala, we might write it like this:

object O {
  def maximum(x: List[Int]): Int = x match {
    case Nil => error("maximum undefined for empty list")
    case x :: y :: ys => maximum((if(x > y) x else y) :: ys)
    case x :: _ => x
  }
}

Notice that if we wish to write the function for some other type besides Int, we would have to start again. Or, we could generalise to the Scala Ordered type:

object O {
  def maximum[a <: Ordered[a]](x: List[a]): a = x match {
    case Nil => error("maximum undefined for empty list")
    case x :: y :: ys => maximum((if(x > y) x else y) :: ys)
    case x :: _ => x
  }
}

So we accept now that we can find the maximum of any type, so long as that type implements the Ordered trait/interface. But what if we have a type that doesn’t implement that interface? Worse still, what if our type does implement that interface, but we wish to redefine ordering? The only solution here is to create a new type that wraps the old type and redefines ordering. In Haskell, this is called “newtyping”, because it is done with the newtype keyword and is one line of very trivial code (newtype T = T U) plus the two or three for the redefinition of ordering. However, in other languages, this is a little cumbersome and can lead to the bloating of code that is difficult to understand.

Scala implicit defs come to the rescue here. But first, a little introduction to two core Haskell type-classes called Eq and Ord. Here is an excerpt of their definitions:

class  Eq a  where
  (==), (/=)   :: a -> a -> Bool
  -- omitted as superfluous to the topic

class  (Eq a) => Ord a  where
  compare      :: a -> a -> Ordering
  -- omitted as superfluous to the topic

This first declaration is of the Eq type-class and states that to implement the class over an unbound type (a), one must define equality such that gives two instances of (a), return a boolean value indicating equality (or non-equality). The second declaration is of the Ord type-class and states that to implement the class over a type (a) that is bound by the type-class Eq, one must define ordering such that given two instances of (a), return a type Ordering (which has only three possible values; LT, EQ, GT).

We can express something similar in Scala. However, note that the type parameter (a) is not co-variant, while all Haskell type parameters are co-variant. This is because Haskell is a pure functional programming language, while Scala is not.

trait Eq[a] {
  def eq(a1: a)(a2: a): Boolean
}

trait Ord[a] extends Eq[a] {
  override def eq(a1: a)(a2: a) = compare(a1)(a2) == EQ
  def compare(a1: a)(a2: a): Ordering
}

// for completeness
sealed abstract class Ordering
final case object LT extends Ordering
final case object EQ extends Ordering
final case object GT extends Ordering

Now comes the interesting part (sorry to the impatient :)). Imagine now that we could write our maximum function, where we could say “the maximum of a list of any type (a) such that there exists one and only one implementation of the Ord trait for type (a) implicitly defined in compiler scope“. That is to say, if there exists two or more implementations of Ord, fail the compiler with an ambiguity error (indeed, many Scala newcomers have likely observed these ambiguity errors from the core Scala APIs). If there is no implementation within scope, fail as well.

Here is how we would write the function now:

object Maximum {
  def maximum[a](as: List[a])(implicit o: Ord[a]): a = as match {
    case Nil => error("maximum undefined for empty list")
    case x :: y :: ys => maximum((o.compare(x)(y) match {
      case GT => x
      case _ => y
    }) :: ys)
    case x :: _ => x
  }
}

Notice that the function takes two arguments, however, one of them is declared implicit. This means that we do not need to explicitly provide this argument (though we can and we might to resolve an ambiguity, but there are also other means). So long as there exists one implementation of Ord[a] implicitly defined in compiler scope, then this implementation is used.

Let us write such an implementation:

object Ord {
  implicit def intOrd = new Ord[Int] {
    def compare(a1: Int)(a2: Int) = if(a1 == a2) EQ else if(a1 < a2) LT else GT
  }
}

Notice that the definition of intOrd is declared with the implicit keyword. Now, if the intOrd function is in scope (and no other implementation is), then we can call the maximum function with a list of integers. Indeed, if we had some other definition of ordering for integers (which is rarely the case for integers, but imagine it were some other type), we would not have to rewrite anything to continue using our maximum function.

Also, be aware that implicit definitions are not transitive. This means that although we might have an implicit definition from Int to Ord[Int] and we might have some other implicit definition from T to Int, however, this does not imply that we have an implicit definition from T to Ord[Int]. This attribute is very unfortunate and quite limiting of the potential of implicit definitions, but one that is to be accepted nonetheless.

At this point, some would be thinking, “so what?”. After all, some have no problem with newtyping (or adapting or design patterning or whatever you want to call it). However, I draw your attention to one example of many where this approach would save much more work. Let us take a look at that List.range function. Notice how the range function is defined over integers only? If I wanted to get a range for some other type, I’d have to rewrite the range function, or I’d have to write a conversion to type Int and use that. Both very annoying.

Indeed, the range function can be generalised to any type that has the notion of a successor (as well, a predecessor if we wish to support backward ranges). However, if we were to define a range function with a step n (default: n = 1), then invoking our successor or predecessor function n times may lead to an inefficiency that is resolved by the integer type, because it has the constant-time + function. Indeed, we would need another function successor(n) so that this efficiency gain could be utilised for types that support it, such as the integer type, where it would use the + function. By default, this implementation would simply invoke the successor function n times. We will acknowledged this fact but will ignore it hereon.

Let us define our successor function:

trait Successor[a] {
  def succ(a: a): Option[a]

  // for efficiency reasons, we might define this function
  // A default implementation invokes the succ function n times.
  // The integer implementation would override and use +
  // def succn(n: Int)(a: a): Option[a]
}

The succ function returns a succeeding value of type (a) if it exists, but no value if there is no successor i.e. the type is maximally bounded. This is the case for the integer type where Integer.MAX_VALUE has no successor. We would write the implementation like so:

object Successor {
  implicit def intSuccessor = new Successor[Int] {
    override def succ(a: Int) = a match {
      case Integer.MAX_VALUE => None
      case _ => Some(a + 1)
    }
  }
}

Now, we can write our range function such that it is defined over any type, so long as that type has one and only one implementation of both Successor[a] and Ord[a] in scope. The implementation of Ord[a] is required to determine the ordering of the from parameter to the to parameter. Also, the equality relation (defined by Eq[a]) is required to know when the range stops.

object Range {
  def range[a](from: a)(to: a)(implicit e: Successor[a], o: Ord[a]): List[a] =
    if(o.compare(from)(to) == GT) Nil
    else if(o.eq(from)(to)) List(from)
    else e.succ(from) match {
      case None => List(from)
      case Some(s) => from :: range(s)(to)
    }
}

Suppose we wish to find the range of a list of playing cards. Is it Aces high or Aces low? What about other card orderings used in the myriad of different card games? What about other types besides playing cards? It doesn’t matter, since our range function is as general as it can be. Yay! No more writing the same code over and over!

sealed abstract class Rank
final case object ACE extends Rank
final case object TWO extends Rank
final case object THREE extends Rank
final case object FOUR extends Rank
final case object FIVE extends Rank
final case object SIX extends Rank
final case object SEVEN extends Rank
final case object EIGHT extends Rank
final case object NINE extends Rank
final case object TEN extends Rank
final case object JACK extends Rank
final case object QUEEN extends Rank
final case object KING extends Rank

object Rank {
  implicit def acesHigh = new Successor[Rank] with Ord[Rank] {
    val ranks = Array(TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, JACK, QUEEN, KING, ACE)

    override def compare(a1: Rank)(a2: Rank) = if(a1 == a2) EQ else if(ranks.indexOf(a1) < ranks.indexOf(a2)) LT else GT

    override def succ(a: Rank) = a match {
      case ACE => None
      case _ => Some(ranks(ranks.indexOf(a) + 1))
    }
  }

  implicit def acesLow = new Successor[Rank] {
    val ranks = Array(ACE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, JACK, QUEEN, KING)

    override def succ(a: Rank) = a match {
      case KING => None
      case _ => Some(ranks(ranks.indexOf(a) + 1))
    }
  }
}

Notice here that we can bring either acesHigh or acesLow into compiler scope (but not both) and use the range function successfully. Indeed, the following code prints different output because of which function is in scope:

object Main {
  def main(args: Array[String]) = {
    {
      import Rank.acesHigh
      Console.println(range(TWO: Rank)(THREE)) // List(TWO,THREE)
      Console.println(range(TWO: Rank)(ACE)) // List(TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINE,JACK,QUEEN,KING,ACE)
      Console.println(range(ACE: Rank)(KING)) // List()
    }

    {
      import Rank.acesLow
      Console.println(range(TWO: Rank)(THREE)) // List(TWO,THREE)
      Console.println(range(TWO: Rank)(ACE)) // List(TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINE,JACK,QUEEN,KING)
      Console.println(range(ACE: Rank)(KING)) // List()
    }
  }
}

Reader’s exercise: write a range function with step of type Int, which may be negative (and so step backward)

Here is a complete, compilable source code listing:

trait Eq[a] {
  def eq(a1: a)(a2: a): Boolean
}

sealed abstract class Ordering
final case object LT extends Ordering
final case object EQ extends Ordering
final case object GT extends Ordering

trait Ord[a] extends Eq[a] {
  override def eq(a1: a)(a2: a) = compare(a1)(a2) == EQ
  def compare(a1: a)(a2: a): Ordering
}

object Ord {
  implicit def intOrd = new Ord[Int] {
    def compare(a1: Int)(a2: Int) = if(a1 == a2) EQ else if(a1 < a2) LT else GT
  }
}

object Maximum {
  def maximum[a](as: List[a])(implicit o: Ord[a]): a = as match {
    case Nil => error("maximum undefined for empty list")
    case x :: y :: ys => maximum((o.compare(x)(y) match {
      case GT => x
      case _ => y
    }) :: ys)
    case x :: _ => x
  }
}

trait Successor[a] {
  def succ(a: a): Option[a]
}

object Successor {
  implicit def intSuccessor = new Successor[Int] {
    override def succ(a: Int) = a match {
      case Integer.MAX_VALUE => None
      case _ => Some(a + 1)
    }
  }
}

object Range {
  def range[a](from: a)(to: a)(implicit e: Successor[a], o: Ord[a]): List[a] =
    if(o.compare(from)(to) == GT) Nil
    else if(o.eq(from)(to)) List(from)
    else e.succ(from) match {
      case None => List(from)
      case Some(s) => from :: range(s)(to)
    }
}

sealed abstract class Rank
final case object ACE extends Rank
final case object TWO extends Rank
final case object THREE extends Rank
final case object FOUR extends Rank
final case object FIVE extends Rank
final case object SIX extends Rank
final case object SEVEN extends Rank
final case object EIGHT extends Rank
final case object NINE extends Rank
final case object TEN extends Rank
final case object JACK extends Rank
final case object QUEEN extends Rank
final case object KING extends Rank

object Rank {
  implicit def acesHigh = new Successor[Rank] with Ord[Rank] {
    val ranks = Array(TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, JACK, QUEEN, KING, ACE)

    override def compare(a1: Rank)(a2: Rank) = if(a1 == a2) EQ else if(ranks.indexOf(a1) < ranks.indexOf(a2)) LT else GT

    override def succ(a: Rank) = a match {
      case ACE => None
      case _ => Some(ranks(ranks.indexOf(a) + 1))
    }
  }

  implicit def acesLow = new Successor[Rank] {
    val ranks = Array(ACE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, JACK, QUEEN, KING)

    override def succ(a: Rank) = a match {
      case KING => None
      case _ => Some(ranks(ranks.indexOf(a) + 1))
    }
  }
}

object Main {
  def main(args: Array[String]) = {
    import Ord.intOrd
    Console.println(Maximum.maximum(List.range(1, 10)))

    import Range.range

    Console.println(range(7)(8))
    Console.println(range(7)(7))
    Console.println(range(7)(6))
    Console.println(range(Integer.MAX_VALUE)(Integer.MAX_VALUE))
    Console.println(range(Integer.MAX_VALUE - 1)(Integer.MAX_VALUE))
    Console.println(range(Integer.MAX_VALUE)(7))
    Console.println(range(Integer.MIN_VALUE)(Integer.MIN_VALUE + 1))

    {
      import Rank.acesHigh
      Console.println(range(TWO: Rank)(THREE))
      Console.println(range(TWO: Rank)(ACE))
      Console.println(range(ACE: Rank)(KING))
    }

    {
      import Rank.acesLow
      Console.println(range(TWO: Rank)(THREE))
      Console.println(range(TWO: Rank)(ACE))
      Console.println(range(ACE: Rank)(KING))
    }
  }
}

I recently read an article (on C programming) that made the following claim:

Either f() or g() gets called twice. This is inefficient [where both f and g are equivalent functions.]

Unfortunately, these kind of statements are very common among programmers who generally only use a certain class of programming languages (strict and imperative; C, Java, C# etc.) and I have seen the statement in various forms many times before, but I have been compelled to dispel this myth. I don’t intend to pick on this particular article — after all, the intended topic of the article is unrelated to the fallacious statement, despite being a premise for the article’s conclusions and there are many other writers who are most capable of propagating this misinformation anyway. What the author of this statement might not know is that it contradicts some really interesting branches of mathematics including the Lambda Calculus and Complexity Theory (you may have noticed the lambda symbols in the title of this page and you may have seen the term λ-calculus written before).

The space versus computation trade is a standard problem for computer scientists, but recent industry trends have generalised this problem to the point of actually not appearing like a problem at all. You see, space has become cheap, really cheap — so cheap that it almost appears infinite. Let us consider the problem of finding the nth element of an array and a linked list. For the array, this will execute in constant time, however, for the linked list, the time to compute it will depend on the value of n. Notice how the array exists in-memory while the linked list might not (e.g. it may read from a file as it is traversed). That is, it has incurred a space cost. This cost has provided the benefit of computation speed. A trade has occurred, not an efficiency gain.

The use of the linked list is called lazy evaluation (or laziness) while the use of an array is called strict evaluation (or strictness). Traversing the linked list is sometimes called thunking (which is just an obscure word for invoking a function) and evaluating each of its elements is called Weak Head Normal Form (WHNF), which is a term taken from the λ-calculus.

Given a lazily evaluated structure, it is possible to make it strict by bringing it to WHNF. This computation will occur once and its result may be placed in a universally-available table with constant time lookup to prevent computing the value again. This storage will incur space and is a process called memoisation. Unfortunately, a strict structure cannot be made lazy since the space cost has already been incurred. In fact, doing so yields no benefit whatsoever (other than to appeal to a type system).

We can observe laziness and strictness in some of our poor-yet-popular programming languages like Java, where an array represents a strict, homogenous list, while an InputStream or Iterator represents a lazy list. A ByteArrayInputStream is a (unfortunate) attempt to construct a lazy structure from a strict one with no additional benefit — in this case, it is to appeal to a type system (e.g. to use a method that must accept an InputStream instead of a byte[]). A Haskell list, which is lazy, is more like a Java iterator than a Java list or array (but still with a significant difference) and it is often better to think this way if you are learning a lazy language coming from a strict, imperative language. In fact, like a Haskell list, a Java iterator can have an infinite length where its hasNext method never returns false.

We can see now that if f() or g() gets called twice, then this is not inefficient, nor is it efficient. This is actually a trade. Computation has been spent while space has been gained, since the result of the computation of the first call of either function is not stored, but is recomputed. Similarly, purchasing a bottle of water for one dollar is not more or less efficient, assuming that the bottle of water is indeed worth one dollar. You are no more or less better off whether you purchased the water or not. Of course, we rarely see such purist forms of capitalism, but the analogy makes sense otherwise
Programmers of strict, imperative languages do not always elect to strictly evaluate from what is called a universe (or domain) of discourse (from Set Theory). That is to say, from the universe (U) that is passed to the programmer, each expression is not necessarily brought to WHNF. Ideally, only what is necessary is evaluated to complete the computation and anything else from U is left untouched, however, the decision of what to evaluate is often (at least in my observations) totally arbitrary due to a lack of formal reasoning and inexperience with the foundations of computer programming — on the part of the programmer. If a subset of the universe is evaluated that is never needed to complete the computation, then this is an inefficiency and it happens very often in strict, imperative languages. (Think tip: Is it any wonder your Java application consumes all your volatile memory?)

Let’s demonstrate this. Suppose a Java programmer is asked to compute an int — the sum of the first 2 bytes from an InputStream, or compute 1024 if the bytes are not available. The InputStream represents a potentially infinite universe of discourse (|U| = ∞), however, not all of it is necessarily evaluated (if it were infinite, the function would never terminate). Here is a canonical solution:

  int firstByte(InputStream in) throws IOException {
    final int i = in.read();
    final int j = in.read();
    return i == -1 || j == -1 ? 1024 : i + j;
  }

Notice how the entire InputStream is not read until the end (if there is one), simply because you can, since this would be an inefficiency. The domain or universe is an InputStream, but only two reads occur. Indeed, if this InputStream were infinite, the function would still terminate. Similarly, the following equivalent Haskell function will terminate:

  let first (i:j:_) = i + j; first _ = 1024

…even if passed an infinite list:

> first [20..] -- from 20 to infinity
41

If a byte[] were passed to the firstByte function instead and the entire array were never evaluated for the computation (why would it?), we would have an inefficiency. If the array was fully evaluated during computation, then we have neither an efficiency, nor an inefficiency. Certainly, evaluating beyond the universe of discourse yields no benefit whatsoever while incurring a space cost. Unfortunately, this is not immediately obvious because poor-yet-popular programming languages sometimes make it cumbersome to write the desired expression without incurring this inefficiency and so it appears as if it were a necessary trade with the language itself. That is, the reasoning “because this language is cumbersome to such an extreme, it will force you to incur inefficiencies by evaluating outside your domain for computation so as to avoid writing code that is cumbersome” is often overlooked, typically because the alternatives are not known. Also, the more elegant solution, even in that cumbersome programming language, is often overlooked. Nevertheless, I find this behaviour of both the programming language and the programmer using that language, completely absurd (I love you Alex ;))

However, languages such as C/Java often make laziness very easy. Suppose you write an if/else. The runtime will not evaluate both the if and else block before executing one or the other. This is lazy behaviour. Similarly, the ternary operator (?:) is also lazy. Finally, the && and || operators are also lazy, since their second argument is only evaluated on-demand. Therefore, we see clearly that laziness is not a completely foreign concept to (mostly :)) strict, imperative languages and is often preferred, since the contrary may certainly result in an inefficiency.

I leave now with the following transcript from my GHC/Haskell interpreter (which is inherently lazy):

> take 5 [1..] -- take the first 5 elements from the list of 1 to infinity
[1,2,3,4,5]
> foldr (&&) True $ repeat False -- fold the conjunction of True and an infinite list of False
False
> foldr (||) False $ repeat True -- fold the disjunction of False and an infinite list of True
True
> -- foldr (||) True $ repeat False -- eek! this will never terminate!
> take 5 $ map (*2) [1..] -- take the first 5 elements from the list with the function (*2) mapped across 1 to infinity
[2,4,6,8,10]