¿Por qué las colecciones de clojure no implementan la interfaz ISeq directamente?

sequence (4)

Cada colección en clojure se dice que es "secuenciable" pero solo la lista y los contras son en realidad las siguientes:

user> (seq? {:a 1 :b 2}) false user> (seq? [1 2 3]) false

Todas las demás funciones seq primero convierten una colección en una secuencia y solo luego operan en ella.

user> (class (rest {:a 1 :b 2})) clojure.lang.PersistentArrayMap$Seq

No puedo hacer cosas como:

user> (:b (rest {:a 1 :b 2})) nil user> (:b (filter #(-> % val (= 1)) {:a 1 :b 1 :c 2})) nil

Y hay que obligar a volver al tipo de datos concreto. Esto me parece un mal diseño, pero lo más probable es que todavía no lo haya recibido.

Entonces, ¿por qué las colecciones clojure no implementan la interfaz ISeq directamente y todas las funciones seq no devuelven un objeto de la misma clase que el objeto de entrada?

Esto ha sido discutido en el grupo de google Clojure; Vea por ejemplo la semántica del mapa de hilos de febrero de este año. Me tomaré la libertad de reutilizar algunos de los puntos que hice en mi mensaje a ese hilo a continuación mientras agrego varios nuevos.

Antes de continuar explicando por qué creo que el diseño de "seq separados" es el correcto, me gustaría señalar que es una solución natural para las situaciones en las que realmente desearía tener una salida similar a la entrada sin ser explícito sobre esto existe en la forma de la función fmap de la biblioteca contrib algo.generic . (No creo que sea una buena idea usarlo por defecto, sin embargo, por las mismas razones por las que el diseño de la biblioteca principal es bueno).

Visión general

La observación clave, creo, es que las operaciones de secuencia como map , filter , etc. se dividen conceptualmente en tres preocupaciones separadas:

alguna forma de iterar sobre su entrada;
aplicando una función a cada elemento de la entrada;
produciendo una salida.

Claramente, 2. no es problemático si podemos lidiar con 1. y 3. Así que echemos un vistazo a ellos.

Iteración

Para 1., considere que la forma más simple y con mayor rendimiento de iterar sobre una colección generalmente no implica asignar resultados intermedios del mismo tipo abstracto que la colección. Es probable que el mapeo de una función sobre una secuencia dividida sobre un vector sea mucho más eficaz que el mapeo de una función sobre una secuencia que produce "vectores de vista" (usando subvec ) para cada llamada a la next ; lo último, sin embargo, es lo mejor que podemos hacer en cuanto al rendimiento para los next vectores de estilo Clojure (incluso en presencia de árboles RRB , que son excelentes cuando necesitamos una operación adecuada de división de vector / subvector para implementar un algoritmo interesante, pero hacer que los recorridos sean terriblemente lentos si los usamos para implementar a next ).

En Clojure, los tipos de secuencia especializados mantienen un estado transversal y una funcionalidad adicional como (1) una pila de nodos para mapas y conjuntos ordenados (aparte de un mejor rendimiento, esto tiene una mejor complejidad de O mayor que las transversales que utilizan dissoc / disj !), (2) índice actual + lógica para envolver matrices de hojas en trozos para vectores, (3) una "continuación" transversal para mapas hash. Atravesar una colección a través de un objeto como este es simplemente más rápido que cualquier intento de atravesar subvec / dissoc / disj .

Sin embargo, supongamos que estamos dispuestos a aceptar el impacto de rendimiento cuando mapeamos una función sobre un vector. Bueno, vamos a tratar de filtrar ahora:

(->> some-vector (map f) (filter p?))

Hay un problema aquí: no hay una buena manera de eliminar elementos de un vector. (Nuevamente, los árboles de la RRB podrían ayudar en teoría, pero en la práctica todo el corte y concatenación de la RRB involucrados en la producción del "vector real" para las operaciones de filtrado destruiría absolutamente el rendimiento).

Aquí hay un problema similar. Considere este oleoducto:

(->> some-sorted-set (filter p?) (map f) (take n))

Aquí nos beneficiamos de la pereza (o, más bien, de la capacidad de dejar de filtrar y mapear temprano; hay un punto relacionado con los reductores que debe hacerse aquí, ver más abajo). Claramente, la take se puede reordenar con el map , pero no con el filter .

El punto es que si está bien que el filter convierta a seq implícitamente, entonces también está bien para el map ; y se pueden hacer argumentos similares para otras funciones de secuencia. Una vez que hemos formulado el argumento para todos, o casi todos, de ellos, queda claro que también tiene sentido que los seq devuelvan objetos de objetos especializados.

Incidentalmente, es muy útil filtrar o mapear una función sobre una colección sin producir una colección similar como resultado . Por ejemplo, a menudo solo nos preocupamos por el resultado de reducir la secuencia producida por una tubería de transformaciones a algún valor o por llamar a una función por efecto secundario en cada elemento. Para estos escenarios, no hay nada que ganar al mantener el tipo de entrada y mucho que perder en el rendimiento.

Produciendo una salida

Como se señaló anteriormente, no siempre queremos producir una salida del mismo tipo que la entrada. Sin embargo, cuando lo hacemos, a menudo la mejor manera de hacerlo es hacer el equivalente a verter una secuencia sobre la entrada en una colección de salida vacía.

De hecho, no hay absolutamente ninguna manera de hacerlo mejor para mapas y conjuntos. La razón fundamental es que para conjuntos de cardinalidad mayores que 1 no hay manera de predecir la cardinalidad de la salida de mapeo de una función sobre un conjunto, ya que la función puede "pegar entre sí" (producir las mismas salidas para) entradas arbitrarias.

Además, para los mapas y conjuntos ordenados, no hay garantía de que el comparador del conjunto de entrada pueda manejar salidas de una función arbitraria.

Por lo tanto, si en muchos casos no hay manera de, por ejemplo, hacer un map significativamente mejor que haciendo una seq y una into separado, y considerando cómo ambas se hacen y hacen primitivas útiles por sí mismas, Clojure toma la decisión de exponer las Primitivas y dejando que los usuarios las compongan. Esto nos permite map y generar un conjunto a partir de un conjunto, mientras nos deja la libertad de no pasar into escenario cuando no se puede obtener ningún valor al generar un conjunto (u otro tipo de colección, según sea el caso). ).

No todo es seq; o, considere los reductores

Algunos de los problemas con el uso de los mismos tipos de colección al mapear, filtrar, etc. no se aplican cuando se usan reductores.

La diferencia clave entre los reductores y las secuencias es que los objetos intermedios producidos por clojure.core.reducers/map y friends solo producen objetos "descriptores" que mantienen información sobre qué cálculos deben realizarse en caso de que el reductor se reduzca realmente. Así, las etapas individuales de la computación se pueden fusionar.

Esto nos permite hacer cosas como

(require ''[clojure.core.reducers :as r]) (->> some-set (r/map f) (r/filter p?) (into #{}))

Por supuesto, todavía tenemos que ser explícitos acerca de nuestro (into #{}) , pero esta es solo una forma de decir "el gasoducto de los reductores termina aquí; genere el resultado en forma de un conjunto". También podríamos solicitar un tipo de colección diferente (quizás un vector de resultados; tenga en cuenta que el mapeo de f sobre un conjunto puede producir resultados duplicados y en algunas situaciones podemos desear preservarlos) o un valor escalar ( (reduce + 0) ) .

Resumen

Los puntos principales son estos:

la forma más rápida de iterar sobre una colección generalmente no implica producir resultados intermedios similares a la entrada;
seq usa la forma más rápida de iterar;
el mejor enfoque para transformar un conjunto mediante el mapeo o filtrado implica el uso de una operación de estilo seq , porque queremos iterar muy rápido mientras acumulamos una salida;
así seq hace un gran primitivo;
map y el filter , en su elección para lidiar con las secuencias, dependiendo del escenario, pueden evitar penalizaciones de rendimiento sin ventajas, beneficiarse de la pereza, etc., pero aún se pueden utilizar para producir un resultado de recolección into ;
así ellos también hacen grandes primitivos.

Es posible que algunos de estos puntos no se apliquen a un lenguaje tipado estáticamente, pero, por supuesto, Clojure es dinámico. Además, cuando queremos una devolución que coincida con el tipo de entrada, simplemente nos vemos obligados a ser explícitos al respecto y eso, en sí mismo, puede verse como algo bueno.

Las Seqs son estructuras ordenadas, mientras que los mapas y conjuntos no están ordenados. Dos mapas que tienen el mismo valor pueden tener un orden interno diferente. Por ejemplo:

user=> (seq (array-map :a 1 :b 2)) ([:a 1] [:b 2]) user=> (seq (array-map :b 2 :a 1)) ([:b 2] [:a 1])

No tiene sentido pedir el rest de un mapa, porque no es una estructura secuencial. Lo mismo vale para un set.

Entonces, ¿qué pasa con los vectores? Están ordenados secuencialmente, por lo que potencialmente podríamos mapear a través de un vector, y de hecho existe una función: mapv .

Bien puede preguntar: ¿por qué esto no es implícito? Si paso un vector al map , ¿por qué no devuelve un vector?

Bueno, primero eso significaría hacer una excepción para estructuras ordenadas como vectores, y Clojure no es grande en hacer excepciones.

Pero lo más importante es que perderías una de las propiedades más útiles de los seqs: la pereza. El encadenamiento de funciones secuenciales, como el map y el filter es una operación muy común, y sin pereza esto sería mucho menos eficaz y requeriría mucho más memoria.

Las clases de colección siguen un patrón de fábrica, es decir, en lugar de implementar ISeq , implementan Sequable es decir, puede crear un ISeq partir de la colección, pero la colección en sí no es un ISeq .

Ahora, incluso si estas colecciones implementaran ISeq directamente, no estoy seguro de cómo resolvería su problema de tener funciones de secuencia de propósito general que devolverían el objeto original, ya que eso no tendría ningún sentido ya que estas funciones de propósito general deberían funcionar en ISeq , no tienen idea de qué objeto les dio este ISeq

Ejemplo en java:

interface ISeq { .... } class A implements ISeq { } class B implements ISeq { } static class Helpers { /* Filter can only work with ISeq, that''s what makes it general purpose. There is no way it could return A or B objects. */ public static ISeq filter(ISeq coll, ...) { } ... }

Las secuencias son una abstracción de lista lógica. Proporcionan acceso a una secuencia ordenada (estable) de valores. Se implementan como vistas sobre colecciones (excepto en las listas donde la interfaz concreta coincide con la interfaz lógica). La secuencia (vista) es una estructura de datos separada que se refiere a la colección para proporcionar la abstracción lógica.

Las funciones de secuencia (mapa, filtro, etc.) toman una cosa "seqable" (algo que puede producir una secuencia), la llaman a ella para producir la secuencia, y luego operan en esa secuencia, devolviendo una nueva secuencia. Depende de usted si necesita o cómo volver a recopilar esa secuencia en una colección concreta. Mientras que los vectores y las listas están ordenados, los conjuntos y los mapas no, y por lo tanto las secuencias sobre estas estructuras de datos deben calcular y conservar el orden fuera de la colección.

Las funciones especializadas como mapv, filterv, reduce-kv le permiten permanecer "en la colección" cuando sabe que desea que la operación devuelva una colección al final en lugar de una secuencia.