language agnostic - que - ¿Por qué solo se puede anteponer a listas en lenguajes funcionales?
programacion funcional c# (5)
Solo he usado 3 lenguajes funcionales: scala, erlang y haskell, pero en los 3 de estos, la forma correcta de construir listas es anteponer los nuevos datos al frente y luego revertirlos en lugar de simplemente agregarlos al final. Por supuesto, podría agregarse a las listas, pero eso da como resultado que se construya una lista completamente nueva.
¿Por qué es esto? Podría imaginar que se debe a que las listas se implementan internamente como listas vinculadas, pero ¿por qué no podrían implementarse simplemente como listas doblemente vinculadas para que pueda agregarse al final sin penalización? ¿Hay alguna razón para que todos los lenguajes funcionales tengan esta limitación?
Porque es mas rapido
Ciertamente, podrían admitir la adición, pero es mucho más rápido para la versión previa que limitan la API. Tampoco es funcional agregarlo, ya que debe modificar el último elemento o crear una lista completamente nueva. Prepend trabaja en un estilo inmutable, funcional, por su naturaleza.
Al restringir la construcción de la lista a la prefijada, significa que cualquier otra persona que tenga una referencia a alguna parte de la lista más abajo, no la verá cambiar inesperadamente a sus espaldas. Esto permite una construcción eficiente de la lista mientras se conserva la propiedad de datos inmutables.
Esa es la forma en que se definen las listas. Una lista se define como una lista vinculada terminada por un nulo, esto no es solo un detalle de implementación. Esto, junto con el hecho de que estos idiomas tienen datos inmutables, al menos erlang y haskell, significa que no se pueden implementar como listas doblemente vinculadas. Agregar un elemento los modificaría la lista, lo cual es ilegal.
Las listas en lenguajes funcionales son inmutables / persistentes.
Anexar al frente de una lista inmutable es barato porque solo tiene que asignar un solo nodo con el siguiente puntero que apunta al encabezado de la lista anterior. No es necesario cambiar la lista original, ya que solo es una lista enlazada individualmente y los punteros a la cabecera anterior no pueden ver la actualización.
Agregar un nodo al final de la lista requiere modificar el último nodo para que apunte al nodo recién creado. Solo que esto no es posible porque el nodo es inmutable. La única opción es crear un nuevo nodo que tenga el mismo valor que el último nodo y apunte a la nueva cola creada. Este proceso debe repetirse hasta el principio de la lista, lo que da como resultado una lista completamente nueva que es una copia de la primera lista con la excepción del nodo detallado. Por lo tanto más caro.