preface

As a Java developer, the concept of class is familiar, but there are other types of classes on the other side of the mountain.

A classic question

In programming, it is often necessary to determine whether two values are equal, and for a long time there is no standard solution to this problem, which is the classic judgment and other problems.

I use the word “value” uniformly here instead of objects, basic types, and so on to simplify communication

In Java, we can use == and equals to determine whether the values are equal

public void test(a) {
    boolean res = "hello"= ="world";
  
    boolean res2 = "hello".equals("hello");

    boolean res3 = 3= =3;

    boolean res4 = 5= =9;
}
Copy the code

If you’re familiar with Java, you’ll know that the default implementation of the equals method for non-basic types is to call the == operator, which compares the reference address of an object

public class Object {
  / /...
  
  public boolean equals(Object obj) {
  	return (this == obj);
  }
  
  / /...
}
Copy the code

All classes will have an equals method because in Java all types are subclasses of Object by default.

In fact, this is also the Java language to deal with the decision and other problems of the solution, that is, unified from Object inheritance of the decision and other methods.

But for a purely functional language like Haskell, which doesn’t have the concepts of inheritance, classes, and so on in OOP, how does it elegantly solve this problem?

If Haskell is new to you, let’s ask a different question: Is there any general design solution that can solve this kind of problem?

Of course, Type classes are the most beautiful ones in the field. To understand Type classes, you have to start with polymorphism.

Type classes and polymorphism

Type classes combine ad-hoc polymorphism with Parametric polymorphism to achieve a more general overloading.

The question is, what is AD hoc polymorphism, parameterized polymorphism?

For more on polymorphisms, see my previous article, “I don’t know what to talk about.”

  • Ad-hoc polymorphism means that a function will behave differently (or behave differently) as it applies different types of parameters

    The most typical is arithmetic overloading

    3 * 3  // represents the multiplication of two integers

3.14 * 3.14 // represents the multiplication of two floating point numbers
Copy the code

  • Parametric polymorphism means that a function is defined on some type, for which the implementation is the same.

    For example, the size() function for List[T] has the same implementation whether T is of type String or Int

    List[String].size()
List[Int].size()
Copy the code

Although Type classes combine the two types of polymorphism, they themselves fall under the category of ad-hoc polymorphism.

If you want to learn more about the idea of type classes, it’s highly recommended to read the paper “How to Make Ad-hoc polymorphism Less AD Hoc,” which is kind of the opening chapter of Type classes.

Haskell and Type classes

Haskell has introduced and implemented Type classes, so it’s important to learn about Haskell’s Type classes.

Let’s take a look at how Haskell uses Type classes to solve this problem.

First we define a Type class with the keyword class, which should not be confused with Java classes.

class Eq a where
	(==) :: a -> a -> Bool
	(/=) :: a -> a -> Bool
Copy the code

/= = =

Haskell’s Type class is similar to Java’s Interface. The Eq class above defines two abstract functions: == and /=, where a is a Type variable, similar to generics in Java.

From this point of view, Type classes are just abstractions of common behaviors whose implementations vary from Type to Type and are defined by Type class instances.

Using the instance keyword, you can create an instance of a type class. The following shows an instance of a type Eq class for Float and Int

instance Eq Int where
	(==) = eqInt
	(/=) = neInt
	
instance Eq Float where
	(==) = eqFloat
	(/=) = neFloat

Copy the code

We assume that eqInt, neInt, eqFloat, and neFloat are already implemented by the standard library

This allows you to calibrate Int and Float directly using the == and /= functions

Int = Int; Int = Int= =1 2/ =2 4

-- Determine the equality of Float= =1.2 1.2/ =2.4 2.1
Copy the code

When the == or /= function is called, the compiler automatically finds an instance of the type class based on the argument type, and then calls the function of the type class instance to perform the call.

If the user needs to customize the function, he can only implement his own type class instance.

At this point, you might be tempted to make a comparison with the inheritance scheme mentioned at the beginning. I have drawn two graphs for reference

  • The type structure of inheritance schemes is hierarchical

  • The Type structure of the Type classes scheme is linear

They are as different from each other as Comparable and Comparator, if only in terms of structure.

Scala and Type classes Pattern

Currently Java cannot implement Type classes, but multi-paradigm Scala, which is also a LANGUAGE of the JVM, can.

Unlike Haskell, Type classes are not first class citizens in Scala, that is, there is no direct syntax support, but we can implement Type classes with the help of a powerful implicit system, and because the steps are more formulaic, This is also called Type classes Pattern.

There are three steps to implement Type classes Pattern in Scala

  1. Define the Type of the class
  2. Implement the Type class instance
  3. Defines a function that contains implicit parameters

Once again, follow the pattern steps summarized earlier to implement a Scala version of the Type Classes solution with the aforementioned determination problem.

The first step in defining a Type class is to define a trait with generic parameters

Traits are similar to Java interfaces, but more powerful

trait Eq[T] {
  def eq(a: T, b: T) :Boolean
}
Copy the code

We then implement two instances of the class type String and Int

object EqInstances {

  implicit val intEq = new Eq[Int] {
    override def eq(a: Int, b: Int) = a == b
  }

  implicit val stringEq = instance[String]((a, b) => a.equals(b))

  def instance[T](func: (T.T) = >Boolean) :Eq[T] = new Eq[T] {
    override def eq(a: T, b: T) :Boolean = func(a, b)
  }
}
Copy the code

StringEq and intEq are constructed in different ways

  • I constructed the stringEq instance using a Java-like anonymous class
  • IntEq instances are implemented using higher-order functions

Both examples are modified with the keyword implicit, commonly called implicit values, which we’ll talk about later.

As a final step, we implement a same function with an implicit argument that calls an instance of the type class to determine whether two values are equal

object Same {
  def same[T](a: T, b: T) (implicit eq: Eq[T) :Boolean = eq.eq(a, b)
}

Copy the code
  • implicit eq: Eq[T]Is the implicit parameter,The caller does not have to pass in actively; the compiler will look in scope for a matching implicit value passed in(This is why the previous instance needs to be implicit.)

Finally, to verify the call, we need to import the instances of the type class in the current scope using the import keyword (mainly so that the compiler can find them).


import EqInstances. _Same.same(1.2)

Same.same("ok"."ok")

// Compile error: no implicits found for parameter eq: eq [Float]
Same.same(1.0F, 2.4F)
Copy the code

As you can see, calls to same for Int and String compile, but when the argument is Float they produce a compilation error because the compiler does not find an Eq instance in scope that can handle Float.

More rules about implicit lookups in Scala can be found at docs.scala-lang.org/tutorials/F…

That’s pretty much it, but it’s not very elegant in Scala, and we can optimize it with a few tricks

  • Change the same function to the apply function to simplify the call

  • Use context bound to optimize implicit parameters. Don’t panic, context bound is just syntax sugar

object Same {
  def apply[T: Eq](a: T, b: T) :Boolean = implicitly[Eq[T]].eq(a, b)
}

// Use apply as a function. You can call it without writing the function name
Same(1.1)
Same("hello"."world")
Copy the code

Just to talk about the context Bund, first of all, the definition of the generic is changed from T to [T: Eq], so you can use IMPLICITLY [Eq[T]] to let the compiler find an implicit instance of Eq[T] in scope, and context bound makes function signatures more concise.

In Scala, type class design is ubiquitous, typically Ordered.

Looking back to the Java

We only realize that this is a different solution to OOP inheritance. Let’s go back to Java and do some other comparisons.

Take the Comparator[T] interface as an example, which is often used in Java in the Collections framework

List<Integer> list = new ArrayList<>();
list.sort(Comparator.naturalOrder())
Copy the code

If you make it Type classes

trait Comparator[T] {
  def compare(o1: T, o2: T) :Int
}

object Instances { 
  implicit val intComprator = new Comparator[T] {
    def compare(o1: Int, o2: Int) = o1.compareTo(o2)
  }
  
  / /... other instances
}
Copy the code

The List sort method also needs to be changed to the front of the implicit argument method, so we don’t need to pass the Compartor instance to the display

// The Comparator[Integer] instance is automatically found at compile time
List[Integer] list = new ArrayList< > (); list.sort()Copy the code

Think of the above Type classes as pseudo-code based on Scala syntax

As you can see, the biggest difference between Java’s Comparator scheme and Type Classes is that Java needs to manually pass in a Comparator instance.

Don’t underestimate the difference between the two. The difference between the two is like defining a type with var

// Java8
Map<String, String> map2 = new HashMap<>();

// Java10
var map = new HashMap<String, String>();
Copy the code

If the type system can do something for you, let it do it for you.

To summarize

After looking at the Haskell and Scala examples, it’s time to conclude:

Type classes abstract the common behaviors of certain types, and when a Type needs these behaviors, it is up to the Type system to find the concrete implementation of these behaviors.

To be continued

In Scala3, Type classes get enough attention, directly provide syntax level support, no longer need to write a lot of template code, from now on can be called Type classes without Pattern.

But to avoid a “long story,” save the relevant content for the next post (like, like, like).

Can you still learn from a weak skin?

reference

  1. How to Make Ad-hoc polymorphism Less AD hoc
  2. Of Scala Type Classes
  3. Where does Scala look for implicits?
  4. Scala implicit parameters
  5. Type classes for the Java Engineer
  6. OOP vs type classes
  7. Cats: Type classes