juan_gandhi: (VP)
Spent 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:

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.

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 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
juan_gandhi: (VP)
Сидит Андрей Петрович Ощепков на крутом бережку Енисея и читает книжку "Гильбертовы Пространства в Задачах и Решениях"; подходит мужик, глядит на обложку, и спрашивает Андрея Петровича: "а шо це за параша, Гильбертовы Пространства?" 
/Эпиграф/

Итак, мой предыдущий пост я практически объявляю полной фигнёй.

Кроме одной фразы - type class - это класс типов. Остальное фигня.

Как я понимаю, класс типов можно определить а) параметрически: List[T] - это класс списков с элементами типа T; в хаскеле для этого есть лихой термин type family b) через уравнение:
class Eq a ...; в скале это можно задать приблизительно.

Сегодня Дэвид Анджеевски на скальном митапе вообще задвинул термин type class pattern, и на мой вопрос, не знает ли он формального определения тайпкласса сказал, что нет, не знает.

Вот ещё линки.
typeclassopedia, by John Kodumal, Atlassian - слов и примеров много, определения нет.
что сказал Дебасиш - это типа скорее паттерн тоже
Stackoverflow: какая польза от тайпклассов? ("а сёдла на них есть?")
Moors, Pissens, Oderski, "Generics of Higher Kind" - тут скорее намёки на тему тайпклассов, наряду с техничным рассуждением на тему шо в скале уже таки есть
"oop vs typeclasses" - по мне так скорее философия, с намёками, что, э, может быть таки тайпклассы - это параметризованные типы, не?

gentle haskell - здесь объясняют, что как раз не, объявляем через уравнения, а определяем или параметрически, или адхок.

Ну вы поняли, да? Я не понял. Только вижу, что тайпклассы - это что-то вроде многообразий, и не пора ли уже просто откровенно пойти пошукать шо за гомотопическая теория типов такая, и не отвечает ли она на вопросы.

Надеюсь на продуктивную дискуссию.
juan_gandhi: (Default)
Не о каких-нибудь там особо хитрых; в принципе, чуть ли не двоичных значений хватает, чтобы продемонстрировать.

Начнём, конечно, с Джавы. В которой сплошь и рядом, у "плохих программистов" встречается такое:
  if (message inscanceof CancellationMessage) { application.cancelnahren(); }
  else if (message instanceof EncouragementMessage) { galera.trabalha(); }
// etc


и хорошим программистам это не нравится, и они говорят "делегейшен давай", или "смартенумы давай!"

Делегейшен, это когда каждый параметр слишком широкого диапазона типов должен вдруг знать, что вот этот вот практически незнакомый тип однажды возьмёт да и обратится к ним, и надо для этого иметь особую форму (сиречь, сигнатуру), чтоб не подвести свой класс, а сделать, что положено (а там хоть не рассветай).

Ну или енум использовать - но енум контента не имеет, это константа... тогда люди ещё как поступают: в класс вставляют этот самый енум, "тип инстанса нашего класса".
  class Message {
    enum type {
      CANCEL,
      ENCOURAGE,
      DGAF} myType;
    ....
  }
...
  switch(message.type()) {
    case CANCEL: ...
    case ENCOURAGE: ...
    case DGAF: ...
  }


и это кошернее, чем было бы писать
  class mc = message.getClass();
  if (mc.equals(CancelMessage.class)) { ... }
  else if (....


В Скале же, на самом деле, не особо стесняются расписывать по классам, но на то есть другая причина: unapply, а ещё лучше сказать, линза (обратная сторона); с помощью её можно устраивать сравнение по образцу и, в зависимости от типа, выполнять какие-то действия с параметрами конструктора.
  message match {
    case CancelMessage(timeout: TimeInSeconds) => app.cancelato(timeout)
    case EncourageMessage(text: String) => galera.listen(text); galera.trabalha
    ...
  }


Фактически эта конструкция в некотором смысле помещает исполяемый, специфический для класса параметра, код немножко в контекст этого класса (видны только параметры конструктора).

В Скале есть немножко тенденция некоторые классы объявить более равными, например Option[T], Either[Left,Right] - для них как бы некошерно употреблять кейсы, а надо использовать функциональную функцию map. В принципе, скальные библиотеки любят возвращать Option[T], и тут-то бы и применять map, да штука в том, что в случае None ничего ни к чему применяться не будет. Так что приходится расписывать кейс. И со списками, что характерно, кейс приходится писать: как правило, разбивая ситуацию на два случая - пустой список или голова с хвостом, неважно, пустым или нет.

Так же и на Хаскеле - или мы матчим список, или Maybe, или data type.

И вот это вот "перечисление случаев" меня как-то смущает; нельзя ли для этого дела пристроить что-то вроде map? Но блин, это ж надо передавать, вообще говоря, по специальному исполнителю на каждый отдельный жизненный случай. Как в Джаве любят писать - лисинеры, listeners - они будут теперь здоровкаться на каждый чих.

Это практически cps, continuation passing style. Как в Джаваскрипте, если вы ещё помните, что такое xhr, а не вызываете что-нибудь там вроде JQuery.doAjaxForMeHurry(), то у вас как правило два-три таких слушателя: - пока читает, - когда закончили, - если ошибка. А могли бы написать (если б могли)

  reset {
    switch {
      case STILL_READING: ...; break
      case GOT_RESULT: ...; return
      case ERROR: ...; return
    }
    shift(k) {
      do {
        var resp = XHR.doPost(myStuff)
        k(resp)
      }
    }
  }


Это было бы почти идеальное решение, да?

Не знаю, не знаю.

Profile

juan_gandhi: (Default)
Juan-Carlos Gandhi

August 2025

S M T W T F S
      12
3456789
10 11 1213141516
17181920212223
24252627282930
31      

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 12th, 2025 07:49 pm
Powered by Dreamwidth Studios