![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
type classes as I see them in Scala
Jan. 21st, 2013 09:12 pmSpent a couple of weeks trying to figure out what exactly is it. Looked it up in Wikipedia, in Scala, in Haskell, in popular articles. Now I think I know what it is; here's my vision. Please pardon my English and my cheap, simplified Math.
1. Type Class is an Algebraic Theory
An algebraic theory is a rather abstract notion. It consists of variables of one or more types, a collection of operations, and a collections of axioms.
1.1. Example
Monoid. Just one variable type; two operations: a binary operation and a nullary operation (that produces a neutral element), and axioms: associativity and neutral element neutrality. Integer numbers can be perceived as a monoid, say, using multiplication as the binary operation and 1 as the neutral element.
1.2. Example
Vector space over a field. We have two types of variables, vectors and scalars. Scalars can add, subtract, multiply, divide, have a zero, a one; vectors can add, subtract, have a zero, can be multiplied by a scalar. We can also throw in scalar product of two vectors.
2. But Can We Express A Theory As Trait (interface, in Java)?
On many occasions, yes. You can define a pure abstract trait (or, in Java, just an interface) that defines the operations, e.g. for a monoid:
Notice, we do not specify any axioms. In languages like Scala, Haskell, Java, we cannot. It takes Agda to handle axioms.
We have a problem here that the if we try to introduce a specific kind of monoid, the result of binOp does not belong to that kind; so we have to be more careful and design our trait keeping in mind we are going to extend it, like this:
Now we can define something like
It works... but well, the new class is not exactly a
Suppose for a moment we could (we can do it in JavaScript ad libitum). What would we do with Ints then? What binary operation, addition? multiplication? min? max? There might be more.
Now let's disambiguate.
2 3. Model
When we defined a trait without implementation, we described a theory. When we started building specific implementations, we define a model for our theory. There may many models for the same theory; the same structure may be a model of a variety of theories. We have to be able to express this relationship.
In the example above we made
In Haskell, models are called instances (of a type class); in C++0x (please excuse my misspelling) they are called models (and theories are called concepts).
In Haskell one can define
and model it with lists (strings are lists in Haskell):
We can do it in Scala, kind of more verbosely.
In one case we used one
3. Important Remark
We could probably start thinking, hmm, how about just parameterized types, what's the difference? Say, take
Not exactly. It is a totally different thing, unfortunately written in the same style. Here we have a functor: given a type
While we could make it into a type class, if the polymorphism here were ad-hoc, we normally do not.
4. That's Not It Yet
Next I'll show how we can restrict the scope of certain operations to certain subtypes, of the type that we pass as a parameter.
please correct me where I'm wrong
1. Type Class is an Algebraic Theory
An algebraic theory is a rather abstract notion. It consists of variables of one or more types, a collection of operations, and a collections of axioms.
1.1. Example
Monoid. Just one variable type; two operations: a binary operation and a nullary operation (that produces a neutral element), and axioms: associativity and neutral element neutrality. Integer numbers can be perceived as a monoid, say, using multiplication as the binary operation and 1 as the neutral element.
1.2. Example
Vector space over a field. We have two types of variables, vectors and scalars. Scalars can add, subtract, multiply, divide, have a zero, a one; vectors can add, subtract, have a zero, can be multiplied by a scalar. We can also throw in scalar product of two vectors.
2. But Can We Express A Theory As Trait (interface, in Java)?
On many occasions, yes. You can define a pure abstract trait (or, in Java, just an interface) that defines the operations, e.g. for a monoid:
trait Monoid {
def neutral: Monoid
def binOp(another: Monoid): Monoid
}
Notice, we do not specify any axioms. In languages like Scala, Haskell, Java, we cannot. It takes Agda to handle axioms.
We have a problem here that the if we try to introduce a specific kind of monoid, the result of binOp does not belong to that kind; so we have to be more careful and design our trait keeping in mind we are going to extend it, like this:
trait Monoid[Actual] {
def neutral: Actual
def binOp(another: Actual): Actual
}
Now we can define something like
class StringConcatMonoid(val s: String) extends Monoid[StringConcatMonoid] {
def neutral = new StringConcatMonoid("")
def binOp(another: StringConcatMonoid) = new StringConcatMonoid(s + another.s)
}
It works... but well, the new class is not exactly a
String class, right? That's the problem, we cannot throw in the new functionality into String. Suppose for a moment we could (we can do it in JavaScript ad libitum). What would we do with Ints then? What binary operation, addition? multiplication? min? max? There might be more.
Now let's disambiguate.
When we defined a trait without implementation, we described a theory. When we started building specific implementations, we define a model for our theory. There may many models for the same theory; the same structure may be a model of a variety of theories. We have to be able to express this relationship.
In the example above we made
StringConcatMonoid a model of Monoid theory. We were lucky, we had just one type; imagine we had more than one. Then there's no way to inherit anything. And we are still not happy that we cannot define binOp on Strings themselves; we look at Haskell, and seems like they do it easily.In Haskell, models are called instances (of a type class); in C++0x (please excuse my misspelling) they are called models (and theories are called concepts).
In Haskell one can define
class Monoid m where
binOp :: m -> m -> m
neutral :: m
and model it with lists (strings are lists in Haskell):
instance Monoid [a] where
binOp = (++)
neutral = []
We can do it in Scala, kind of more verbosely.
object A {
implicit object addMonoid extends Monoid [Int] {
def binOp (x :Int,y :Int) = x+y
def neutral = 0
}
}
object B {
implicit object multMonoid extends Monoid [Int] {
def binOp (x :Int,y :Int) = x ∗ y
def neutral = 1
}
}
val test :(Int,Int,Int) = {
{
import A._
println(binOp(2, 3))
}
{
import B._
println(binOp(2, 3))
}
}
In one case we used one
binOp, in another we used another. We can define fold that implicitly accepts an instance of Monoid, and provides the required operation, but that's beyond the topic of this talk.3. Important Remark
We could probably start thinking, hmm, how about just parameterized types, what's the difference? Say, take
List[T], is not it a type class? We have abstract operations, independent of the type T, and so it is also not a specific type, but a class of types, right?Not exactly. It is a totally different thing, unfortunately written in the same style. Here we have a functor: given a type
T, we produce another type, List[T], uniquely determined by the type T, and whose operations (almost) do not depend on what is T.While we could make it into a type class, if the polymorphism here were ad-hoc, we normally do not.
4. That's Not It Yet
Next I'll show how we can restrict the scope of certain operations to certain subtypes, of the type that we pass as a parameter.
please correct me where I'm wrong
