Desestructuracíon y recursividad en Javascript 2015

Arrays literales

Los arrays en javascript son representaciones nativas de las listas. Las listas son importantes porque representan colecciones ordenadas de cosas, y la ordenacion de esas colecciones es una abstraccion fundamental para dar sentido a la realidad.

javascript tiene una sintaxis literal para crear arrays. Los corchetes [ ]. Podemos crear una lista vacia:

1
2
[]
//-> []

Tambien podemos crear un array con uno o mas elementos colocandolos entre los corchetes ([ ]) y separandolos por comas. El espacio en blanco es opcional aunque se recomienda por legibilidad:

1
2
3
4
[1]
//-> [1]
[2,3,4]
//-> [2,3,4]

Cualquier expresion funcionara:

1
2
3
4
5
[ 2,
3,
2 + 2
]
//=> [2,3,4]

Incluidas expresiones que denoten otros arrays:

1
[[[[[]]]]]

Esto es un array con un elemento que es un array de arrays con un elemento que es un array con un elemento que es un array con un elemento vacio. Aunque esto parece algo que nunca jamas nadie construiria, muchos estudiantes han trabajado con casi exactamente lo mismo cuando se exploran diversas maneras para la construccion de la aritmetica de la teooria de categorias.

Cualquier expresion puede hacerlo:

1
2
3
4
const wrap = (something) => [something];
wrap("lunch")
//=> ["lunch"]

Los arrays literales son expresiones, y los arrays son tipos por referencia. Podemos ver que cada vez que se evalua un array literal, obtenemos un nuevo array distinto, incluso si contiene los mismos elementos exactos.

1
2
3
4
5
6
7
8
9
10
[] === []
//=> false
[2 + 2] === [2 + 2]
//=> false
const array_of_one = () => [1];
array_of_one() === array_of_one()
//=> false

Desestructurando arrays.

La desestructuración es una caracteristica que se remonta a Common Lisp, si no antes. Ya vimos como construir una matriz usando un array literal [, expresiones, , y ]. Aqui hay un ejemplo de un array literal que usa un nombre:

1
const wrap = (something) => [something];

vamos a ampliar esto para que use un bloque y un nombre adicional:

1
2
3
4
5
6
7
8
const wrap = (something) => {
const wrapped = [something];
return wrapped;
}
wrap("package")
//=> ["package"]

La linea const wrapped = [something]; es interesante. En el lado izquierdo tenemos un nombre que sera vinculado, y en el lado derecho un array literal. Un template para construir un array, muy parecido a una cadena cuasi-literal.

En Javascript, nosotros podemos invertir la declaracion y colocar el template en la izquierda y el valor en la derecha.

1
2
3
4
5
6
7
8
const unwrap = (wrapped) => {
const [something] = wrapped;
return something;
}
unwrap(["present"])
//=> "present"

La declaración const [something] = wrapped; desestructura el array representado por wrapped, une el valor de su unico elemento al nombre somehing. Podemos hacer lo mismo con mas de un elemento.

1
2
3
4
5
6
7
8
const surname = (name) => {
const [first, last] = name;
return last;
}
surname(["Reginald", "Braithwaite"])
//=> "Braithwaite"

Podriamos lograr lo mismo con (name) => name[1], pero la desestructuracion es un codigo que se asemeja a los datos que consume, un estilo valioso de programación.

La desestructuracion tambien se puede añidar:

1
2
3
4
5
6
7
8
const description = (nameAndOccupation) => {
const [[first, last], occupation] = nameAndOccupation;
return `${first} is a ${occupation}`;
}
description([["Reginald", "Braithwaite"], "programmer"])
//=> "Reginald is a programmer"

Recolección

Ha veces tenemos que extraer arrays desde arrays. Este es el patron mas comun:
La extraccion de la cabeza y la recoleccion de todo el resto del array excepto la cabeza:

1
2
3
4
5
6
const [car, ...cdr] = [1, 2, 3, 4, 5];
car
//=> 1
cdr
//=> [2, 3, 4, 5]

car y cdr sor terminos arcanos que se remontan a una implementacion de Lisp que corria en las computadoras IBM 704. Algunos otros lenguajes llaman a esto first y butFirst, o head y tail. Nosotros vamos a usar una convención comun y llamar a las variables que recogemos como rest, pero refiriendonos al operador como recolector.

Por desgracia, la notacion no nos provee de una capacidad universal de pattern-maching. Por ejemplo, no podemos escribir:

1
2
3
4
const [...butLast, last] = [1, 2, 3, 4, 5];
//=> ERROR
const [first, ..., last] = [1, 2, 3, 4, 5];
//=> ERROR

Tambien es importante tener un cuenta que la notacion , puede estar al principio. Por ejemplo en el caso de un constructor como:

1
const date = new Date(...[2015, 1, 1]);

Ahora, cuando introdujimos desestructuración, vimos que es kind-of-sort-of el reverso de arrays literales. Entonces si

1
const wrapped = [something];

Entonces:

1
const [unwrapped] = something;

¿Cual es la inversa de la recoleccion?, Lo sabemos ahora:

1
const [car, ...cdr] = [1, 2, 3, 4, 5];

Vamos a probar esto:

1
2
3
4
const oneTwoThree = ["one", "two", "three"];
["zero", ...oneTwoThree]
//=> ["zero","one","two","three"]

¡Funciona! nosotros podemos usar ... para colocar los elementos de una matriz dentro de otra matriz. Decimos que el uso de ... para desestructurar esta reuniendo, y usandolo con un literal para insertar elementos es llamado “extension”.

Desestructurando paramentros.

Considere la forma de pasar los argumentos a los parametros de una función.

1
2
3
foo()
bar("smaug")
baz(1, 2, 3)

Esto es muy parecido a un array literal. Y considere como ligamos valores a nombres de los parametros.

1
2
3
const foo = () => ...
const bar = (name) => ...
const baz = (a, b, c) => ...

Esto luce igual que la desestructuración. Y actua igual que la desestructuración. Solo hay una diferencia: no hemos probado la recolección. Vamos a hacer eso:

1
2
3
4
5
6
7
8
9
const numbers = (...nums) => nums;
numbers(1, 2, 3, 4, 5)
//=> [1,2,3,4,5]
const headAndTail = (head, ...tail) => [head, tail];
headAndTail(1, 2, 3, 4, 5)
//=> [1,[2,3,4,5]]

La recolección trabaja con parametros!. Esto es muy util de echo, y vamos a ver más de ella en un momento.

Auto-Similaridad

Vimos que la idea básica de poner un array junto con una expresion de array literal era la inversa o contraria de desarmarlo con una asignación desestructurada.

Vamos a ser un poco mas especiicos. Algunas estructuras de datos, como las listas, pueden ser obviamente vistas como una colección de elementos. Algunas estan vacias, otras tendran tres elementos, otras cuarenta y dos, algunas contienen numeros, otras contienen cadenas, algunas una mexcla de elementos, existen todo tipo de listas.

Pero tambien podemos definir una lista ecribiendo algunas reglas para la construccion de las mismas. Una de las mas sencillas y de mas larga data en las ciencias de la computación, es decir que una lista es:

  1. Vacia, o;
  2. Consta de un elemento concatenado con una lista.

Convirtamos nuestras reglas en arrays literales. La primer regla es simple: [] es una lista. ¿Y que hay hacerca de la segunda regla?. Podemos expresar esto usando una extensión. Dado un elemento e y una lista list, [e, ...list] es la lista. Podemos verificar esto de forma manual mediante la creacion de una lista.

1
2
3
4
5
6
7
8
9
10
11
[]
//=> []
["baz", ...[]]
//=> ["baz"]
["bar", ...["baz"]]
//=> ["bar","baz"]
["foo", ...["bar", "baz"]]
//=> ["foo","bar","baz"]

Gracias al paralelismo entre arrays literales + las extensiones con desestructuración + rest, tambien podemos usar las mismas reglas para descomponer listas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const [first, ...rest] = [];
first
//=> undefined
rest
//=> []:
const [first, ...rest] = ["foo"];
first
//=> "foo"
rest
//=> []
const [first, ...rest] = ["foo", "bar"];
first
//=> "foo"
rest
//=> ["bar"]
const [first, ...rest] = ["foo", "bar", "baz"];
first
//=> "foo"
rest
//=> ["bar","baz"]

Para el proposito de esta exploración, vamos a suponer lo siguiente:

1
2
3
4
5
6
7
8
9
10
const isEmpty = ([first, ...rest]) => first === undefined;
isEmpty([])
//=> true
isEmpty([0])
//=> false
isEmpty([[]])
//=> false

Armados con nuestra definición de una lista vacia y con lo que ya hemos aprendido, podemos construir una gran cantidad de funciones que operan con arrays. Sabemos que podemos obtener la longitud de un array mediante Array.length. Pero como un ejercicio, ¿como podemos escribir una funcion length usando solo lo que ya tenemos?

Primero, especificamos lo que llamamos un caso base terminal. ¿Cual es la longitud de un array vacio? 0. Asi que vamos a empezar nuestra función con la observación de que si un array esta vacio, la longitud es 0:

1
2
3
4
const length = ([first, ...rest]) =>
first === undefined
? 0
: // ???

Ahora necesitamos algo para cuando el array no este vacio. Si un array no esta vacio y lo dividimos en dos partes, first y rest, la longitud del array va a ser: length(first) + length(rest). Pues bien, la longitud de first es 1, debido a que hay solo un elemento en la parte delantera. Pero no sabemos la longitud de rest. Si solo hubiese una función a la cual llamar… ¡Lo tengo! length!.

1
2
3
4
const length = ([first, ...rest]) =>
first === undefined
? 0
: 1 + length(rest);

Probemos esto!.

1
2
3
4
5
6
7
8
length([])
//=> 0
length(["foo"])
//=> 1
length(["foo", "bar", "baz"])
//=> 3

Nuestra función length es recursiva, osea que se llama a si misma. Esto tiene mucho sentido porque nuestra definición de una lista es recursivo, y si una lista es auto-similar, es natural para crear un algoritmo que sea tambien auto-similar.

recursión lineal.

La “recursión” algunas veces parece un truco de una fiesta geek. Hay incluso una broma acerca de esto.

When promising students are trying to choose between pure mathematics and applied engineering, they are given a two-part aptitude test. In the first part, they are led to a laboratory bench and told to follow the instructions printed on the card. They find a bunsen burner, a sparker, a tap, an empty beaker, a stand, and a card with the instructions “boil water.”

Of course, all the students know what to do: They fill the beaker with water, place the stand on the burner and the beaker on the stand, then they turn the burner on and use the sparker to ignite the flame. After a bit the water boils, and they turn off the burner and are lead to a second bench.

Once again, there is a card that reads, “boil water.” But this time, the beaker is on the stand over the burner, as left behind by the previous student. The engineers light the burner immediately. Whereas the mathematicians take the beaker off the stand and empty it, thus reducing the situation to a problem they have already solved.

Hay mas en las soluciones recursivas que una simple funcion que se invoca a si misma.
Los algoritmos recursivos siguen la estrategia “divide y venceras” para solventar los problemas:

  1. Divide los problemas en problemas mas pequeños.
  2. Si un problema tiene una solucion mas pequeña, entonces se resuelve el problema mas pequeño.
  3. Si un problema pequeño no es facilmente solucionable, entonces “divide el problema en otros mas pequeños y conquistalo”.
  4. Cuando se han resuelto todos los problemas pequeños, entonces componerlos juntos en una gran solucion.

Los grandes elementos de “divide y venceras” son un metodo para descomponer un problema en problemas mas pequeños y manejables, una prueba para el problema mas pequeño posible, y un medio para poner las piezas juntas.

Nuestras soluciones son un poco mas simples en las que en realidad no rompemos un problema en multiples piezas, rompemos una pieza del problema cuando puede o no ser solucionable, y la resolvemos antes de pegarla en una solucion para el resto del problema.

Un muy buen algoritmo recursivo es aquel que es paralelo a la naturaleza recursiva de los datos que estan siendo manipulados. Esta forma simple de “divide y venceras” es comunmente llamada “recursion lineal”. Es muy util y facil de entender, y es paralelo a la definicion lineal self-similar que hicimos para las listas. Tomemos otro ejemplo. Hay veces que queremos aplanar un array, esto es, un array de arrays que necesita ser convertido en una serie de elementos que no son matrices.

Ya sabemos como dividir las matrices en trozos mas pequeños. ¿Como podemos decidir si un problema tiene o no una solucion mas pequeña?. Necesitamos una prueba para el caso base. Afortunadamente, hay algo a lo largo de estas lineas proporcionado para nosotros.

1
2
3
4
5
Array.isArray("foo")
//=> false
Array.isArray(["foo"])
//=> true

El caso base sera que intentar aplanar un array vacio producira un array vacio. El siguiente caso base es que si un elemento no es un array pues que no se aplane, y lo pondremos junto con el resto de los elementos en la solución directamente. Mientras que si un elemento si es un array, lo vamos a aplanar y lo pondremos junto con el resto de nuestra solución.

Asi que de un primer vistazo, nuestra funcion flatten puede verse asi:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const flatten = ([first, ...rest]) => {
if (first === undefined) {
return [];
}
else if (!Array.isArray(first)) {
return [first, ...flatten(rest)];
}
else {
return [...flatten(first), ...flatten(rest)];
}
}
flatten(["foo", [3, 4, []]])
//=> ["foo",3,4]

Una vez más, la solucion muestra directamente los elementos importantes: Dividir el problema en subproblemas mas pequeños, detectar cuales son los casos base (cuando se considerara que la funcion debe finalizar), resolver los casos base antes que nada y componer la solucion a partir de los casos base antes resueltos.

Mapear (Mapping).

Otro problema común es aplicar una función a cada elemento de un array. Javascript cuenta con una funcion interna para eso, pero vamos a escribir nuestra propia especificacion para ilustrar el uso de la recursion lineal.

Si quisieramos elevar al cuadrado cada numero en una lista, podriamos escribir:

1
2
3
4
5
6
7
8
const squareAll = ([first, ...rest]) =>
first === undefined
? []
: [first * first, ...squareAll(rest)];
squareAll([1, 2, 3, 4, 5])
//=> [1,4,9,16,25]

Y si quisieramos saber que elementos de un array son true o false podriamos escribir:

1
2
3
4
5
6
7
const truthyAll = ([first, ...rest]) =>
first === undefined
? []
: [!!first, ...truthyAll(rest)];
truthyAll([null, true, 25, false, "foo"])
//=> [false,true,true,false,true]

Este caso especifico de recursividad lineal es llamado “maping” (o mapeo), y no es necesario escribir constantemente el mismo patron una y otra vez. Las funciones en javascript pueden tener funciones como argumentos, asi que vamos a “extraer” lo que hay que hacer para cada elemento en una funcion aparte, y separarlo de la actividad tomando un array aparte, haciendo lo que tenga que hacer, y juntando los elementos modificados en otro array.

Dada la signatura:

1
const mapWith = (fn, array) => // ...

Podriamos escribir esto usando un operador ternario. Incluso en esta pequeña funcion, podemos identificar facilmente el caso base, la pieza que se rompe, y recomponer la solución.

1
2
3
4
5
6
7
8
9
10
const mapWith = (fn, [first, ...rest]) =>
first === undefined
? []
: [fn(first), ...mapWith(fn, rest)];
mapWith((x) => x * x, [1, 2, 3, 4, 5])
//=> [1,4,9,16,25]
mapWith((x) => !!x, [null, true, 25, false, "foo"])
//=> [false,true,true,false,true]

Pliegues (Folding)

Con la excepción del ejemplo de length que hicimos al comienzo, todos nuestros ejemplos hasta ahora implican la reconstruccion de una solución usando extensiones. Pero ellos no la necesitan. Una función para calcular la suma de los cuadrados de una lista de números podría tener este aspecto:

1
2
3
4
5
6
7
const sumSquares = ([first, ...rest]) =>
first === undefined
? 0
: first * first + sumSquares(rest);
sumSquares([1, 2, 3, 4, 5])
//=> 55

Aqui hay dos diferencias entre sumSquares y nuestros mapas anteriores.

  1. Dado un caso base de una lista vacia, retornamos un 0 en lugar de una lista vacia, y;
  2. Concatenamos el cuadrado de cada elemento al resultado de aplicar sumSquares al resto de los elementos.

Vamos a reescribir mapWith para que podamos utilizar esto para sumar cuadrados.

1
2
3
4
const foldWith = (fn, terminalValue, [first, ...rest]) =>
first === undefined
? terminalValue
: fn(first, foldWith(fn, terminalValue, rest));

y ahora que tenemos una funcion que hace un poco mas que nuestra funcion map.

1
2
3
foldWith((number, rest) =>
number * number + rest, 0, [1, 2, 3, 4, 5])
//=> 55

Nuestra función foldWith es una generalización de nuestra función mapWith. Podemos representar un mapa como un pliegue, solo tenemos que suministrar el array y recompilar el codigo.

1
2
3
4
5
const squareAll = (array) =>
foldWith((first, rest) => [first * first, ...rest], [], array);
squareAll([1, 2, 3, 4, 5])
//=> [1,4,9,16,25]

Y si nos gusta, podemos escribir mapWith usando foldWith:

1
2
3
4
5
6
const mapWith = (fn, array) =>
foldWith((first, rest) => [fn(first), ...rest], [], array);
const squareAll = (array) => mapWith((x) => x * x, array);
squareAll([1, 2, 3, 4, 5])
//=> [1,4,9,16,25]

Y para volver a nuestro primer ejemplo, nuestra version de length, podemos reescribirlo como un pliegue:

1
2
3
4
5
const length = (array) =>
foldWith((first, rest) => 1 + rest, 0, array);
length([1, 2, 3, 4, 5])
//=> 5

¿Que significa todo esto?

Algunas estructuras de datos, como las listas, pueden ser definidas como “auto similares”, cuando se trabaja con estructuras de datos auto-similares, un algoritmo recursivo es paralelo a la auto similitud de los datos.

La recursividad lineal es un componente basíco de los algoritmos. Estas formas basícas son paralelas a las estructuras de datos de forma lineal como la construcción de listas: Esto ayuda a que sea comprensible. Sus casos especiales de mapeos y folding son especialmente utiles y se pueden utlizar para construir otras funciones. Y finalmente, mientras que folding es un caso especial de recursion lineal, mapping es un caso especial de folding.

Y por ultimo pero no menos importante, la desestructuración, extensión, y la recoleccion hacen que todo esto sea muy natural de expresar en JavaScript ES-6.

Comentarios