Well you could use a newtype, or in Scala 3 an opaque type.
Yes, but Int is the set of all 32-bit-integers, not the set of integers 0 to 4.
right, I didn’t see those discussions previously. Thanks.
1 Like
I can imagine that many abstractions which seem good at first turn out to be bad ideas when the rubber hits the road.
Certainly a programming language (Scala, Common Lisp, Rust, Java script etc) are imperfect tools for used in solving problems. Scala gives me some tools for modeling some aspects in mathematics, but these abstractions are limited for many reasons. For example, in mathematics a monoid is closed, and the operation is associative. Scala does not let me indicate that in any useful or enforceable way. Although, I could certainly write some property based tests to help.
The Fortress language (A Sun Microsystem language designed by Guy Steele, but later abandoned) as I understand, allowed the programmer to specify whether operations were commutative or associative, and the compiler was allowed to optimized based on that fact.
The model that I’ve used in this exercise, does allow me to express some abstract mathematical ideas elegantly. Whether or not the approach fits the definition of typeclass, does not change whether it is useful or powerful.
When I said " Monoid should not be modeled like that", I didn’t mean your code but the fact of using typeclasses (or at least implicit typeclasses if you please).
BTW:
That is what cats do, it encodes the laws of the typeclasses as some property test.
Sure, as I said multiple times now, my point is not that your code is wrong, is just that is not a good example to learn typeclasses; which, IIRC, was your primary goal.
Seems you’re right: In retrospect I suppose I had two goals. (1) to experiment with typeclasses, and (2) to represent abstract algebra, with the motivation of implementing fast-exponent.
However, I do seem to recall when I presented this question recently (how to represent sets with mathematical structure), in the context of making it fit into the object system, someone suggested it could be solved with typeclasses. Maybe that was a miscommunication.
The thing is that even if not the best fit, still the best way to abstract over numeric types and operations is something akin to a typeclass, it is just that its implicit / unique nature doesn’t play nice.
So, yeah, at the end what you wanted was just the strategy pattern.
It seems to me that understanding this strategy pattern helps to understand typeclasses. Ask me this question in one year and see if I still believe it.
Context matters. Strictly speaking, type classes are a type level construct - and in Haskell, for example, you cannot have it any other way. In Scala, where type classes are not a dedicated language feature, but rather emulated through a mix of language features such as traits and implicits, I’d think it’s common to call any construct where a trait implementation is looked up from implicit scope for a given type (or a combination of types) a “type class”, even if there’s potentially multiple competing implementations for this type that could be in scope instead. In order to learn about type classes, though, it’s probably best to start with cases that are entirely “by the book”, even if Scala allows additional degrees of freedom compared to the stricter notion as enforced in Haskell.
Thanks for sharing your point of view. It is really interesting to hear different opinions from experts who don’t agree. The state of understanding advances when we are able to articulate our disagreement in a constructive way.
What’s the best way to learn? That’s an interesting question indeed. As a professor, I try to put myself in the shoes of a student seeing it for the first time–with different degrees of success.
In my own experience, I’ve read several descriptions of typeclasses, and never really understood. However, working through a real problem which I understood (i.e. understood the mathematical problem but not yet the programming problem) was helpful for me to understand how the pieces fit together. I think there is merit (pedagogically) in understanding the strategy pattern before trying to understand singleton-evidence-based type classes.
Perhaps people who learned OO with single-dispatch based systems, think that patterns such as strategy and visitor are necessary and are thus understood by everyone.
Perhaps my difficult with this concept comes from my lisp experience. In CLOS, these types of problems are obviated by multiple dispatch. When applications can specialize their functions on classes they don’t own, and when run-time method selection is robustly done as a function of ALL the arguments, you then need far less application-level scaffolding to force your problem into the object system constraints of the programming language in question.
Where does cats encode these laws? Are they factored into the test suite? Or are they implemented within the classes themselves? Does implementing the laws in the classes make the application depend on the test framework?
It is probably very often the case that a law in a superclass should also apply to subclasses. However, I can imagine cases where this shouldn’t be enforced for implementation reasons or performance reasons.
Yes, they are a separate library, which is not required if you just use their typeclass instances. You only need it, if you want to test instances yourself, see Law testing
They are based on Typelevel’s discipline library for law checking
1 Like
I suspect that’s true – the way you’re used to things working is very different from the Haskell world that type classes arose from.
I don’t think the strategy pattern per se (at least by name) is necessarily the best way to start – it’s great for folks coming from a background in Java and some other languages that are used to that GoF way of looking at the world, but in my experience many Scala learners are coming from backgrounds that don’t have that, so it’s just an extra level of complication.
Personally, I’ve found type classes to be reasonably teachable when I step far away from other OO systems – in particular, step away from the notion that data and behavior can be coupled – and break it down to the three key concepts. In order to use type classes, you need three things:
- Data types – data structures with no behavior unto themselves.
- Type classes – pure interfaces that describe behavior
- Implementations – for a given data type, provide an implementation of a type class
That’s over-simplified in a number of respects, but I’ve usually found it sufficient to get folks understanding the basics of the approach, which is step one. Motivating why they are useful tends to take more time and practice, but I’ve found it helpful to ask students to just implement a few simple type classes (classics like Show, Ordering, etc) as a first step.
3 Likes
- For type classes by the book, there’s (at most) one type class instance per type.
- To implement monoid as a by-the-book type class, you’d have to conjure up dedicated types per instance - there won’t be a
Monoid[Int], but aMonoid[Sum]and aMonoid[Product],SumandProductboth wrappingInt. - Scala is more lenient about this, as implicit resolution involves scope as well as types - you can have multiple instances of
Monoid[Int]and bring the one in scope you need. - This broader concept of “matching trait instances to types via implicit resolution” usually is called a “type class”, too, in the Scala world.
- This “watered-down” type class approach is usually considered a decent way of implementing something the monoid concept in Scala.
- …but as it strays somewhat from the essence of the strict type class concept, it may not be the best way to get acquainted with the concept.
I haven’t perceived much disagreement around this at all so far (maybe due to confirmation bias, though).
This statement confuses me somewhat. It seems to imply that the type class concept has OO roots and doubles down on your type class ~ strategy metaphor.
Type classes originated in Haskell, and Haskellers would sneer at the idea that type classes resemble the OO strategy pattern - for them, the core of the OO strategy pattern boils down to a plain function.
Of course you could say that type classes are something like the strategy pattern at type level - but you could just as well say that type classes are like the adapter pattern at type level (it adapts a type to the type class API) or like a burrito (because whatever). I’d think this just muddies the waters.
1 Like
While that’s kind of by-the-book true, it’s not unusual to violate it in Scala. Indeed, the standard library makes this point – the existence of Ordering.reverse provides a fairly common, and very official, example…
Fully agree, and I hoped I’d expressed this “by-the-book” vs “the Scala way” distinction clearly (along with the notion that there’s nothing wrong about the Scala way at all).
I’m tempted to argue that the existence of #reverse as such doesn’t necessarily break the stricter concept - I might use it if I ever wanted a “by-the-book” reverse, for example:
class Down[T](val value: T) extends AnyVal
object Down {
implicit def downOrdering[T : Ordering]: Ordering[Down[T]] =
Ordering[T].reverse.on(_.value)
}
It’s passing a reverted (or any other) ordering instance as an explicit argument (or explicitly bringing an implicit in scope) that makes things “special”.
Speaking of Ordering, there’s a nice “micro showcase” for comparing the type class and strategy approaches in the stdlib with the #sortWith() and #sorted methods on collections.
If you want to code things like that, you can explore languages with dependent types such as Idris, Agda or Coq.
This seems strange to me. From the point of view of the monoid, it doesn’t know whether it is multiplicative or additive. In some abstractions you very well might have two different additive or two different multiplicative monoids.
Yes, when I read this the first time it bothered me, and still does. Ordering is not a function of the set, but a function of the application. To say that strings have a natural ordering is just wrong. Applications order strings, whether high to low, low to high, case independent, ignoring spaces, handing diacritics differently e, è, é, ë etc. There are many different orderings.
This is not about the semantics of the monoid(s). If there can only be one monoid per type and you want both an additive and multiplicative monoid for integers in different contexts (perhaps within the same computation), then you’ll need dedicated types for “integer with additive monoid” and “integer with multiplicative monoid”. (You can choose one monoid variant as the “canonical” one and tie it to the original type, leaving one wrapper type to be introduced for the non-canonical variant.) That’s just about as strange as not being able to have one single strategy implementation for both addition and multiplication.
(Note again that this is about the purist definition of a type class and how it is enforced e.g. in Haskell. You very likely wouldn’t use this approach in Scala production code.)
Then you’d have to introduce the corresponding (wrapper) types, one per monoid variant.
An ordered set is a set plus an ordering relation. You can either view your types as ordered sets or as plain sets. For the former view, you’d tie the relation to the type. With the OO way, you’d make the relation a method on the type - that’s what the Ordered trait does. Using “strict” type classes, you’d have dedicated types per ordering, each with a corresponding, fixed Ordering instance. For the plain set view, there’s the strategy approach. With Scala type classes, you can kind of mix and match in between the two views. (Note the #orderBy() method on collections in this context.)
I don’t think there’s a clear right or wrong there, it’s about which model is best suited for a given use case (and how well the language supports this model).
Nobody challenges this, I’d think. But there’s different ways of modeling this fact.