Difference between Type Class and Algebraic data types

Question

As I understand the Type Class is that it's not something concrete but just a construct for ad-hoc and parametric polymorphism. Eq and Semigroup are examples of type classes. On the other hand, there is Algebraic data type, which is a concrete composite type, for example, Either and Maybe. And they are also Functors.

So, there is a specification for Algebraic data types for JavaScript: https://github.com/fantasyland/fantasy-land. On this page, Setoid(Eq), Ord and Semigroup are also ADT. But is it correct? If so, they are composite of what types?

I also find out this article regarding type classes, and here Functors and Monads are type classes. https://typelevel.org/cats/typeclasses.html#type-classes-in-cats. And, is it means that Either and Maybe are type classes as well?

Is Eq a type class or algebraic data type? Or both? Same for Functor

Answer 1

We collect data (values, terms) into types (data types). We can collect types into type classes.

1, "a", true, Some(1), None, ... are values. They belong to types, Int, String, Boolean, Option[Int], ... Types can belong to type classes, Eq, Ord, Functor, ...

ADT (algebraic data type) is a data type constructed via sum and product

// Scala
sealed trait MyTrait
case class MyClass1(i: Int, s: String) extends MyTrait
case class MyClass2(b: Boolean) extends MyTrait

-- Haskell
data MyTrait = MyClass1 { i :: Int, s :: String } | MyClass2 { b :: Bool }

Here MyTrait is a sum of MyClass1 and MyClass2. MyClass1 is a product of Int and String. MyClass2 is a product of single multiplier Boolean.

There are also data types that are not ADT. E.g. function types A => B, union types A | B, intersection types A & B or A with B, existential types, etc. Scala ADT are automatically generalized ADT (GADT) in Haskell terminology. There are generalizations of ADT in dependently typed languages, Sigma- and Pi-types (i.e. dependent sum and product).

Type classes is FP way to describe a behavior (via ad hoc polymorphism, early binding, static/compile-time dispatch). We can make a type an instance of a type class

// type class
trait MyTypeclass[A] {
  def foo(a: A): Unit
}
object MyTypeclass {
  // instances
  implicit val myTraitMyTypeclass: MyTypeclass[MyTrait] = new MyTypeclass[MyTrait] {
    override def foo(a: MyTrait): Unit = a match {
      case MyClass1(i, s) => println(s"MyTrait: MyClass1: i=$i, s=$s")
      case MyClass2(b)    => println(s"MyTrait: MyClass2: b=$b")
    }
  }
  implicit val myClass1MyTypeclass: MyTypeclass[MyClass1] = new MyTypeclass[MyClass1] {
    override def foo(a: MyClass1): Unit = println(s"MyClass1: i=${a.i}, s=${a.s}")
  }
  implicit val myClass2MyTypeclass: MyTypeclass[MyClass2] = new MyTypeclass[MyClass2] {
    override def foo(a: MyClass2): Unit = println(s"MyClass2: b=${a.b}")
  }
}

class MyTypeclass a where
  foo :: a -> IO ()
  
instance MyTypeclass MyTrait where
  foo (MyClass1 i s) = print ("MyClass1: i=" ++ show i ++ ", s=" ++ show s)
  foo (MyClass2 b)   = print ("MyClass2: b=" ++ show b)

Here MyClass1, MyClass2, MyTrait (in Haskell only MyTrait) are types, they are instances of the type class MyTypeclass.

An alternative to typeclasses (another way to describe a behavior) is OOP inheritance (via subtyping polymorphism, late binding, dynamic/runtime dispatch)

sealed trait MyTrait {
  def foo(): Unit
}
case class MyClass1(i: Int, s: String) extends MyTrait {
  override def foo(): Unit = println(s"MyClass1: i=$i, s=$s")
}
case class MyClass2(b: Boolean) extends MyTrait {
  override def foo(): Unit = println(s"MyClass2: b=$b")
}

We can lift an ADT into a type class. For example standard ADT

sealed trait Option[+A]
case class Some[+A](a: A) extends Option[A]
case object None extends Option[Nothing]

data Maybe a = Just a | Nothing

can become a type class and its instances

trait Option[A]

case class Some[A](a: A)
case object None
type None = None.type

implicit def someOption[A]: Option[Some[A]] = new Option[Some[A]] {}
implicit val noneOption: Option[None] = new Option[None] {}

class Maybe a
 
newtype Just a = Just a
data Nothing a = Nothing
 
instance Maybe (Just a)
instance Maybe (Nothing a)

On this page, Setoid(Eq), Ord and Semigroup are also ADT. But is it correct? If so, they are composite of what types?

Normally, Eq, Ord, Semigroup are not ADT. They are not constructed via sum and product. They are type classes. They describe behavior, namely how to compare elements for equality, how to compare them for order, how to add elements, what is unit element. They "consists" of all types declared as their instances, e.g. Int, String etc. (i.e. where the corresponding behavior is implemented in some specific way).

is it means that Either and Maybe are type classes as well?

Normally, Either and Maybe are not type classes, they are ADT. But if we really want we can lift ADT into a type class as I showed above.

Is Eq a type class or algebraic data type? Or both? Same for Functor.

Eq and Functor are type classes, not ADT.

Answer 2

Algebraic Data Types and typeclasses are both "things with multiple types", and I think that's what's confusing you. I think the reason we're having a hard time answering your question (or even figuring out precisely what it is) is because other than that they have almost nothing in common.

A typeclass could be thought of as a contract or specification. It exists independently of any concrete type and they are open: and any type you come up with could implement the necessary details to be a member of the set. We specify this in different ways in different languages that include this concept.

For instance Rust traits like Display:

use std::fmt;

struct Foo(i32);

impl fmt::Display for Foo {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

Or Haskell typeclases like Show:

data Foo = Int deriving Show

We have created in both cases a very basic type Foo based on the integer type that implements the "has a string representation" typeclass in the respective languages. As I said before the set of types that implement Show/Display is open: we can do this forever with any applicable type we come up with.

Contrast that with Maybe, which is a tagged union (which qualifies it as an Algebraic Data Types) Just a | Nothing for some type a. The set of types in the Maybe union is closed: you can use any type a you want but you can't add new things to the union.

Maybe is a type (or to be more precise, a type constructor), not a typeclass. It's meaningless to say that Foo implements/derives Maybe. Maybe is not a set of rules for some other type to follow, anything could be a Maybe Whatever.

But Maybe as a type does implement some typeclasses, for instance the Monad typeclass (and by implication Functor, Applicative, etc.). It is not meaningless to say that Maybe implements the Monad specification.

Answer 3

The underlying root of your confusion is distinguishing concepts from implementations.
So let's try to make some of those clearer.

Typeclasses

Is a pattern to achieve polymorphism; punctually, ad-hoc polymorphism.

In some languages those are a feature provided by the language; e.g. Haskell or Rust.
Others, allow you to express them using other features; e.g. Scala using implicits, meaning that they are values in this language while they aren't in Rust (AFAIK)
And finally, in theory, you may model them in any language, but you would need to pass the instances manually, this is what is usually called the strategy pattern; an example is Java's Comparator. Some folks argue that if the value has to be passed explicitly then is not a typeclass, I personally disagree but let's not open that pandora's box.

Algebraic Data Types (ADTs)

Is a pattern to model data based on simple constructors known as products and unions.

Again, some languages provide the building blocks for those out of the box, like Haskell. Some others emulate them upon classic subtyping and objects with some help from the compiler, like Scala.
And, once again, you may in theory model them in any language and replace pattern matching with a fold. But, in this case, I do agree that if the UX is not pleasant and you don't have pattern matching built-in in the language is hard to talk about ADTs.

Functor

Is an abstraction, a concept derived from category theory.
In essence, it is constituted of three things:

• A type F[_] of kind * -> * (commonly know as type constructors); e.g. List
• An implementation of map[A, B](fa: F[A])(f: A => B): F[B] for the given type F
• A formal proof that such implementation satisfies the Functor laws.

I won't attempt to explain what a Functor is here...
But, a quick TL;DR; is that it represents the possibility of transforming some context by applying a function to the value(s) it will compute.

Since a Functor is an abstraction, we need some form of polymorphism to represent it. Experience has shown us that typeclasses are the most natural way to model Functor, Monad, Monoid, etc. But, you may try to use other approaches like structural types or subtyping... but really, you will hit a wall sooner than latter.

Extras

On top of all that, we also need to add other layers of indirection that each language may have.
For example, in Scala we use subtyping to model typeclasses hierarchies, so Monad[F] extends Functor[F], and the same keyword to model both subtyping abstractions and typeclass abstractions trait.

So again, it is important to always separate concepts / ideas from their underlying implementations; at the end of the day, everything will be just electrical pulses on a weird machine :p