Ejemplo Scala (2)

scala

El programa funcional atrapa la esencia del algoritmo Quicksort de una forma concisa:

Si el arreglo está vacío o bien consiste de un solo elemento, entonces ya está ordenado, con lo que se retorna de manera inmediata.
Si el arreglo no está vacío ni es único, se escoge un factor a la mitad del arreglo tal y como si fuera un pivotee.
Se parte el arreglo en 2 subarreglos conteniendo elementos que, respectivamente, sean menores y mayores que el factor pivotee, y un tercer arreglo que contiene los elementos igual al pivotee (con el procedimiento filter).
Se ordenan los primeros 2 subarreglos por invocación recursiva de la función de ordenación. [1]
El resultado se consigue al acomodar los 3 subarreglos juntos.
[1] Esto no es precisamente lo que hace el algoritmo imperativo; el llamado siguiente de la función, parte el arreglo en 2 subarreglos conteniendo elementos menores o bien mayores o bien iguales al pivotee.
Tanto la implementación imperativa como la funcional tienen exactamente la misma dificultad asintótica – O(N;log(N)) en el caso promedio y O(N^2) en el peor de los casos. Mas donde la implementación imperativa opera sobre el arreglo que le llega como razonamiento modificándolo, la implementación funcional retorna un nuevo arreglo acomodado y deja el arreglo que le llega como razonamiento sin cambio. La implementación funcional requiere más memoria transitiva que la imperativa.

La implementación funcional hace parecer a Scala tal y como si fuera un lenguaje que se especializa en operaciones funcionales sobre arreglos. En verdad, no es así; todas y cada una de las operaciones usadas en el ejemplo son bien simples métodos de la clase sequence Seq[T], los que son una parte de la biblioteca estándar de Scala, misma incorporada en Scala. Dado a que los arreglos son instancias de Seq todos y cada uno de los métodos de sequence están libres para ellos.

Particularmente, hay un procedimiento filter que toma como razonamiento una función de predicado. Esta función de predicado mapea los elementos del arreglo a valores booleanos. El resultado de filter es un arreglo consistente con todos y cada uno de los elementos del arreglo original para los que la función de predicado es auténtica (true, en ingles). El procedimiento filter de un objeto de tipo Array[T] tiene esta estructura:

Acá, T => Boolean es del género de funciones que toma un factor de tipo T y retorna un Boolean. Las funciones como filter que toman otra función como razonamiento para retornar uno como resultado se llaman funciones de orden superior (higher-order functions, en inglés).
Scala no distingue entre identificadores y nombres de operador. Un identificador puede ser tanto una secuencia de letras y dígitos que empiecen con una letra, o bien pueden ser una secuencia de caracteres singulares, como “+”, “*”, o bien “:”. Cualquier identificador puede emplearse como un operador infijo en Scala. La operación binaria E\ op\ E’ se interpreta siempre y en toda circunstancia como una llamada del procedimiento Y también.op(E’) . Esto asimismo aplica para operadores infijos binarios los que empiecen con una letra. Por tanto, la expresión xs filter (pivote >) es equivalente a la llamada del procedimiento xs.filter(pivote >).

En el programa Quicksort, a filter se aplica 3 veces una función anónima como razonamiento. El primer razonamiento, pivote > , representa una función que toma a x como razonamiento y retorna el valor pivote > x . Este es un caso de una función parcialmente aplicada (Partially applied function, en inglés). Otra forma equivalente de redactar esta función la que muestra explícitamente al razonamiento restante es x => pivote > x. La función es anónima, o sea, no se define con un nombre. El género de factor x se omite por el hecho de que el compilador de Scala puede inferirlo de forma automática del contexto donde la función se emplea. Para resumir, xs.filter(pivote >) retorna una lista consistente con todos y cada uno de los elementos de la lista xs que sean más pequeños que pivote.

Al mirar nuevamente en detalle a la primera implementación imperativa de Quicksort, hallamos que muchos de los constructos de lenguaje empleados en la segunda solución están asimismo presentes, sin embargo, en una forma disfrazada.

Por servirnos de un ejemplo, los operadores binarios “estándar” como +, -, o bien < no se tratan de ningún modo singular. Como append, son métodos de sus operando izquierdo. Consecuentemente, la expresión i + 1 se mira como la invocación i.+(1) del procedimiento + del valor entero x.

Como es natural, un compilador es libre (y si es moderadamente inteligente, aun se espera que lo haga) de reconocer el caso singular en al llamar al procedimiento + sobre razonamientos enteros y producir código eficaz para esto en una línea.

Para un diagnóstico de fallos más eficaz y mejor, el ciclo while es un constructo primitivo en Scala. Mas de entrada, bien podría haber sido una función predefinida. Acá hay una posible implementación de él:

La función While toma como su primer factor una función de prueba, lo que no toma factores y genera un valor boolean. Como segundo factor toma una función de comando la que tampoco toma factores y genera un resultado del tipo Unit. While invoca la función de comando mientras que la función de prueba genera true.
El tipado Unit de Scala corresponde grosso modo al void en Java; se utiliza siempre y cuando una función no regrese un resultado interesante. En verdad, como Scala es un lenguaje orientado a expresiones, una función siempre y en todo momento retorna algún resultado. Si no se da una expresión de regreso de forma explícita, se acepta el valor (), que se pronuncia “unit”. Este valor es del tipo Unit. Las funciones que retornan Unit asimismo se llaman procedimientos. Acá está una formulación más “orientada a expresiones” de la función swap en la primera implementación del Quicksort, que hace esto explicito:

 

El valor que regresa esta función es sencillamente su última expresión – la palabra clave return no es precisa. Nótese que las funciones que retornan un valor explícito precisan un “=” ya antes de acotar su cuerpo o bien de delimitar sus expresiones.

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *