2
votes

Over the past week or so I've been working on a typed, indexed array trait for Scala. I'd like to supply the trait as a typeclass, and allow the library user to implement it however they like. Here's an example, using a list of lists to implement the 2d array typeclass:

// crate a 2d Array typeclass, with additional parameters
trait IsA2dArray[A, T, Idx0, Idx1] {
  def get(arr: A, x: Int, y: Int): T // get a single element of the array; its type will be T
}
// give this typeclass method syntax
implicit class IsA2dArrayOps[A, T, Idx0, Idx1](value: A) {
  def get(x: Int, y: Int)(implicit isA2dArrayInstance: IsA2dArray[A, T, Idx0, Idx1]): T = 
    isA2dArrayInstance.get(value, x, y)
}

// The user then creates a simple case class that can act as a 2d array
case class Arr2d[T, Idx0, Idx1] (
  values: List[List[T]],
  idx0: List[Idx0],
  idx1: List[Idx1],
)
// A couple of dummy index element types:
case class Date(i: Int) // an example index element
case class Item(a: Char) // also an example
// The user implements the IsA2dArray typeclass 
implicit def arr2dIsA2dArray[T, Idx0, Idx1] = new IsA2dArray[Arr2d[T, Idx0, Idx1], T, Idx0, Idx1] {
  def get(arr: Arr2d[T, Idx0, Idx1], x: Int, y: Int): T = arr.values(x)(y)
}
// create an example instance of the type
val arr2d = Arr2d[Double, Date, Item] (
  List(List(1.0, 2.0), List(3.0, 4.0)),
  List(Date(0), Date(1)),
  List(Item('a'), Item('b')),
)
// check that it works
arr2d.get(0, 1)

This all seems fine. Where I am having difficulties is that I would like to constrain the index types to a list of approved types (which the user can change). Since the program is not the original owner of all the approved types, I was thinking to have a typeclass to represent these approved types, and to have the approved types implement it:

trait IsValidIndex[A] // a typeclass, indicating whether this is a valid index type
implicit val dateIsValidIndex: IsValidIndex[Date] = new IsValidIndex[Date] {} 
implicit val itemIsValidIndex: IsValidIndex[Item] = new IsValidIndex[Item] {}

then change the typeclass definition to impose a constraint that Idx0 and Idx1 have to implement the IsValidIndex typeclass (and here is where things start not to work):

  trait IsA2dArray[A, T, Idx0: IsValidIndex, Idx1: IsValidIndex] {
    def get(arr: A, x: Int, y: Int): T // get a single element of the array; its type will be T
  }

This won't compile because it requires a trait to have an implicit parameter for the typeclass, which they are not allowed to have: (Constraining type parameters on case classes and traits).

This leaves me with two potential solutions, but both of them feel a bit sub-optimal:

  1. Implement the original IsA2dArray typeclass as an abstract class instead, which then allows me to use the Idx0: IsValidIndex syntax directly above (kindly suggested in the link above). This was my original thinking, but a) it is less user friendly, since it requires the user to wrap whatever type they are using in another class which then extends this abstract class. Whereas with a typeclass, the new functionality can be directly bolted on, and b) this quickly got quite fiddly and hard to type - I found this blog post (https://tpolecat.github.io/2015/04/29/f-bounds.html) relevant to the problems - and it felt like taking the typeclass route would be easier over the longer term.
  2. The contraint that Idx0 Idx0 and Idx1 must implement IsValidIndex can be placed in the implicit def to implement the typeclass: implicit def arr2dIsA2dArray[T, Idx0: IsValidIndex, Idx1: IsValidIndex] = ... But this is then in the user's hands rather than the library writer's, and there is no guarantee that they will enforce it.

If anyone could suggest either a work-around to square this circle, or an overall change of approach which achieves the same goal, I'd be most grateful. I understand that Scala 3 allows traits to have implicit parameters and therefore would allow me to use the Idx0: IsValidIndex constraint directly in the typeclass generic parameter list, which would be great. But switching over to 3 just for that feels like quite a big hammer to crack a relatively small nut.

1
I think this line is wrong def arr2dIsA2dArray[T, Idx0, Idx1] = new IsA2dArray[Arr2d[T, Idx0, Idx1], T, Date, Item], it's either Data, Item in the end and remove Idx0 and 1 or Idx0, Idx1 in the end.pedrofurla
@pedrofurla - thanks and yes, you're right - I'll correct it now.Chris J Harris
Btw, I was going to answer the question with your second solution, then I saw you already nailed it. Giving further thought, I think you are bundling to many thing together, at least that's what I feel without seeing a purpose for Idx0 and 1.pedrofurla
@Chrisper Regarding 1. I can't see how using abstract class rather than trait is less optimal. "it requires the user to wrap whatever type they are using in another class which then extends this abstract class" Why?? Abstract class will not be extended, it will be still a type class, just abstract-class type class and not trait type class.Dmytro Mitin
@Mostly. stackoverflow.com/questions/1991042/… geeksforgeeks.org/… Unless you have hierarchy of type classes (like Functor, Applicative, Monad... in Cats). Trait or abstract class (a type class) can't extend several abstract classes (type classes) while it can extend several traits (type classes).Dmytro Mitin

1 Answers

2
votes

I guess the solution is

  1. Implement the original IsA2dArray typeclass as an abstract class instead, which then allows me to use the Idx0: IsValidIndex syntax directly above (kindly suggested in the link above).

This was my original thinking, but a) it is less user friendly, since it requires the user to wrap whatever type they are using in another class which then extends this abstract class.

No, abstract class will not be extended*, it will be still a type class, just abstract-class type class and not trait type class.

Can I just assume that trait and abstract class are interchangeable when defining typeclasses?

Mostly.

What is the advantage of using abstract classes instead of traits?

https://www.geeksforgeeks.org/difference-between-traits-and-abstract-classes-in-scala/

Unless you have hierarchy of type classes (like Functor, Applicative, Monad... in Cats). Trait or abstract class (a type class) can't extend several abstract classes (type classes) while it can extend several traits (type classes). But anyway inheritance of type classes is tricky

https://typelevel.org/blog/2016/09/30/subtype-typeclasses.html


* Well, when we write implicit def arr2dIsA2dArray[T, Idx0, Idx1] = new IsA2dArray[Arr2d[T, Idx0, Idx1], T, Idx0, Idx1] {... technically it's extending IsA2dArray but this is similar for IsA2dArray being a trait and abstract class.