How to return Array[B] rather than ArraySeq[B]

Question
1

Can someone suggest how to fix this compilation error? Is the problem that I should not use map with Arrays, or is the problem that I need to convert the ArraySeq to an Array, or do I simply need to change the type declaration?

  implicit val arrayPairable: Pairable[Array] = new Pairable[Array] {
    override def map[A, B](arr: Array[A], f: A => B): Array[B] = arr.map(f)

    override def foldLeft[A, B](arr: Array[A], z: B)(f: (B, A) => B): B = arr.foldLeft(z)(f)
  }

I get the following compilation error.

Error:(58, 73) type mismatch;
 found   : scala.collection.mutable.ArraySeq[B]
 required: Array[B]
    override def map[A, B](arr: Array[A], f: A => B): Array[B] = arr.map(f)
2

Why I try to convert the return value to array using the toArray method I get another slew of errors I don’t quite understand.

  implicit val arrayPairable: Pairable[Array] = new Pairable[Array] {
    override def map[A, B](arr: Array[A], f: A => B): Array[B] = arr.map(f).toArray[B]

    override def foldLeft[A, B](arr: Array[A], z: B)(f: (B, A) => B): B = arr.foldLeft(z)(f)
  }

Error:(58, 84) No ClassTag available for B
    override def map[A, B](arr: Array[A], f: A => B): Array[B] = arr.map(f).toArray[B]
Error:(58, 84) not enough arguments for method toArray: (implicit evidence$1: scala.reflect.ClassTag[B])Array[B].
Unspecified value parameter evidence$1.
    override def map[A, B](arr: Array[A], f: A => B): Array[B] = arr.map(f).toArray[B]
3

In order to construct an array, the compiler needs to know the type. Since this is currently abstract (in the form of A and B) the compiler cannot.

If you add an implicit class tag to your B value in your map method then it would work

4

As I said in another thread, the reason for this is that arrays aren’t classes with type parameters, but a low-level datatype of the JVM.

This means, that type erasure does not apply to the parameter of an array (an Array[Int] and an Array[Double] are different types at runtime). But this in turn also means, that to create an array, you need the information about that type at runtime. You want to create an Array[B], but B is a type parameter that is erased at runtime.

To keep the required information, you’d have to change the type parameters to def map[A, B: ClassTag] (ClassTag from scala.reflect). So you will have to change the signature in your trait.

5

So I need to change the definition of map in the trait, and propagate that change to all instances of the trait, even if those instances don’t need reflection?

6

Yes, that sadly is the case, as the ClassTag is an additional implicit parameter to the method. Another point to consider is that the change will also propagate up in the call hierarchy, so any method where you use Pairable's map, will either have to use concrete types or also add the ClassTag to the signature.

Overall you have to decide based on your use case, if supporting arrays in this typeclass is feasible or if a separate implementation of algorithms using Pairable for arrays is more appropriate. As arrays are rarely used in Scala except for performance-critical parts of the code, an implementation for arrays could be more optimized by making use of their mutability. Using arrays in an immutable fashion discards most of its performance gains anyways.

7

I beg to differ. If anyone’s interested checkout this Tokeniser

8

I’m not sure how that tokenizer shows, that using the operators from immutable structures, that don’t mutate the array, but return a new one (like map, fold) are faster with arrays than with immutable data structures? Are there any benchmarks I’m overlooking?

1 Like
9

So there 3 main challenges to using Arrays in a functional, efficient way.

  1. map
  2. flatMap
  3. Custom loop decomposition.

So as you suggest, most of the time you want to be able to use the standard high level functional collection methods, append, map, flatMap, fold etc. Folds are no problem, you just need a a foreach method to implement a fold. appends are not a problem as long as you don’t declare the append method in the base trait.

map and flatMap are provided through 2 types classes

trait ArrFlatBuild[ArrT <: ArrImut[_]]
{ def flatMap[A](orig: ArrayLike[A], f: A => ArrT): ArrT
}

trait ArrBuild[B, ArrT <: ArrImut[B]]
{ etc etc
}

The Tokeniser shows efficient functional decomposition over immutable Arrays, for custom loops. Hopefully with improved code since the previous post.

10

I think maybe you misunderstood my original statement.

I know that you can implement these methods efficiently, I only doubt, that there is a relevant gain of performance using an Array directly instead of using an existing collection, e.g. the ArraySeq returned by the library-provided map method, when using the immutable methods exclusively.

As far as I understand your code, the place where you use the array immutably is the Chars class? I’m just arguing, that this won’t be much faster than using ArraySeq, as it’s basically the same, and that instead of changing the Pairable typeclass in the original post to accomodate for raw JVM Arrays, one should just use one of the higher level wrappers.

11

The standard Library ArraySeq currently boxes on map and flatMap. So as far I am concerned, it as it currently stands, useless. I had already implemented Array based homogeneous compound deep-value collections, so I took the deficiency of ArraySeq as an opportunity to create one unified collection schema. I haven’t implemented heterogeneous compound deep-value collections, but I feel confident I can if a compelling use case arises.

The loop decomposition is not using the Chars class, but the CharsOff class which is just a compile time wrapped Integer. So passing the tail of the loop only requires incrementing an integer, or if passing to an external method requires passing the new offset and implicitly passing a reference to the immutable Array. Taking the tail of a a standard Array, an ArraySeq or indeed the tail of a Chars would involve copying. The CharsOff class does not copy the Array, although for the user you can pattern match on a CharsOff as if you were pattern matching directly on the array. The tails in those extractors are just integers.