let me show you something

[juan_gandhi]

I was experimenting with Set[T] functor variance. Here are my considerations regarding the opportunity to make it contravariant. In short: it's impossible.

    /**
     * Casts a set into a set of subtype (contravariance, that is)
     * This method does not work, due to JVM type erasure.
     * Actually, delegating the work to runtime would be a stupid idea anyway;
     * so, is it a general problem with oop? Have to think.
     */
    @Deprecated  
    /*implicit*/ def downshift[A, B >: A] (source: Set[B]) : Set[A] = {
      val b2a: (B => A) = {case (a: A) => a}
      val elements = {for (b <- source; if b.isInstanceOf[A]) yield b2a(b)}
      setOf(elements, source.size, source.contains _)
    }

So, what I am thinking. Can we make Set functor contravariant in OOP? I mean, we have two problems here:

1. Java type erasure makes it impossible to actually check the element type;


2. OOP in general forces us to delegate this type checking to runtime - which is, I assume, a wrong idea

Seems like variance just does not work here.

I'll continue investigating the opportunities for covariance.

Comments

[kashnikov.livejournal.com]

Правильно ссылкой полагаю будет вот такая, но, полагаю, Вы её видели уже скорее всего -- http://www.hpl.hp.com/techreports/90/HPL-90-121.pdf

Прошу извинить, за редактуру =)

[ivan-gandhi.livejournal.com]

Не видел, но спасибо; разъясняет общепринятые (до сих пор) практики.

Славные были времена, в HP сидели ученые и что-то такое писали философское.

[kashnikov.livejournal.com]

Сейчас тоже пишут, направление философии переменилось ;-)

[huzhepidarasa.livejournal.com]

Почему Set должен быть контравариантным?!

[ivan-gandhi.livejournal.com]

X → Ω^X

[huzhepidarasa.livejournal.com]

А ну да, есть же два разных powerset функтора, один ковариантный, другой контравариантный. Но этот, который контравариантный, его ведь нельзя запрограммировать.

[ivan-gandhi.livejournal.com]

А почему собственно?

[huzhepidarasa.livejournal.com]

Ну как. Этот функтор переводит функцию в обратную к ней (многозначную в общем случае, но поскольку у нас теперь с обеих сторон powerset, нам не страшно).

f a = x
f b = y
f c = y

(CoPowSet f) {} = {}
(CoPowSet f) {x} = {a}
(CoPowSet f) {y} = {b,c}
(CoPowSet f) {x,y} = {a,b,c}

Мы это вычислять не умеем.

[ivan-gandhi.livejournal.com]

Переводит, а чё. a ∈ CoPowSet f)(x, y) ≡ f(a) ∈ (x, y) - is it hard?

[huzhepidarasa.livejournal.com]

Ну дык. Имея на руках А и Б, можно что-то такое о них проверить. Но это не совсем то же самое, что имея А, вычислить Б. От функторов в хаскеле именно это требуется. Хотя да, с другой стороны, у нас же не функтор. Функции в одну сторону, стрелки в другую. С третьей стороны, это обычно рассматривается как функтор Set^op→Set, а не наоборот, значит, это на входе у него должна быть кофункция, а на выходе как раз функция.

[ivan-gandhi.livejournal.com]

Что-то я не понял, о чём мы договорились.

Хаскельную форму функториальности я не затрагиваю, там категория другая. В скале категория типов и подтипов (ну ооп же). Нет смысла, имхо, вводить функторы, если они не работают на основной категории (подтипы).

[huzhepidarasa.livejournal.com]

А, черт. Не та категория. Забываю все время. То есть если есть некий тип, у которого параметр только в ковариантной позиции, то это будет функтор, если только в контравариантной — то это контравариантный функтор, а если в обеих — то не функтор вообще. Но в множестве есть естественные операции, у которых аргумент в обеих позициях, namely, итерация по элементам (деление на голову и хвост, whatever) и проверка, принадлежит ли элемент множеству. Если оставить только одну операцию, можно сделать ко- или контра-, по желанию (если JVM позволит, здесь я пока не очень соображаю). Если нужны обе, то функтор не получается, так?

[huzhepidarasa.livejournal.com]

Ага, в Скале же есть и lower bound, и upper bound. Можно сделать ковариантную проверку принадлежности:

   {
      () :;
       (f :) :;
       (z:, f : (, )  ) :;
      (f :) :;
       (y :) : = ! (filter (b  y == b)).empty();
}

Это оно или не оно? (Я пока со Скалой только играюсь, тонкостей не понимаю).

[ivan-gandhi.livejournal.com]

Это любопытно. Нет, это очень даже прикольно.

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

[huzhepidarasa.livejournal.com]

Хм, получается, что проверка на принадлежность может с тем же успехом принимать Any. Что, в общем, совершенно законно и понятно. Если перед нами тип Set[Integer], а мы хотим проверить, не сидит ли в нем какой-нибудь String, что нам мешает? Может ведь и сидеть, оно же ковариантное, там если там на самом деле могут быть объекты, которые наследуют и Integer и String.

ООП иногда бывает очень странным.

[ivan-gandhi.livejournal.com]

В 2.8 проверка принадлежности задана на типе элемента множества, а не на Any, как в джаве.

[huzhepidarasa.livejournal.com]

Ага, понятно. И что 2.8 выдает? В репозиториях только 2.7.7, а из tgz мне не шибко удобно ставить (хоть и придется, наверное).

Если множество задано предикатом, то оно вроде бы как контравариантно, потому что там ничего кроме этого предиката и нету, так?

[ivan-gandhi.livejournal.com]

Да, конечно.

Я использую 2.8, но множество определяю сам (а то слишком резво оно начинает вычисляться). И попробовал побаловаться с вариантностью вот.

[huzhepidarasa.livejournal.com]

Скачал 2.8. Все равно все прекрасно компилирует, 2 == "abc", ворнинг только выдает, что всегда false.

[thedeemon.livejournal.com]

А проблема в ООП или в erasure? Потому что, например, в .net erasure не делается, типы генериков есть в рантайме.

[ivan-gandhi.livejournal.com]

Половина проблемы решена. Эх... ну не писать же на шарпе... ёлы-палы.

[thedeemon.livejournal.com]

Да, боюсь, в .net ничего уровня Скалы нет, шарпу до нее далеко, F#-у, возможно, тоже.

[migmit.vox.com (from livejournal.com)]

Вроде, в .NET есть Скала?

[zoonior.livejournal.com]

Только на уровне "Hello World".

[cema.livejournal.com]

Clojure есть. Но я с ней, наверно, уже надоел. К тому же, она без классов практически.

[alexott.livejournal.com]

да она там вроде тоже не особо живая, по сравнению с JVM версией :-)

[ivan-gandhi.livejournal.com]

Да вот свежая весть пришла, что поставили на моно.