Generalizing number types seems harder than it should be

I want to implement add(a,b) = a + b for all primitive numbers, not only Int

I expect generics to be the right approach

def add[T <: Int | Double | Float](a: T, b: T): T =
   a + b

The logic is sound; after the first occurrence of T, then T will consistently be inferred as that same type for all occurrences, meaning the possible permutations of types of a,b are exactly known as

(Int, Int)
(Double, Double)
(Float, Float) 

and the + operator is defined for all of those type pairs. Regardless of how this function is called, T + T is guaranteed to be implemented.

And yet, this error is shown

value + is not a member of T

where:    T is a type in method add with bounds <: Int | Double | Float

I ask around and consult some LLMs, and I see solutions involving “type classes”, some arcane looking constructs and slightly advanced fp / category theory I’m still unfamiliar with as a newer Scala user… I’m sure these approaches work, but they still seem like they are overly complex and laborious solutions, to workaround an insufficiency of the language. The generic argument solution I showed is logically provable to work as far as I can see, but the compiler is apparently incapable of knowing that. If so, can this be improved?

Depending on what you seek to achieve, it could be worth looking at the Numeric class.

import scala.math.Numeric.Implicits.infixNumericOps

def addly[A: Numeric](a: A, b: A): A =
  a + b

At least, there may be inspiration around there…

3 Likes

There is some prior art for this in the std lib - implemented as a type class.

There is a + operator implemented for each type, but it’s not “the” + operator - they all have different signatures and no shared generic definition (the latter being what you want to accomplish to start with).

That’s a somewhat bold statement coming from somebody unfamiliar with the language after consulting a couple of LLMs, don’t you think? :slight_smile:

2 Likes

That’s a somewhat bold statement coming from somebody unfamiliar with the language after consulting a couple of LLMs, don’t you think? :slight_smile:

Well, I made sure to qualify my statements with “seems like”, “as far as I can tell”, “if so”, as to stop it from coming across as a bold statement, heh. That was the intent at least.

There is a + operator implemented for each type, but it’s not “the” + operator - they all have different signatures and no shared generic definition (the latter being what you want to accomplish to start with).

I’m wondering why this matters. The signatures will align fine whichever “the” operator ends up being.

If a is int, then “the” operator is +(x: Int), so we must have a.+(x: Int). The type of b is also Int, so a.+(b) is Int.+(Int), which works out, compiler should allow it. Repeat for all of the possible type pairs.

Is this just a nominal vs structural typing limitation? Are there any example problematic scenarios that could arise from this that I’m not thinking of? Or is it just a difficulty in the compiler seeing that it is definitely safe?

This is how I would imagine the workflow of the compiler (though I haven’t written one myself)
0: analyze call site to infer Int as the generic argument

def add[T <: Int | Double | Float](a: T, b: T): T =
   a + b
add(3,4) // T = Int

1: replace generics parameters with arguments

def add(a: Int, b: Int): Int =
   a + b

2: after knowing the types are Int,Int interpret the + as Int.+(Int)

def add(a: Int, b: Int): Int =
   a.+(b)

If this were the series of reduction and analysis steps that the compiler takes, then I don’t see why the compiler would need to know “which” + operator signature is going to happen, since it will know that by the end after replacing all of the Ts with Int.

So, the compiler phases must not work as simply as that, yeah?

Right, but signature isn’t identity.

Think of it this way: if you have two completely unrelated classes, both of which happen to have a method named “add” but work completely differently, does it make sense that you can use them interchangeably? In most languages, the answer is no. They might have the same name and shape, but they aren’t the same thing.

This is where type classes come in: they’re the way to describe a common “interface” for arbitrary, unrelated classes. They’re absolutely the right answer for this sort of problem. Numeric is the standard way to express this for basic numerical operations.

Indeed, there is a frequently-used type class – not in the standard library, but implemented in Cats and some other common base libraries – usually called “Monoid” because that’s the name in mathematics, that truly represents the abstraction of “add”: it allows you to add not just Ints and Doubles but Lists, Strings, and anything else where you would commonly say “this plus that”.

More generally, this is a lesson in how Scala tends to think. It doesn’t cheat with shortcuts for things like this hacked into the language – instead, it’s designed to let you express things in truly general ways in the libraries.

4 Likes

if you have two completely unrelated classes, both of which happen to have a method named “add” but work completely differently, does it make sense that you can use them interchangeably?

So this does sound like a nominal vs structural typing example then. I would answer “yes” that it makes sense to allow that sort of usage interchangeably, but I tend to prefer structural typing anyway. So, Scala’s nominal nature is what creates this limitation?

Also, I’m curious why Scala didn’t implement a common base interface Number for all of these primitives, isn’t that what Java did? Since Scala is already an OO-friendly language, I assumed that’s what would be going on.

That’s a much more complicated question than it looks like on the surface. The answer is basically that, if you rely on OO inheritance like that, you wind up gradually building up a combinatoric explosion of things you need to implement in the leaf classes. (This is sometimes called “the expression problem”.)

Type classes turn out to usually be a more elegant solution, that lets you separate your concerns better.

Hence, while Scala allows OO inheritance, and folks use it to some degree, it’s less the default answer to everything than in Java.

3 Likes

(Also, again, type classes are way more general, and can be added post-hoc to any class after the fact. So you’re not dependent on the original creator of the class having built in the interface you happen to need.)

Well, yes, if you want to call it a limitation. :slight_smile: To me it looks more like a deliberate design decision in the first place. (But I may actually be wrong.)

Here’s a somewhat related previous discussion:

Java has an abstract class Number for the boxed primitive wrappers - I wouldn’t call this a great design. And I do recall that even back in the days when I was doing full OO Java, I’d prefer using Comparator (a poor man’s “type class”) over Comparable for various reasons. IOW, I don’t think having Numeric implemented as a type class must necessarily be a big surprise for anybody coming to Scala from the Java side - it wasn’t for me.

1 Like

Yes Scala is compiled and nomial. Not interpreted or structural like Python or TS.

For your original method to work, it would need to do a runtime lookup. Actually the language allows to express that: Programmatic Structural Types - More Details
But, as I just said, such solution requires doing runtime checks through reflection, which has some implications.

Most Scala programmer prefer to avoid that by using static solutions like typeclasses.

Also, I’m curious why Scala didn’t implement a common base interface Number for all of these primitives, isn’t that what Java did? Since Scala is already an OO-friendly language, I assumed that’s what would be going on.

I have to point out that Java doesn’t have any base type for primitives. Perhaps Valhalla will change this somewhat, but the primitives aren’t objects and don’t participate in any subtyping relationships. That was a choice they made at the time for performance reasons. When Scala was created, it was possible to have the compiler optimize code to use primitives when possible and wrappers otherwise.

I didn’t see any description of why you want to do this. I don’t know if you are performance-sensitive, but I will note that if you are, using an inheritance hierarchy will likely force the compiler to use wrapper objects and make your code significantly slower.

3 Likes

The discussion is about runtime implementation, but probably the solution lies in compiletime inlining and match types.

That may feel like “too much mechanism”, but “generalizing” also results in over-engineering.

1 Like

no, you can provide pairs like (Int, Float). T doesn’t have to be a non-union, it can be an union, e.g. T = Int | Float and then you can provide argument a of type Int and argument b of type Float, e.g.

def add[T <: Int | Double | Float](a: T, b: T): Unit =
   println(s"trying to add parameters of types ${a.getClass} and ${b.getClass}")

add(5, 5f)

which prints:

trying to add parameters of types class java.lang.Integer and class java.lang.Float
3 Likes

compiler doesn’t reanalyze method bodies for each call site, unless you’re doing inline methods in scala3: Inline or other sorts of metaprogramming, as @som-snytt already pointed out.

1 Like

no, you can provide pairs like (Int, Float). T doesn’t have to be a non-union, it can be an union, e.g. T = Int | Float

You’re right I hadn’t considered this, explicitly passing in add[Int | Float] is allowed, which means that heterogeneous pairs like (Int, Float) are possible. The problem then is in that I’m using a <: operator, when I really want something like = “exclusively pick one option” syntax, i.e

def add[T = Int | Double | Float](a: T, b: T): T =
   a + b

So only add[Int], add[Float], add[Double] would be accepted. Seems allowing a way to say this would make a generic approach viable and avoid the need for typeclasses.

Scala has the =:= operator that can enforce the type equality (and <:< too), but I don’t think it has a “logical OR” operator at type level.

You can try using match types (which require the =:= relation to hold true, in addition to other strict conditions).

Even in mathematical languages with much more powerful type systems like Lean (where literally everything is a type), heterogeneous addition is still done via type classes, so I’m not sure why you want so badly to avoid type classes (just theoretical curiosity?), they are actually much easier than these other approaches.

1 Like

so I’m not sure why you want so badly to avoid type classes

Just that I recall every example I’ve seen of type classes looking like a lot of boilerplate and manual labor, whereas this Generic T example is intuitive and easy to write once at the same place.

I’ve also tried understanding conceptually what type classes are a few times and failed (I am new to FP in general), so the intimidation of the concept (like how it takes people forever to understand what Monads are) is another off-putter.

Does anyone want to show me how I could write a type class here to solve my problem? (instead of using the prebuilt Numeric?)

scala compiler has actually plenty of machinery that makes its implementation of type classes quite powerful and approachable, especially in scala3.

type classes aren’t hard. for example, in rust language (which isn’t a functional language), type classes are actually the basic and most common abstraction. in rust language, type classes are defined using trait keyword, which can cause confusion (that keyword is used for different purposes in different languages) - i think rust lang authors avoided using keyword class because they wanted to make their language as different from java as possible (that’s my impression after knowing java for years and then learning rust).

3 Likes

And I assume trait in Scala also has no relation to the concept of “type classes”?