¿Por qué no hay matrices inmutables en la biblioteca estándar scala?

Question

Scala tiene todo tipo de clases de secuencias inmutables como Lista, Vector, etc. Me he sorprendido de no encontrar implementación de secuencias indexadas inmutables respaldadas por una matriz simple (Vector parece demasiado complicado para mis necesidades).

• ¿Hay un motivo de diseño para esto? No pude encontrar una buena explicación en la lista de correo.

• ¿Tiene una recomendación para una secuencia indexada inmutable que tiene casi las mismas prestaciones que una matriz? Estoy considerando Scalaz ImmutableArray, pero tiene algunos problemas con scala trunk por ejemplo.

Gracias

Answer 1

Se podría emitir su matriz en una secuencia.

val s: Seq[Int] = Array(1,2,3,4) 

La matriz se convertirá implícitamente en WrappedArray. Y como el tipo es Seq, las operaciones de actualización ya no estarán disponibles.

Answer 2

Principalmente porque no hay matrices en Scala. Lo que estás viendo son las matrices de Java con algunos métodos que les ayudan a encajar en la API de recopilación.

Cualquier otra cosa no sería una matriz, con su propiedad única de no sufrir borrado de tipo, o la varianza rota. Simplemente sería otro tipo con índices y valores. Scala hace tienen que, se llama IndexedSeq, y si es necesario pasarlo como una matriz para algunos API tercera parte a continuación, puedes utilizar .toArray

Answer 3

El punto de la Scala Array clase es proporcionar un mecanismo para el acceso las capacidades de las matrices de Java (pero sin la decisión de diseño horrible de permitir que las matrices sean covariantes dentro de su sistema de tipos). Las matrices de Java son mutables, por lo tanto, también las de la biblioteca estándar scala.

Supongamos que hay también eran otra clase immutable.Array en la biblioteca, pero que el compilador eran también de usar una matriz de Java como la estructura subyacente (para la eficiencia/velocidad). El siguiente código se compilaría y ejecutaría:

val i = immutable.Array("Hello") 
i.asInstanceOf[Array[String]](0) = "Goodbye" 
println(i(0)) //I thought i was immutable :-(

Es decir, la matriz sería realmente mutable.

Answer 4

Por lo tanto, primero hagamos una distinción entre interfaz y clase. La interfaz es un diseño de API, mientras que la clase es la implementación de dicha API.

Las interfaces en Scala tienen el mismo nombre y paquete diferente para distinguir en lo que respecta a la inmutabilidad: Seq, immutable.Seq, mutable.Seq.

Las clases, por otro lado, generalmente no comparten un nombre. Un List es una secuencia inmutable, mientras que un ListBuffer es una secuencia mutable. Hay excepciones, como HashSet, pero eso es solo una coincidencia con respecto a la implementación.

Ahora, y Array no es parte de la colección de Scala, ya que es una clase de Java, pero su contenedor WrappedArray muestra claramente dónde se mostraría: como una clase mutable.

La interfazimplementado por WrappedArray es IndexedSeq, que existe son ambas características mutables e inmutables.

El immutable.IndexedSeq tiene algunas clases de implementación, incluido el WrappedString. La clase de uso general que lo implementa, sin embargo, es Vector. Esa clase ocupa la misma posición que una clase Array ocuparía en el lado mutable.

Ahora, no hay más complejidad en el uso de un Vector que usando un Array, así que no sé por qué lo llaman complicado.

Tal vez pensamos que lo hace demasiado internamente, en cuyo caso podría estar equivocado. Todas las clases inmutables bien diseñadas son persistent, porque usar una colección inmutable significa crear nuevas copias de la misma, por lo que deben optimizarse para eso, que es exactamente lo que hace Vector.

Answer 5

El problema con las matrices es que tienen un tamaño fijo. No hay ninguna operación para agregar un elemento a una matriz o eliminar uno de ella.

Puede mantener una matriz que suponga será lo suficientemente larga como una copia de seguridad, "desperdiciando" la memoria que no está utilizando, realizar un seguimiento del último índice utilizado y copiar a una matriz más grande si necesita el espacio extra. Esa copia es O(N) obviamente.

Cambiar un solo elemento también es O(N), ya que tendrá que copiar todo el conjunto. No hay intercambio estructural, que es el eje de las estructuras de datos funcionales.

También podría asignar una matriz adicional para los elementos "desbordados", y de alguna manera realizar un seguimiento de sus matrices. En ese punto, estás en el camino de reinventar Vector.

En resumen, debido a su falta de compatibilidad estructural, las fachadas inmutables para arreglos tienen características de rendimiento de tiempo de ejecución terribles para las operaciones más comunes, como agregar un elemento, quitar un elemento y cambiar un elemento.

Eso solo deja el caso de uso de un proveedor de datos de contenido fijo de tamaño fijo, y ese caso de uso es relativamente raro. La mayoría de los usos se sirven mejor con List, Stream o Vector