juan_gandhi | Entries tagged with scala

  implicit def f2tof1[X,Y,Z](f2: Function2[X,Y,Z]) = (xy:(X,Y)) => f2(xy._1, xy._2)

Update: f2.tupled

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)

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

Сидит Андрей Петрович Ощепков на крутом бережку Енисея и читает книжку "Гильбертовы Пространства в Задачах и Решениях"; подходит мужик, глядит на обложку, и спрашивает Андрея Петровича: "а шо це за параша, Гильбертовы Пространства?"
/Эпиграф/

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

Кроме одной фразы - 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 - здесь объясняют, что как раз не, объявляем через уравнения, а определяем или параметрически, или адхок.

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

Надеюсь на продуктивную дискуссию.

here

https://groups.google.com/forum/?fromgroups=#!topic/scala-user/nC263xUiaQo

The same dumb stupid Java where you can only pass a final into an internal class...

"

List<Integer> ints = new ArrayList<>(); 
ints.add(1); 
ints.add(2); 
ints.add(3); 

int sum = 0; 
ints.forEach(i -> {sum += i;});

The compiler error is: "value used in lambda expression should be effectively final". I got some bad suspicion and tried whether this compiles:

int sumArray[] = new int[] { 0 }; 
ints.forEach(i -> {sumArray[0] += i;});

This did compile.
"

Crossposts: http://ivan-gandhi.livejournal.com/2194098.html

( oh fuck can you see )

Non-blocking, composable and reactive realtime web

PartialFunction.lift

Ну это же такая топосная вещь! Обожаю.

(from scala-user)

Can someone tell me whether this "gotcha" is type-unsafe or am I just not realizing something? This bit me in production code today (via java interop).

scala> def x: java.math.BigDecimal = null
x: java.math.BigDecimal

scala> def y = Option[BigDecimal](x) orElse Option[BigDecimal](x)
y: Option[BigDecimal]

scala> for (z <- y) println(z)
java.lang.NullPointerException

Year 2020:

...
java.lang.IllegalArgumentException: null value for BigDecimal
  at scala.math.BigDecimal.(BigDecimal.scala:406)
  at scala.math.BigDecimal$.apply(BigDecimal.scala:335)
  at scala.math.BigDecimal$.apply(BigDecimal.scala:332)
  at scala.math.BigDecimal$.javaBigDecimal2bigDecimal(BigDecimal.scala:347)
  at .y(:12)
  ... 28 elided

Киселёв сказал.

Это я еду со стрейнджлупа, в Сент Луисе; играет джаз и накрапывает дождик.

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

Потом был доклад о скале на llvm. Есть плюсы - не надо хитрить с трейтами, и функции можно нормально передавать. Но данные все забоксены. И библиотека джавная... Ну, нейтивы-то переписывать надо.

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

Один философ рассказал, что скала олицетворяет слияние аристотелевой философии с сократовской, а венчает всё монада.

И ещё, говорит, джаваскрипт - тоже сократовская вещь.

Потом я пошел в другую аудиторию, на второй этаж, но лестница была забита народом. Это что, - спрашиваю, - на Киселёва очередь? Ага.

Но все влезли.

Киселёв код писал на окамле, но, говорит, мог бы и на си.
Речь шла о правильной ленивости. В качестве примера показывал генерацию палиндромов, распараллеленную и по Монте-Карло. А как результаты кешировать? А он использовал fork, так что в каждом процессе своё значение. А в скале надо бы было threadlocal. А в конце объяснил, что речь идёт о SCM - State Continuation Monad.

Открыл мне глаза. Я уже месяц кык пытался сообразить, как на скале или хаскеле кеш запрограммировать, без варов и без блядских этих threadlocals. А вот как. Ну теперь знаю, остаётся код написать.

Погятно, что Киселёв код писал тут же, по ходу дела, и гонял, распараллеоив и показывая top.

JavaScript/Scala
( Read more... )

Завтра на доклад Дэна про scalaz придёт 94 человека. 94 человека будут слушать про моноиды, полугруппы, алгебры, комонады, коалгебры, функторы, аппликативные функторы...

Что делается-то!

function New(name) { return java.lang.Class.forName(name).newInstance() }

function newList() { return New("java.util.LinkedList") }

function arrayFrom(list) {
  var out = [];
  for (i = 0; i < list.size(); i++) { out[i] = asJS(list.apply(i)) }
  return out;
}

function mapFrom(map) {
  var out = {};

  var i = map.iterator();
  while(i.hasNext()) {
    var e = i.next();
    out[e._1()] = asJS(e._2())
  }
  return out;
}


function isListlike(name) {
  return name.indexOf("List") >= 0 || name.indexOf("Array") >= 0 || name.indexOf("$colon$colon") >= 0
}

function isMapLike(name) {
  return name.indexOf("Map") >= 0
}

function asJS(obj) {
  try {
    var cn = obj.getClass().getSimpleName();
    if (isListlike(cn)) return arrayFrom(obj);
    if (isMapLike(cn))  return mapFrom(obj);
  } catch (x) {}
  return obj;
}

critique?

Пишу на джавасприпте кусочки, которые через http post бросаю своему серверу, там рино их исполняет, вызывая мои методы на скале, каковые разговаривают с другим сервером и переформатируют варварские данные в простые мапы; что-то тут лишнее, но я пока не понял, что.

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

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

Обожаю этот постмодерновый стиль. Три языка (четыре - там ещё shell). Ещё один - и сгожусь в члены правительства ПМР.

...что последнее время меня так настойчиво окружают, один смешной - это remote scala actors seemingly not working on my mac.

Т.е. Я могу на пальцах накатать ремотного актёра, что там писать-то, положить его к себе на пришив, и он там целую неделю будет жужжать:
( Read more... )

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

Народ советует акку. Но акку надо привинчивать, осваивать и т.д. Освою, конечно, но через пару недель. А так, на скале я лучше накатаю веб-сервер, половина тех же актёров, те же строк двадцать займёт, делов-то, serializable.unapply... да я просто строки перебрасывать буду, мне для инструментации, пиши как хочешь.

Обидно, да.

Остальные траблы я перечислять не буду; всё это можно спокойно свалить на собственную глупость.

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

Это пессимистический пост, и очень прошу пессимистическую часть не комментировать, а если есть идейки насчёт маков и актёров, то буду очень благодарен.

P.S. Да и хрен с ними с актёрами; написал сервер, теперь через браузер к своему реплу хожу, любо-дорого.

Итак, если у нас имеются две категории, C и D, и два функтора, F: C → D и G: D → C, мы говорим, что эти два функтора образуют сопряженную пару, F ⊣ G если имеется взаимно-однозначное соответствие

F(X) → Y <====> X → G(Y)

Для сопряженной пары мы вывели два естественных преобразования, η: Id_C → F;G и ε: G;F → Id_D.

Оказывается, если есть такие два естественных преобразования, для пары функторов, то они сопряжены.
Ну и правда, если есть f: F(X) → Y, то приложим к нему G, получим G(f): G(F(X)) → G(Y), и соединим это с η_X: X → G(F(X)), получим ту самую X → G(Y).

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

Наши η_X и ε_Y обладают чудесными свойствами:

Эти два чудесные свойства получаются в результате применения тех самых соответствий α и β, что были нарисованы в первой серии - попробуйте сами.

У нас есть теперь всё для монады и комонады.

Монада делается путём композиции, T = F;G; это функтор T: C → C. В качестве монадной единицы годится уже появлявшаяся у нас η, а в качестве монадного умножения (a.k.a. flatten) возьмём μ_X = G(ε_F(X)): G(F(G(F(X)))) → G(F(X)).

Единица оказывается единицей относительно монадного умножения, и умножение оказывается ассоциативно - всё это следует из описанных выше свойств сопряженных функторов.

Симметрично мы можем определить комонаду, путём композиции U = G;F.

Пример.

Возьмём категории C=Set и D=Set×Set - множества и пары множеств, и два функтора, Δ(X) = (X,X) и Π((X,Y)) = X×Y.

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

Эти два функтора сопряжены, Δ ⊣Π.

А именно, если есть (f₁,f₂): (X,X) → (Y₁, Y₂), то это задаёт отображение X →Y₁×Y₂, и наоборот, отображение в декартово произведение Y₁×Y₂ задаёт пару отображений, по компонентам.

Какая ж тут у нас монада? Монада берёт множество X и сопоставляет ему X×X. Монадная единица - диагональ (η(x) = (x,x)), а монадное умножение, X×X×X×X → X×X строится, согласно картинкам из начала этой части, из ε: (Y₁×Y₂, Y₁×Y₂) →(Y₁,Y₂) - проектированием по первой и последней координатам. μ(x₁,x₂,x₃,x₄) = (x₁,x₄).

Кто любит симплициальные категории, увидит тут различные краюшки и рёбрушки, но это ладно, это мы лучше не будем трогать.

"Практический смысл" в программировании у этой монады вот какой: есть двоичный флаг; и наши данные от него зависят - в одном случае вызов возвращает Y₁, а в другом Y₂. Ну и если у нас есть функция, зависящая от того же флага, то нам надо как-то комбинировать и сплющивать; это же Reader Monad, сведённая к двоичному флагу. Ну вот эта монада и есть.

Вопросы?

(Завтра продолжу, хочу показать, как из монады можно построить сопряженную пару, и не одну.)

сижу балуюсь с удалёнными артистами (remote actors)
чё у меня есть - а линух, ну
p
И вот потыкал lsof -i :9000, взял пид, сказал kill -9 этот самый пид

В той скале, что бежала слушала на 9000, вижу вот такой концептуальный текст:


scala> /home/vlad/scala-2.9.2/bin/scala: line 161:  5766 Killed
"${JAVACMD:=java}" $JAVA_OPTS "${java_args[@]}" ${CPSELECT}${TOOL_CLASSPATH} -Dscala.usejavacp=true -Dscala.home="$SCALA_HOME" -Denv.emacs="$EMACS" $CYGWIN_JLINE_TERMINAL scala.tools.nsc.MainGenericRunner "$@"

Just observed a curious thing. I'm using 2.9.2 on my linux.
And what I see: I println a set of two elements; and on different runs the order is different.
I was totally confused, but then noticed Parallelizable is being used (somehow I do not have source code installed; not the best time today).

So what I think I see is this: the nondeterminism in listing set elements. Just a two-element set.

I think this is beautiful. I believe we just beat the axiom of choice, like in the old article by A.Scedrov, where he demonstrated that even for the choice of two AC does not always hold (in his case, though, there was a circular "time" involved).

The future is now.

Profile

Juan-Carlos Gandhi

patryshev.com

November 2025

S	M	T	W	T	F	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

Syndicate

Page Summary

Active Entries

Style Credit

Style: Neutral Good for Practicality by timeasmymeasure

Expand Cut Tags

No cut tags

Page generated Nov. 30th, 2025 11:35 pm

Observations

Views from Souths

Entries tagged with scala

is there anything like this already?

and more on type classes in Scala

type classes as I see them in Scala

typeclasses take 2

scala specs online

no closures in java 8 actually

an eternal shining beauty of scala code

one of the best talks I heard, ever

just learned about...

scala fun

state continuation monad

fun/fuck

дорогая редакция

new stuff

scala->js

пока сам не понимаю, что делаю

среди всех относительно ужасных траблов...

сопряженные функторы-3

смешные случаи со скалой

no axiom of choice for Scala sets in a multicore environment