A "class" in Haskell is a typeclass, sort of like a trait in Rust or an interface / abstract class in OO languages. An "instance" is a specific data type that satisfies the rules of the typeclass. The classic example is something like this:
class Eq a where
(==) :: a -> a -> Bool
instance Eq Integer where
x == y = <some native code>
That is, Eq is a class we can apply to any type a, as long as we have a way of defining the (==) operator, which takes two things of type a and returns a bool. We would like to say that Integer is an instance of this typeclass Eq.
You can use classes to express rules about multiple types, by just adding more type variables to the class definition. The Haskell wiki gives the example of matrix and vector multiplication, with "class Mult a b c", "instance Mult Matrix Matrix Matrix", and "instance Mult Matrix Vector Vector".
(One of the problems that comes up when doing this is that type inference doesn't know how to resolve overloaded types. FunctionalDependencies lets you add the "| a b -> c" syntax, which means "the type c in this typeclass is uniquely determined by whatever the type of list is, nobody can instantiate this typeclass twice for the same type of a and b". But don't let that syntax confuse you into thinking that a function, in the normal sense of something taking inputs and producing outputs, is being defined; it's just defining relationships between objects. almost Prolog-style.)
What he's doing is defining type classes for what us normal people would think of as functions. Nil and Cons are separate, unrelated types: in C++ terms, Nil would be class Nil {}, and Cons would be template <typename x, typename xs> class Cons {}. Keep in mind that x and xs are type arguments, not actual data members!
Then there are typeclasses with no functions; nothing needs to be implemented to be a member of the typeclass, but the type constraints need to be satisfied.
So we say that the two types a=Nil and b=Nil satisfy the "First" typeclass, and that the two types a=Cons x more and x also satisfy the "First" typeclass, for any type x (and any type more).
Then ListConcat gets to type constraints: the three types (Cons a as), bs, and (Cons a cs), taken together, satisfy the typeclass ListConcat as long as the three types as, bs, and cs also satisfy it. So now we're asking the type inference algorithm to start doing some recursion and probably some backtracking, but it's all hidden.
So on and so forth, with Peano integers and everything else, until we get to the meat of the queens problem: an instance of the 6-queens problem can be constructed if there are six queens not attacking each other.
Then he asks the typesystem to run type inference and figure out a plausible type for the 6-queens problem.
A "class" in Haskell is a typeclass, sort of like a trait in Rust or an interface / abstract class in OO languages. An "instance" is a specific data type that satisfies the rules of the typeclass. The classic example is something like this:
That is, Eq is a class we can apply to any type a, as long as we have a way of defining the (==) operator, which takes two things of type a and returns a bool. We would like to say that Integer is an instance of this typeclass Eq.You can use classes to express rules about multiple types, by just adding more type variables to the class definition. The Haskell wiki gives the example of matrix and vector multiplication, with "class Mult a b c", "instance Mult Matrix Matrix Matrix", and "instance Mult Matrix Vector Vector".
(One of the problems that comes up when doing this is that type inference doesn't know how to resolve overloaded types. FunctionalDependencies lets you add the "| a b -> c" syntax, which means "the type c in this typeclass is uniquely determined by whatever the type of list is, nobody can instantiate this typeclass twice for the same type of a and b". But don't let that syntax confuse you into thinking that a function, in the normal sense of something taking inputs and producing outputs, is being defined; it's just defining relationships between objects. almost Prolog-style.)
What he's doing is defining type classes for what us normal people would think of as functions. Nil and Cons are separate, unrelated types: in C++ terms, Nil would be class Nil {}, and Cons would be template <typename x, typename xs> class Cons {}. Keep in mind that x and xs are type arguments, not actual data members!
Then there are typeclasses with no functions; nothing needs to be implemented to be a member of the typeclass, but the type constraints need to be satisfied.
So we say that the two types a=Nil and b=Nil satisfy the "First" typeclass, and that the two types a=Cons x more and x also satisfy the "First" typeclass, for any type x (and any type more).
Then ListConcat gets to type constraints: the three types (Cons a as), bs, and (Cons a cs), taken together, satisfy the typeclass ListConcat as long as the three types as, bs, and cs also satisfy it. So now we're asking the type inference algorithm to start doing some recursion and probably some backtracking, but it's all hidden.
So on and so forth, with Peano integers and everything else, until we get to the meat of the queens problem: an instance of the 6-queens problem can be constructed if there are six queens not attacking each other.
Then he asks the typesystem to run type inference and figure out a plausible type for the 6-queens problem.
What's the runtime? Who knows.