Aplanar un Array

En los temas anteriores hemos visto que los recursivos sirven para resolver problemas reduciendo el tamaño del mismo hasta alcanzar un caso trivial. En esos recursivos el objetivo era alcanzar la solución con el menor número de llamadas. Pero además los recursivos sirven para recorrer una estructura de árbol, donde el objetivo no es reducir las iteraciones, sino iterar por los nodos del árbol. Un árbol se caracteriza por tener una un único nodo padre (nodo raíz) del cual descienden hijos de forma recurrente hasta llegar a un nodo final que no tiene hijos, denominados también como hojas del árbol. Esta estructura recurrente es propia para aplicar un algoritmo recursivo con el objeto de recorrer el árbol.

La estructura de árbol se utiliza en muchos casos, como en el que observa en la Figura. Se trata del árbol DOM que sirve para estructurar los elementos en un documento HTML. En un apartado al final de este tema veremos un ejemplo usando un recursivo para recorrer el DOM.

Pero empecemos con algo simple, como el Array [1, [[2, 3], 4, [5, 6]], [7, 8]], donde sus elementos son números enteros o a su vez elementos Array. Esto podría verse como una estructura de árbol. Sus hojas son los elementos finales que no tienen descendientes, siendo en este ejemplo los números enteros:

               array
                 ⇓
[i=0            i=1                i=2]
  ⇓              ⇓                  ⇓
  1     [j=0    j=1    j=2]     [j=0 j=1]
          ⇓      ⇓      ⇓         ⇓   ⇓
     [k=0, k=1]  4   [k=0, k=1]   7   8
      ⇓      ⇓         ⇓    ⇓
      2      3         5    6

En ciertos casos necesitamos aplanar un Array, cuyo objetivo es poner todos los elementos en el primer nivel del Array externo. Si aplanamos el Array anterior deberíamos obtener [1, 2, 3, 4, 5, 6, 7, 8]. Planteamos el siguiente recursivo para conseguirlo:

function myFlat(obj=null, result=[]){
    if (!Array.isArray(obj)){
        result.push(obj);
    } else {
        for (let i=0; i<obj.length; i++){
            myFlat(obj[i], result);
        }
    }
    return result;
}

El caso trivial es cuando el objeto que recibimos no es un Array, en cuyo caso lo almacenamos en el resultado inmerso como un parámetro. Cuando es un Array iteramos aplanando cada elemento. En el siguiente ejemplo lo pondremos en práctica. Aunque sólo permitirá números enteros como elementos de los Array, realmente la función para aplanar podría aceptar otros elementos, pero si fuesen objetos habría que clonarlos antes de almacenarlos en el resultado. En un apartado siguiente veremos también un método para clonar objetos.

Además ejecutaremos el método array.flat(depth) nuevo en JavaScript. Es un método aún experimental y que no está soportado por todos los navegadores. El argumento opcional depth establece la profundidad hasta donde queremos aplanar. En nuestro ejemplo el recursivo myFlat() no tiene límite de profundidad, por lo que al nuevo método hay que pasarlo con un límite infinito de profundidad, es decir, array.flat(Infinity).

También ejecutaremos un generador recursivo, mostrando que los generadores pueden actuar también recursivamente. Dado que un generador devuelve un objeto iterador, la primera llamada la hacemos con [...genFlat(array)].

function* genFlat(obj){
    if (!Array.isArray(obj)){
        yield obj;
    } else {
        for (let i=0; i<obj.length; i++){
            yield* genFlat(obj[i]);
        }
    }
}

Recorrer un objeto

Hace algún tiempo expuse un ejemplo para iterar por un objeto, ejemplo que replicaremos a continuación con algunos pequeños cambios destinados a separar con más claridad los casos triviales de los no triviales:

function view(obj) {
    let tipo = typeof obj;
    if (tipo!=="object"){
        return tipo==="undefined" ? "undefined" :
            tipo==="string" ? `"${obj}"` :
            obj.toString();
    } else if (obj===null) {
        return "null";
    } else {
        let isArray = Array.isArray(obj);
        let cad = isArray ? "[" : "{";
        for (let key of Object.getOwnPropertyNames(obj)){
            if (!isArray || /\d+/.test(key)) {
                if (cad.length>1) cad += ",";
                cad += (isArray ? "" : `"${key}":`) + view(obj[key]);
            }
        }
        cad +=  isArray ? "]" : "}";
        return cad;
    }
}

Un objeto es una colección de propiedades que son parejas clave-valor. Los valores pueden a su vez ser también objetos, por lo que el recursivo es una buena forma para iterar por todas las propiedades del objeto y extraerlas. Los casos triviales en el recursivo anterior son cuando el objeto es nulo o bien no es del tipo object, con lo que será un tipo primitivo. En estos casos devolvemos "null", "undefined" o el string del valor primitivo. Hay que entender que el valor null es también del tipo object. Entonces si es un objeto no nulo iteramos por las claves del mismo.

Los Array también son del tipo object. Podemos detectarlos con Array.isArray(), lo que nos servirá para recorrer sólo las claves numéricas del Array así como presentarlo con corchetes en lugar de llaves. Componemos el texto de una pareja key: obj[key], o sólo obj[key] si es un Array, llamando nuevamente a view(obj[key]) para ver ese sub-objeto.

let obj = {
    a: 1,
    x: {z: "abc", m: undefined},
    y: [4, null, {w: true, v: ["", 7]}]
};

Usamos también JSON.stringify(obj) para obtener una cadena de texto que representa el objeto. Coincidirá a excepción de que JSON ignora los valores undefined.

Recuerde que las claves de un objeto pueden escribirse en el código sin comillas cuando son nombres válidos de variable en JavaScript, tal como explicamos en inicialización de objetos con notación literal. Sin embargo realmente siempre se almacenan como Strings. Por eso JSON siempre los recupera como Strings y se encierran entre comillas.

Clonar un objeto

En su día expliqué como clonar un objeto. Se trata de un recursivo que recibe un objeto. Si es nulo o es un tipo primitivo lo devolvemos tal como está, con lo que estamos devolviendo una copia de ese tipo primitivo o nulo. En otro caso será un objeto no nulo que hemos de clonar. Una clonación correcta debe contemplar el clonado del prototipo, que al ser también un objeto y cuando no provenga de un constructor, podemos llamar recursivamente para copiarlo. Creamos un nuevo objeto con ese prototipo y luego iteramos por las propiedades del objeto para clonarlas.

function clone(obj) {
    let copy = obj;
    if (obj !== null && typeof obj === "object"){
        let proto = Object.getPrototypeOf(obj);
        if (!proto.hasOwnProperty("constructor")) proto = clone(proto);
        let values = Object.getOwnPropertyDescriptors(obj);
        copy = Object.create(proto, values);
        let keys = Object.getOwnPropertyNames(obj).concat(Object.getOwnPropertySymbols(obj));
        for (let key of keys){
            copy[key] = clone(obj[key]);
        }
    }
    return copy;
}

En el ejemplo de uso de este recursivo declaramos un objeto obj. En primer lugar hacemos una copia de la referencia con let obj2 = obj. Esto copia sólo la referencia, de tal forma que cualquier referencia a obj2 es como si la estuviéramos haciendo a obj. Luego clonamos el objeto en copy. Modificamos el objeto original obj y la copia copy. Comprobaremos que obj2 contiene lo mismo que obj, mientras que el cambio en copy no modifica los anteriores, por lo que es un ejemplar independiente.

let obj = {             // Objeto original
    a: 1,
    b: [true, {c: "X", d: [2, 3]}],
    e: {f: null, __proto__: {h: 4}}
};
let obj2 = obj;         // Copia sólo la referencia 
let copy = clone(obj);  // El clonado si hace una copia
obj.a = "ABC";          // Cambiamos el objeto original
copy.a = "XYZ";         // Cambiamos la copia
show(obj, result1);     // Mostramos original 
show(obj2, result2);    // Mostramos copia de la referencia
show(copy, result3);    // Mostramos clonado

Para ver el objeto usamos en la función show() un recursivo similar a view(obj) que vimos en el apartado anterior, pero que tiene más funcionalidades como la de poder ver los prototipos. Puede ver el código de esta función verObjeto().

Recorrer el DOM

Una estructura de árbol es el DOM (Document Object Model), que viene a ser un modelo de objetos para representar un documento HTML. El siguiente recursivo recorre el árbol de elementos que son hijos de un elemento dado.

function dom(element=null, nivel=0) {
    let arr = [];
    let tab = "\n" + " ".repeat(nivel);
    if (!element){
        arr.push(`${tab}NULL`);
    } else {
        let type = element.nodeType;
        if (type===1){
            arr.push(`${tab}<${element.tagName.toLowerCase()}>`);
            nivel += 2;
            for (let hijo of element.childNodes){
                arr.push(dom(hijo, nivel));
            }
        } else if (type===3) {
            arr.push(`${tab}${shortText(element.textContent)}`);
        } else if (type===8) {
            arr.push(`${tab}<!-- ${shortText(element.textContent)} -->`);
        } else {
            arr.push(`${tab}nodeType=${type}`);
        }
    }
    return arr;
}

Un caso trivial es cuando el elemento es nulo. En otro caso el árbol llega a una hoja final si el tipo de nodo no es un elemento HTML (tipo 1). Si es un elemento HTML iteramos por todos sus hijos llamando por cada uno a dom(hijo, nivel). El nivel nos servirá para hacer un indentado en el código esquemático que extraemos.

La función shortText() recortará el texto para no alargar en exceso el ejemplo.

function shortText(text){
    return text.replace(/\s+/g, " ").trim().substring(0, 20) + "...";
}

En este ejemplo primero pulsaremos "Ejecutar" que extraerá el subárbol del elemento padre que contiene la sección de este ejemplo. Luego podemos navegar usando las propiedades del propio DOM como parentElement, previousSibling, nextSibling y firstChild.