juan_gandhi | and more on type classes in Scala

Entry tags:

and more on type classes in Scala

This part is not exactly a theory of algebraic theories, but anyway.

Imagine we have a parametric class (e.g. List[X]) for which we would like to define methods that would only work if X satisfies certain conditions. E.g. define sum if it is a numeric type, or define flatten if it is some kind of sequence (Traversable[Y] would be enough). How can we accomplish it in Scala?!

Suppose we want to declare flatten

trait List[X] {
// bla-bla-bla

  def flatten[X <% Iterable[Y]] { ... } // no way, we already mentioned X; this one would shadow the previous one
// OOPS!
}

The trick would be to have an implicit transformation handy that transforms X into Iterable[Y] for some Y; and define it so that if X is actually some kind of Iterable, the implicit would be available, and otherwise not available.

Where can we find such a general transformation? The only thing that comes up to mind is an identity:

implicit def itsme[Y, X <% Iterable[Y]](x: X): Iterable[Y] = x

This would be enough in this specific case... but then we would have to define another one for numeric types, and so on.

We can go generic, and write something like this:

abstract class SafeToCast[-S, +T] extends Function1[S, T]
implicit def canCast[X <% Y, Y]: SafeToCast[X, Y] = new SafeToCast[X,Y] { def apply(x:X) = x }

Now we can define flatten, like this:

class List[X] { ...
  def flatten[Y](implicit transformer: SafeToCast[X, Iterable[Y]]) { ... }
}

All the conditions are satisfied now. Contravariance in the first argument and covariance in the second argument ensure that a subtype can be cast to its supertype... to be more precise, an instance of supertype can be substituted by an instance of subtype.

The only thing is that we can try to make the code more readable, by refactoring.

Step 1. Use the trick in Scala that binary operations can be written in an infix way, even for types. E.g. you can declare val map: (String Map Int) - this is the same as Map[String, Int].

sealed abstract class SafeToCast[-S, +T] extends Function1[S, T]
implicit def canCast[X <% Y, Y]: (X SafeToCast Y) = new (X SafeToCast Y) { def apply(x: X) = a }
...

class List[X] { ...
  def flatten[Y](implicit transformer: X SafeToCast Iterable[Y]) { ... }
}

Step 2. Rename the method, giving it a more "type-relationship" name: SafeToCast -> <:<.

sealed abstract class <:<[-S, +T] extends Function1[S, T]
implicit def canCast[X <% Y, Y]: (X <:< Y) = new (X <:< Y) { def apply(x: X) = a }
...

class List[X] { ...
  def flatten[Y](implicit transformer: X <:< Iterable[Y]) { ... }
}

That's the trick.

(if you have questions, ask; if you have corrections, please tell me)

Flat | Top-Level Comments Only

Че-то всё не по-русски?

Я уже лет тридцать как на такие темы предпочитаю рассуждать по-английски. И Вам советую освоить, если Вы хотите программировать профессионально.

а потом вдруг появилсь?

:) Русские буквы не пропадут!

А какой у флаттена тут возвращаемый тип?

Скажем, Iterable[Y]?

Я бы в честь этого хотел бы отметить две техники, которые делаются возможными благодаря имплиситам.

Первая - то, что при помощи имплиситов можно разрешать или запрещать типы. Скажем, если ожидаемый тип результата вызова флаттена не подходит ни под один имплисит, то будет ошибка компиляции. Это отлично описано в посте.

Но есть еще и вторая. Если ожидаемый тип (pt в терминологоии тайпера) неизвестен, то имплисит серч позволяет его вывести!! Именно таким образом работает CanBuildFrom, позволяя мапу над строками возвращать строки, а мапу над листами - листы. И все это при помощи только одного определения функции map (в плане, достаточно определить map в базовом трейте коллекций и потом ничего нигде оверрайдить не придется - нужные типы будут выводиться автоматом для каждоо конкретного случая как надо).

Edited 2013-01-24 08:07 (UTC)

а чё вот так: http://ivan-gandhi.livejournal.com/2213417.html?thread=28781865#t28781865 - хорошо бы, чтобы компилятор допонимал

Да! Но я постремался усложнять этот пост; тут типа одна тема раскрыта.

scala> sealed abstract class <:<[-S, +T] extends Function1[S, T]
defined class $less$colon$less

scala> implicit def canCast[F <% T, T]: (F <:< T) = new (F <:< T) { def apply(a: F): T = a }
canCast: [F, T](implicit evidence$1: F => T)<:<[F,T]

scala> case class L[X](val x: X) { def double[Y](implicit transformer: X <:< Int) = x*2 }
defined class L

scala> L(42).double
res16: Int = 84

scala> L("a").double
<console>:26: error: diverging implicit expansion for type <:<[String,Int]
starting with method canCast
              L("a").double

А вот с

implicit def canCast[F <: T, T]: (F <:< T) = new (F <:< T) { def apply(a: F): T = a }

уже не работает…

P.S. Сорри за множественные правки: сначала больше-меньше побилось в html, затем заметил, что лишний кусок прихватил.

Edited 2013-01-24 07:15 (UTC)

О, спасибо, конечно <%

алсо,

case class L[X](val x: X) { def double[_ >: X <: Int] = /* safe to cast now */ (x.asInstanceOf[Int])*2 } жаль, конечно, что скала не умеет умозаключить, что X - субкласс Int из экзистенциального баунда на _.

У нас констрейнты на type vars весьма ограниченные + очень локальные (одно из размышлений на эту тему с участием Мартина и Спивака: http://pchiusano.blogspot.ch/2011/05/making-most-of-scalas-extremely-limited.html).

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

Конкретно по деталям реализации, есть символ X, у него есть сигнатура, однозначно определяемая его дефинишеном и никак не изменяемая. Types.isSubType определен в scala-reflect.jar, т.е. он ничего не знает про контексты тайпчекера, определенные в scala-compiler.jar, т.е. единственное, что он может сделать - спросить у символа сигнатуру => фейл.

спасибо.

а почему implicit вот такого вида не работает:

implicit def safeCast[X,Y, _ >: X <: Y]( x:X ):Y = x.asInstanceOf[Y]
case class L[X](val x: X) { def double[_ >: X <: Int] = x*2 }

Edited 2013-01-24 11:56 (UTC)

Можно, пожалуйста, полный сниппет, который не компилируется? Я, если честно, не понял, куда safeCast должен примениться в твоем примере.

Edited 2013-01-24 12:03 (UTC)

он должен был попасть в x*2, заменяя x.asInstanceOf[Int], который был изначально.

http://ideone.com/bpLenc - не компилируется; говорит, x не Int

http://ideone.com/MlYeRN - всё в порядке, но и каст explicitly

Edited 2013-01-24 12:31 (UTC)

Вот, что пишет -Xlog-implicits:

13:33 ~/Projects/Kepler_snippet00/sandbox (topic/snippet00)$ scalac -Xlog-implicits Test.scala 
Test.scala:3: safeCast is not a valid implicit value for L.this.x.type => ?{def *: ?} because:
inferred type arguments [X,L.this.x.type,X] do not conform to method safeCast's type parameter bounds [X,Y,_ >: X <: Y]
  case class L[X](val x: X) { def double[_ >: X <: Int] = x*2 }

Сейчас подумаю, почему так.

Edited 2013-01-24 12:35 (UTC)

Ну в плане оно-то да, что X это не подтип x.type. Но почему оно x.type не расширяет до X - это от меня ускользает. Если не лень, можешь спросить вот тут: http://groups.google.com/group/scala-language.

переписываем, чтобы не было путаницы с X

    implicit def safeCast[Z,Y, _ >: Z <: Y]( z:Z ):Y = z.asInstanceOf[Y]
    case class L[X](val x: X) { def double[_ >: X <: Int] = x*2 }

safeCast is not a valid implicit value for L.this.x.type => ?{val *: ?} because:
incompatible: (z: X)X does not match expected type L.this.x.type => ?{val *: ?}
safeCast is not a valid implicit value for => L.this.x.type => ?{val *: ?} because:
incompatible: (z: X)X does not match expected type => L.this.x.type => ?{val *: ?}

а почему он говорит (z: X)X? Это он о чём? Что Z и Y ему одним типом кажутся в том контексте?

Ок, поспрашиваю.

Edited 2013-01-24 12:57 (UTC)

Стоп, подожди. А откуда компилятору знать, что у X есть мембер *?

Он говорит (z: X)X потому, что это сигнатура метода safeCast с выведенными аргументами.

Причем здесь сигнатура? Когда компилятор не находит мембера, он ищет имплисит конвершн, преобразующий ресивер в нечто, что содержит нужный мембер. Как вот тут: implicit value for L.this.x.type => ?{val *: ?}.

Так как у Y нет мембера * (в силу того, что тот экзистенциальный тип, как мы выяснили, не влияет на тайп инференс), то соответственно safeCast не соответствует нужной сигнатуре.

Edited 2013-01-24 13:08 (UTC)

ну это совсем странно. или не очень понятно.

    implicit def safeCast[Z,Y, _ >: Z <: Y]( z:Z ):Y = z.asInstanceOf[Y]
    def asInt( x: Int ): Int = x
    case class L[X](val x: X) { def double[_ >: X <: Int]: Int = asInt(x)*2 }

a.this.safeCast is not a valid implicit value for X => Int because:
incompatible: (z: X)X does not match expected type X => Int
a.this.safeCast is not a valid implicit value for => X => Int because:
incompatible: (z: X)X does not match expected type => X => Int
...(и ещё куча)

тут уже я даже сказал, чему x должен быть равен. На входе в asInt должен быть Int, почему не пробует safeCast с Z=X, Y=Int?

тут ещё оказывается, что несмотря на одинаковый синтаксис, в double[ _ >: X <: Int ] запись интерпретируется по другим законам, не связанными с existential types. (не компилируется перезапись по "законному" раскрытию того типа: double[ T forSome { type T >: X <: Int } ])

внезапно.

А, точно. Так же гораздо проще.

     case class L[X](val x:X) {
        def double[P >: X <: Int]: Int = (x:P) * 2
    }

(this scala awesomeness brought to you courtesy of Roland Kuhn)

(всё ещё жаль, что не догадывается, что x is Int, но уже значительно лучше!)

Funny, how much effort it took to figure out this specific format.
And it involved great minds, too. :)

Great to listen to great minds!

But frustrating that you need to know which way will work (vs which way is correct)

define methods that would only work if X satisfies certain conditions

Что конкретно должно происходить, когда вызывается метод, который не работает? И что сделает реальный программист в таком случае?

не компилируется.

e.g. List[String].sum не откомпилируется.

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

Не то, чтобы я не видел подобного в реале, но просто интересны предположения тех, кто такое позволяет.

Скажет, что не найден имплисит. Такие сообщения можно кастомизировать при помощи аннотации на классе имплисита: https://github.com/scalamacros/kepler/blob/18a906bb9a6c6b50d286ca76f219a5b351514ae4/src/library/scala/collection/generic/CanBuildFrom.scala#L28.

Насколько я понимаю английский, "cannot construct" это немного не то же самое, что "не найден". Так что действия после обнаружения ошибки будут совсем не те, что предполагают жители башни из слоновой кости.

Type-level программирование это непростая вещь, поэтому, мне кажется, не стоит ожидать от обычного пользователя того, что он сможет починить такого рода ошибку самостоятельно. Поэтому, на мой взгляд, понятное сообщение об ошибке важнее подлежащих технических деталей.

С другой стороны, более продвинутые программисты, которые в курсе имплиситов и их применимости для обсуждаемых задач, будут в курсе и насчет кастомных сообщений об ошибках, так что их это в заблуждение не введет. На крайний случай есть -Xlog-implicits.

Хочу отдельно сконцентрировать внимание на то, что имплиситы, обсуждаемые здесь, нельзя случайно забыть импортировать - они всегда в скоупе при помощи механизмов, описанных в гугле по ключевым словам implicits without import tax. Поэтому тут либо коллекция поддерживает сумму по элементам, либо не поддерживает и ее надо допиливать, что явно за пределами возможностей обычных пользователей.

не стоит ожидать от обычного пользователя

Оп-с. С каких времён мир разделился на "обычных пользователей" и "продвинутых программистов"? Практика показывает, что предполагать наличие каких-то особых качеств у людей - это очень опрометчиво.

что явно за пределами возможностей обычных пользователей

Ха.

Сложно - это правильно расширить, сохранив логику и ясность. "Обычные пользователи" допилят как смогут.

Стандартная ситуация: сделать надо было вчера и есть крутой алгоритм, найденный гуглом. Скопировали, поменяли что надо, а оно не компилируется. Дальше начинается индийские танцы. Потом придётся удивляться результатам сложения элементов списка, содержащего числа, даты и строки.

Когда я писал про "обычных пользователей" и "продвинутых программистов" я имел ввиду что-то похожее на вот это: http://www.scala-lang.org/node/8610. Не вижу ничего страшного в том, что есть программеры, чье владение Скалой в текущий момент не позволяет им заниматься type-level программированием. Все там были - почему бы не попробовать оптимизировать экспириенс менее опытных товарищей?

Это теория. Практика гораздо печальнее.

А как бы вы сделали сообщение об ошибке в обсуждаемом случае?

Я бы не создавал случая, когда вещи называются одним и тем же именем, а ведут себя принципиально по-разному. И с неявными преобразованиями я бы не игрался. Тайные знания как правило ни к чему хорошему не приводят.

Везде есть компромиссы. В Сишарпе, например, Filter/Select/итд возвращают IEnumerable вне зависимости от типа коллекции. У нас в Скале для листа вернется лист, для вектора - вектор, для мапы - мап. Мне неочевидно, что увеличение подкапотной сложности не оправдывается достигаемым удобством.

Одному надо в список добавить элемент со строкой, другому - сосчитать сумму. При явных преобразованиях они не договорятся. При неявных - намутят где-то в глубинах и создадут фигню.

Сишарп я бы за пример не брал.

Implicit search это, в основном, про type-level пролог, а не про неявные преобразования. К счастью, implicit conversions все больше и больше становятся дурным тоном в сообществе Скалы.

Вот как, например, было в посте:

implicit def canCast[X]: SafeToCast[X, X] = new SafeToCast[A,A] { def apply(a: A) = a }

Здесь implicit определение выражает то, что можно скастовать любой тип сам в себя. Никто никого не преобразовывает, просто на основе фактов, указанных таким образом, тайпчекер выдает ответ: "да, подходит" или "нет, не подходит".

Там на рассылке интересный момент выясняется.

В хаскелле экзистенциальные типы и rank-N полиморфизм выражаются с помощью (forall blah . P blah => ...), что на деле выражается в виде функции с неявным параметром, который в точке вызова конструируется неявно же, и является ничем иным как словарём функций.

В скале, собственно, происходит то же самое - неявный параметр, в точке вызова конструируется неявно, и является ничем иным как словарь функций = object. Под таким углом как-то виднее, почему такое ударение на имплиситы по сравнению с экзистенциальными констрейнтами.

С одной стороны, какой-то сумбур, путаница с иерархией классов дополнительно к путанице с имплиситами. С другой стороны, как раз решение проблемы неявной передачи словаря, которую в хаскеле решить ...скажем, не так удобно. (Как сообщить, какой именно моноид на Int? в скале - либо локально импортируй один из моноидов, либо передавай явно)

ага, а чё я, собственно, это всё говорю. Если имплиситы всё более дурным тоном считается, то что ему на замену хорошим тоном считают?

Edited 2013-01-28 19:08 (UTC)

Я уверен, что имплиситы считают дурным тоном те, кто их готовить не умеет. Это примерно как жалобы тупых на джавные дженерики (есть ещё правильные жалобы, но тупые джавщики даже слов таких не знают, как variance and higher order).

Я имел ввиду исключительно implicit conversions. Мы в Scala compiler team всеми силами их избегаем.

Edited 2013-01-28 19:44 (UTC)

Может быть, в компиляторе они и моветон; а в жизни написать sleep(10 seconds) - милое дело.

Это implicit classes. Их тоже можно. Их даже SIP-18 разрешает :)

Я скорее имею ввиду няшечки типа неявных преобразований из String в TermName или TypeName для удобства вызова функций, которые принимают имена. В итоге потом местами очень затруднительно понять, где имена, где строки, а где включился умный конвершн и, например, сломал сравнение на равенство. И живучие же эти конверсии - до сих пор еще, вроде бы, не отовсюду из компилятора вычистили.

Ну мне из эстетических соображений forSome {...} кажется то ли приятнее, то ли понятнее.

Более явно, что ограничение является compile-time, что ли.

ну от чего-же. Для обладателя тайных знаний - к job security, пока не найдут 100500 индусских программистов способных расковырять тайные знания.

Касательно самого понятия "сложность", у меня нет однозначного мнения. С одной стороны, хотелось бы, чтобы вещи вроде [1] писались на раз-два. С другой, стороны, может, такие задачи просто сами по себе очень сложны, поэтому вполне естественно, что не всегда получится бац-бац и в продакшен [2].

[1] http://yz.mit.edu/wp/true-scala-complexity/
[2] http://news.ycombinator.com/item?id=3443436 (см. коммент Мартина)

Я пытаюсь прикинуть, что получится в реальной ситуации. И получающееся мне совсем не нравится.

(см. коммент Мартина)

Идём по ссылке и ищем "martin". Потом размышляем над результатом.

Вот именно об этом я и говорю.

Я не очень понимаю, о чем именно вы говорите. Если поясните, буду благодарен.

Мартина там нет. И кто такой Мартин можно узнать только, если поднять какой-то левый контекст, на который ссылок нет.

Короче говоря, кто-то передаёт список, кто-то пишет библиотеку. При соединении в коде это то работает, то не работает. Эксперт долго и нудно ищет причину, а потом громко ругается. "Обычный пользователь" видит чудо, ругает индийских программистов и склеивает на соплях с разными интересными эффектами в результате.

Вообще-то работать перестало только когда человек попытался расширить стандартные коллекции способом, который в других языках попросту невозможен. (Причем по концовке-то все завелось).

Если вы знаете язык программирования, в котором описанный сценарий можно реализовать простым способом, расскажите, пожалуйста.

Edited 2013-01-24 12:26 (UTC)

попросту невозможен

Если язык или библиотека что-то не делают, это совсем не значит, что причина в том, что этого нельзя сделать.

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

Про Мартина виноват. Для тех, кто будет читать обсуждение позже, я имел ввиду пользователя modersky.

Это не "виноват", это "высказывание сделано с предположением о наличии у программиста определённых знаний". То есть, это не ошибка. По крайней мере, не случайная ошибка.

Flat | Top-Level Comments Only

and more on type classes in Scala

no subject

no subject

я просто удилась, куда пропали русские буквы

Re: я просто удилась, куда пропали русские буквы

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject