data-structures - curso - tutorial qgis 2.18 español pdf

¿Por qué F#prefiere las listas sobre las matrices?

Question

Estoy tratando de aprender F # y estaba viendo un video cuando surgió algo extraño (al menos, para mí). El video en cuestión está here y la parte correspondiente comienza a las 2:30 para los interesados. Pero básicamente, el tipo dice que F # hace que sea incómodo trabajar con arreglos y que los diseñadores lo hicieron a propósito porque las listas son más fáciles de "añadir y añadir".

La pregunta que vino inmediatamente a mi mente: ¿no es fácil preparar y añadir algo que debería ser mal visto en un lenguaje inmutable? Específicamente, estoy pensando en las listas de C # donde puedes hacer algo como List.Add(obj); y mutar la lista. Con una matriz, tendrías que crear una matriz completamente nueva, pero eso también es lo que debería ocurrir en un lenguaje inmutable.

Entonces, ¿por qué los diseñadores de F # prefieren las listas? ¿Cuál es la diferencia fundamental en un entorno inmutable entre una lista y una matriz? ¿Qué me estoy perdiendo? ¿Las listas en F # son realmente listas enlazadas?

Answer 1

F # hace que sea incómodo trabajar con matrices

F # proporciona muchas características que facilitan el trabajo con arreglos que en otros idiomas, incluidos los literales de arreglos, patrones de arreglos y funciones de orden superior.

La pregunta que vino inmediatamente a mi mente: ¿no es fácil preparar y añadir algo que debería ser mal visto en un lenguaje inmutable?

Creo que has entendido mal lo que significa esa declaración. Cuando las personas hablan de anteponer y agregar en el contexto de estructuras de datos puramente funcionales, se refieren a la creación de una nueva colección que se deriva (y comparte la mayoría de sus elementos internos) con una colección existente.

Entonces, ¿por qué los diseñadores de F # prefieren las listas?

F # heredó algunas capacidades relacionadas con listas de OCaml que las heredó de Standard ML y ML porque las listas inmutables con enlaces simples son muy útiles en el contexto de su dominio de aplicación (metaprogramación), pero no diría que los diseñadores de F # prefieren las listas.

¿Cuál es la diferencia fundamental en un entorno inmutable entre una lista y una matriz?

En F #, las listas proporcionan O (1) prepend y anexar y O (n) acceso aleatorio, mientras que las matrices proporcionan O (n) prepend y anexión y O (1) acceso aleatorio. Las matrices pueden ser mutadas pero las listas no.

¿Qué me estoy perdiendo?

Conocimientos básicos de estructuras de datos puramente funcionales. Leer Okasaki.

¿Las listas en F # son realmente listas enlazadas?

Sí. Específicamente, listas inmutables enlazadas individualmente. De hecho, en algunos NM el tipo de list puede definirse como:

type ''a list =
  | ([])
  | (::) of ''a * ''a list

Por esta razón, el operador :: es un constructor y no una función, por lo que no puede escribir (::) como puede, por ejemplo, con (+) .

Answer 2

En los lenguajes funcionales, las listas suelen ser listas enlazadas simples. Es decir, no es necesario copiar la lista completa. En lugar de eso, el complemento (a menudo llamado contras) es una operación O (1) y aún puede utilizar la lista anterior, porque las listas son inmutables.

Answer 3

En primer lugar, los arreglos son una estructura de datos de muy bajo nivel y realmente solo son útiles si se conoce la longitud del arreglo al crearlo. No suele ser el caso y por eso los programadores de C # usan System.Collections.Generic.List<T> y los programadores de F # usan F # list<T> .

La razón por la que F # prefiere su propia lista funcional en lugar de usar .NET List<T> es que los lenguajes funcionales prefieren tipos inmutables. En lugar de modificar el objeto llamando a list.Add(x) , puede crear una nueva lista con los elementos agregados en la parte delantera escribiendo let newList = x::list .

También estoy de acuerdo con Stephen en que el uso de matrices en F # no es para nada incómodo. Si conoce la cantidad de elementos con los que está trabajando o está transformando alguna fuente de datos existente, entonces trabajar con matrices es bastante sencillo:

/ You can create arrays using `init`
let a = Array.init 10 (fun i -> (* calculate i-th element here *) )

// You can transform arrays using `map` and `filter`
a |> Array.map (fun n -> n + 10)
  |> Array.filter (fun n -> n > 12)

// You can use array comprehensions:
let a2 = [| for n in a do
              if n > 12 then yield n + 10 |]

Básicamente, esto es lo mismo que procesar listas: aquí se usarían las funciones de comprensión de lista y de procesamiento de lista, como List.map etc. La diferencia realmente aparece justo cuando se inicializa la lista / matriz.

Answer 4

No estoy de acuerdo en que "F # hace que sea incómodo trabajar con matrices". De hecho, F # hace que trabajar con matrices sea bastante agradable en comparación con la mayoría de los lenguajes.

Por ejemplo, F # tiene una construcción de matriz literal: let arr = [|1;2;3;4;|] . Y quizás incluso más fresco, coincidencia de patrones en matrices:

match arr with
| [|1;2;_;_|] -> printfn "Starts with 1;2"
| [|_;_;3;4|] -> printfn "Ends with 3;4"
| _ -> printfn "Array not recognized"

En cuanto a por qué se prefieren listas inmutables enlazadas individualmente en la programación funcional como F #, hay mucho que decir, pero la respuesta corta es que permite una eficiencia de prefabricación O (1), y permite que la implementación comparta nodos, por lo que es fácil memoria. Por ejemplo,

let x = [2;3]
let y = 1::x

Aquí y se crea anteponiendo 1 a x, pero x no se modifica ni se copia, por lo que hacer y fue muy barato. Podemos ver un poco cómo esto es posible, ya que x apunta a la cabecera, 2, de la lista construida inicialmente y solo puede avanzar, y dado que los elementos de la lista a los que apunta no pueden ser mutados, no es así. importa que y compartas nodos con ella.

Answer 5

Una lista F # es más parecida a la siguiente estructura de datos: una única lista vinculada:

public class List<T> {

    public List(T item, List<T> prev) { /*...*/ }

    public T Item { get; }
    public List<T> Prev { get; }
}

Por lo tanto, cuando se crea una nueva lista, en realidad está creando un solo nodo con una referencia al primer elemento de la lista anterior, en lugar de copiar la matriz completa.