net - operador de cons(::) en F#

.net programming language

Question

El operador :: en F # siempre antepone elementos a la lista. ¿Hay un operador que se agrega a la lista? Supongo que usando el operador @

[1; 2; 3] @ [4]

sería menos eficiente que agregar un elemento.

Answer 1

Supongo que usar @ operator [...] sería menos eficiente que agregar un elemento.

Si lo es, será una diferencia insignificante. Tanto agregar un solo elemento como concatenar una lista hasta el final son O(n) operaciones. De hecho, no puedo pensar en una sola cosa que @ tenga que hacer, que no sería una función de adición de un solo elemento.

Answer 2

Como otros dijeron, no existe tal operador, porque no tendría mucho sentido. De hecho, creo que esto es algo bueno, porque hace que sea más fácil darse cuenta de que la operación no será eficiente. En la práctica, no debe necesitar al operador; generalmente hay una mejor manera de escribir lo mismo.

Escenario típico: creo que el escenario típico en el que podría pensar que necesita agregar elementos al final es tan común que puede ser útil describirlo.

Agregar elementos al final parece necesario cuando está escribiendo una versión recursiva de cola de una función usando el parámetro de acumulador . Por ejemplo, una implementación (ineficaz) de la función de filter para listas se vería así:

let filter f l =
let rec filterUtil acc l =
match l with
| [] -> acc
| x::xs when f x -> filterUtil (acc @ [x]) xs
| x::xs -> filterUtil acc xs
filterUtil [] l

En cada paso, necesitamos agregar un elemento al acumulador (que almacena los elementos que se devolverán como resultado). Este código se puede modificar fácilmente para usar el operador :: lugar de agregar elementos al final de la lista acc :

let filter f l =
let rec filterUtil acc l =
match l with
| [] -> List.rev acc // (1)
| x::xs when f x -> filterUtil (x::acc) xs // (2)
| x::xs -> filterUtil acc xs
filterUtil [] l

En (2), ahora estamos agregando elementos al frente del acumulador y cuando la función está a punto de devolver el resultado, invertimos la lista (1), que es mucho más eficiente que agregar elementos uno por uno.

Answer 3

El costo de agregar dos listas estándar es proporcional a la longitud de la lista de la izquierda . En particular, el costo de

xs @ [x]

es proporcional a la duración de xs ; no es un costo constante.

Si desea una abstracción tipo lista con un apéndice de tiempo constante, puede usar la representación de la función de John Hughes, que llamaré hlist . Trataré de usar la sintaxis OCaml, que espero esté lo suficientemente cerca de F #:

type ''a hlist = ''a list -> ''a list (* a John Hughes list *)
let empty : ''a hlist = let id xs = xs in id
let append xs ys = fun tail -> xs (ys tail)
let singleton x = fun tail -> x :: tail
let cons x xs = append (singleton x) xs
let snoc xs x = append xs (singleton x)
let to_list : ''a hlist -> ''a list = fun xs -> xs []

La idea es que represente una lista funcionalmente como una función desde "el resto de los elementos" hasta "la lista final". Esto funciona si creas la lista completa antes de mirar cualquiera de los elementos. De lo contrario, tendrá que lidiar con el costo lineal de agregar o usar otra estructura de datos por completo.

Answer 4

Intente utilizar una cola de doble final en lugar de lista. Recientemente agregué 4 versiones de deques (ortografía de Okasaki) a FSharpx.Core (Disponible a través de NuGet. Código fuente en FSharpx.Core.Datastructures ). Ver mi artículo sobre el uso de dequeus Colas de http://jackfoxy.com/double-ended-queues-for-fsharp

He sugerido al equipo de F # el operador contra, ::, y el discriminador de patrones activos estará disponible para otras estructuras de datos con una firma de cabeza / cola. 3

Answer 5

La eficiencia (o falta de) proviene de iterar a través de la lista para encontrar el elemento final. Entonces, declarar una nueva lista con [4] va a ser insignificante para todos los escenarios menos triviales.

Answer 6

Las listas en F # están individualmente vinculadas e inmutables. Esto significa que consingrar en el frente es O (1) (crear un elemento y hacer que apunte a una lista existente), mientras que esnob en la parte posterior es O (N) (como toda la lista debe ser replicada, no se puede cambiar el puntero final existente, debe crear una lista completamente nueva).

Si necesita "agregar un elemento a la parte posterior", entonces, por ejemplo

l @ [42]

es la manera de hacerlo, pero este es un olor a código.

Answer 7

Tal vez quieras usar otra estructura de datos. Tenemos colas de doble final (o corto "Deques") en fsharpx . Puede leer más sobre ellos en http://jackfoxy.com/double-ended-queues-for-fsharp