¡Hola, habitantes! Muchos errores de programación se deben a discrepancias en los tipos de datos. Un sistema de tipos sólido evita toda una clase de errores y garantiza la integridad de los datos en toda la aplicación. Al aprender a dominar los tipos en la práctica diaria, un desarrollador creará un mejor código y ahorrará el tiempo necesario para encontrar errores de datos complicados.
El libro le muestra cómo usar la mecanografía para crear software que no solo es seguro y funciona sin problemas, sino que también es fácil de mantener.
Los ejemplos de resolución de problemas, escritos en TypeScript, lo ayudarán a desarrollar sus habilidades para trabajar con tipos, desde tipos de datos simples hasta conceptos más complejos, como functores y mónadas.
En este libro:
- Creación de estructuras de datos basadas en tipos simples, matrices y referencias.
- Programación y tipos orientados a objetos.
- Usando genéricos y tipos de orden superior.
Este libro requiere experiencia con uno de los lenguajes de programación convencionales, como TypeScript, Java, JavaScript, C # o C ++.
Para quién es este libro
El libro está destinado a programadores en práctica. El lector debe ser bueno escribiendo código en uno de los lenguajes de programación como Java, C #, C ++ o JavaScript / TypeScript. Los ejemplos de código están en TypeScript, pero la mayor parte del material es aplicable a cualquier lenguaje de programación. De hecho, los ejemplos no siempre usan TypeScript típico. Siempre que ha sido posible, se han adaptado para que los programadores de otros lenguajes de programación puedan entenderlos. El ensamblaje de ejemplos de código se describe en el Apéndice A, y una breve hoja de trucos de TypeScript se describe en el Apéndice B.
Si está involucrado en el desarrollo de código orientado a objetos para el trabajo, es posible que haya escuchado sobre tipos de datos algebraicos (ADT), expresiones lambda, genéricos, functores, mónadas y desee comprender mejor qué son y cómo usarlos en su trabajo .
Este libro le mostrará cómo utilizar el sistema de tipos de un lenguaje de programación para diseñar un código menos propenso a errores, más modular y comprensible. Verá cómo convertir los errores de tiempo de ejecución que pueden bloquear todo el sistema en errores de compilación y detectarlos antes de que se metan en problemas.
La mayor parte de la literatura sobre sistemas de tipos está muy formalizada. El libro se centra en las aplicaciones prácticas de los sistemas de tipos; por lo tanto, contiene muy pocas matemáticas. Sin embargo, es aconsejable que comprenda los conceptos básicos de álgebra, como funciones y conjuntos. Esto es necesario para aclarar algunos de los conceptos que necesitamos.
Interadores y algoritmos generalizados
En este capítulo
- El uso de operaciones map (), filter () y reduce () no es solo para matrices.
- Resolver una amplia gama de problemas utilizando un conjunto de algoritmos comunes.
- Proporcione soporte de tipo de datos genérico para el contrato deseado.
- Implementación de una variedad de algoritmos usando diferentes categorías de iteradores.
- Implementación de algoritmos adaptativos.
Este capítulo se centra completamente en algoritmos genéricos y reutilizables adecuados para una amplia variedad de tipos y estructuras de datos.
Observamos una versión de cada una de las operaciones map (), filter () y reduce () en el Capítulo 5 cuando discutimos las funciones de orden superior. Estas funciones funcionan con matrices, pero como hemos visto en capítulos anteriores, los iteradores son una gran abstracción para trabajar con cualquier estructura de datos. Comenzaremos implementando versiones genéricas de los tres algoritmos anteriores que funcionan con iteradores y, por lo tanto, son aplicables al procesamiento de árboles binarios, listas, matrices y cualquier otra estructura de datos iterable.
Las operaciones map (), filter () y reduce () no son únicas. Hablaremos de otros algoritmos genéricos y bibliotecas de algoritmos disponibles en la mayoría de los lenguajes de programación modernos. Veremos por qué es mejor reemplazar la mayoría de los bucles con llamadas a algoritmos de biblioteca. También hablaremos un poco sobre API fluidas e interfaces de algoritmos fáciles de usar.
A continuación, repasaremos las restricciones de los tipos de parámetros; Las estructuras y algoritmos de datos genéricos pueden especificar las capacidades que deben estar presentes en sus tipos de parámetros. Esta especialización conduce a estructuras de datos y algoritmos algo menos universales que no se pueden utilizar en todas partes.
Entraremos en más detalles sobre los iteradores y hablaremos sobre sus diferentes categorías. Cuanto más especializado es un iterador, los algoritmos más eficientes son posibles con su participación. Sin embargo, no todas las estructuras de datos son capaces de admitir iteradores especializados.
Finalmente, echaremos un vistazo rápido a los algoritmos adaptativos. Permiten implementaciones más versátiles pero menos eficientes para iteradores con menos características e implementaciones más eficientes pero menos versátiles para iteradores con más características.
10.1. Operaciones de mapa (), filtro () y reducción () mejoradas
En el Capítulo 5, hablamos sobre las operaciones map (), filter () y reduce () y analizamos una de las posibles implementaciones de cada una. Estos algoritmos son funciones de orden superior porque toman otra función como argumento y la aplican a una secuencia de datos.
La operación map () aplica una función a cada elemento de la secuencia y devuelve los resultados. La operación filter () aplica una función de filtro a cada elemento y devuelve solo aquellos para los que esta función devuelve verdadero. La operación reduce () agrupa todos los valores en una secuencia usando una función y devuelve un solo valor como resultado.
Nuestra implementación del Capítulo 5 utilizó el parámetro genérico tipo T y representó secuencias como matrices de elementos de tipo T.
10.1.1. Operación Map ()
Recordemos cómo implementamos la operación map (). Teníamos dos tipos-parámetros: T y U. La función toma como argumento una matriz de valores de tipo T y una función que convierte de T a U como segundo argumento. Devuelve una matriz de valores U, como se muestra en el Listado 10.1.
Ahora, con nuestro conocimiento de iteradores y generadores, veamos en el Listado 10.2 cómo implementar map () para que pueda funcionar con cualquier Iterable <T>, no solo con matrices.
Si bien la implementación original se limitó a matrices, esta puede funcionar con cualquier estructura de datos que proporcione un iterador. Además, el código se ha vuelto mucho más compacto.
10.1.2. Operación de filtro ()
Hagamos lo mismo con filter () (listado 10.3). Nuestra implementación original esperaba una matriz de elementos de tipo T y un predicado como entrada. Permítanme recordarles que un predicado es una función que toma un elemento de algún tipo y devuelve un booleano. Si una función dada devuelve verdadero para un valor que se le pasa, entonces se dice que el valor satisface el predicado.
Al igual que con la operación map (), usaremos un Iterable <T> en lugar de una matriz e implementaremos este Iterable como un generador que produce valores que satisfacen el predicado, como se muestra en el Listado 10.4.
Nuevamente, ha resultado una implementación más lacónica, capaz de funcionar no solo con arreglos. Finalmente, modificamos la función reduce ().
10.1.3. Reducir () operación
Nuestra implementación original reduce () esperaba una matriz de elementos de tipo T, un valor inicial de tipo T (en caso de que la matriz estuviera vacía) y una operación op (). Esta operación es una función que toma dos valores de tipo T como argumentos y devuelve un valor de tipo T. La operación reduce () aplica la operación al valor inicial y el primer elemento de la matriz, almacena el resultado, aplica el misma operación al resultado y al siguiente elemento de la matriz, etc. (Listado 10.5)
Puede reescribir esta función para usar Iterable <T> en lugar de una matriz y trabajar con cualquier secuencia, como se muestra en el Listado 10.6. En este caso, no necesitamos generador. A diferencia de las dos funciones anteriores, reduce () no devuelve una secuencia de elementos, sino un solo valor.
El resto de la implementación no ha cambiado.
10.1.4. Filtrar () / reducir () canalización
Veamos cómo combinar estos algoritmos en una canalización que selecciona solo números pares de un árbol binario y los suma. Usemos la clase BinaryTreeNode <T> del Capítulo 9 con su recorrido de árbol centrado y concatenémoslo con un filtro de número par y una función reduce () que usa la suma como una operación (Listado 10.7).
Este ejemplo es una prueba viviente de la eficacia de los tipos genéricos. En lugar de implementar una nueva función para atravesar un árbol binario y sumar números pares, simplemente formamos una canalización de procesamiento específicamente para el escenario deseado.
10.1.5. Ejercicios
- Cree una canalización para manejar un iterable de tipo cadena: la concatenación de todas las cadenas no vacías.
- Cree una canalización para procesar un iterable de tipo número: seleccionando todos los números impares y elevándolos al cuadrado.
10.2. Algoritmos comunes
Discutimos los algoritmos map (), filter () y reduce (), y también mencionamos take () en el Capítulo 9. Muchos otros algoritmos se usan a menudo en pipelines. Enumeraré algunos de ellos. No veremos implementaciones, solo describiré qué argumentos (además de Iterable) reciben y cómo procesan los datos. Además, enumeraré los distintos nombres a los que se puede hacer referencia a estos algoritmos:
- map () toma como entrada una secuencia de valores de tipo T y una función (valor: T) => U, y devuelve una secuencia de valores de tipo U después de aplicar esta función a todos los valores de la entrada secuencia. También aparece bajo los nombres fmap (), select ();
- filter() T (value: T) => boolean, T, , true. where();
- reduce() T T (x: T, y: T) => T. reduce() T. fold(), collect(), accumulate(), aggregate();
- any() T (value: T) => boolean. true, ;
- all() T (value: T) => boolean. true, ;
- none() T (value: T) => boolean. true, ;
- take() T n. , n . limit();
- drop() T n. , , n. skip();
- zip() T U, , T U, , .
Hay muchos otros algoritmos para ordenar, invertir, dividir y concatenar secuencias. Afortunadamente, estos algoritmos son tan útiles y aplicables en tantas áreas que no es necesario que los implemente usted mismo. Para la mayoría de los lenguajes de programación, existen bibliotecas con implementaciones listas para usar. JavaScript tiene paquetes underscore.js y lodash, cada uno con muchos algoritmos similares. (En el momento de escribir este artículo, estas bibliotecas no admiten iteradores, solo la matriz de JavaScript incorporada y los tipos de objeto). En Java, se pueden encontrar en el paquete java.util.stream. En C #, se encuentran en el espacio de nombres System.Linq. En C ++, en el archivo de encabezado de la biblioteca estándar <algrithm>.
10.2.1. Algoritmos en lugar de bucles
Puede que se sorprenda, pero hay una buena regla general: siempre que escriba un algoritmo, verifique si hay un algoritmo de biblioteca o una canalización para la tarea. Los bucles generalmente se escriben para procesar secuencias, exactamente lo que hacen los algoritmos discutidos anteriormente.
Se prefieren los algoritmos de biblioteca a los bucles personalizados porque hay menos posibilidades de error. Los algoritmos de biblioteca están probados y se implementan de manera eficiente, y pueden usarse para hacer que el código sea más legible especificando explícitamente operaciones.
Hemos analizado varias implementaciones en este libro para comprender mejor los aspectos internos, pero rara vez es necesario implementar los algoritmos usted mismo. Si se encuentra con una tarea que está más allá del poder de los algoritmos existentes, es mejor crear una implementación genérica y reutilizable que una única y especializada.
10.2.2. Implementación de una tubería de fluidos
La mayoría de las bibliotecas proporcionan una API fluida para canalizar algoritmos. Las API fluidas son API encadenadas que hacen que su código sea mucho más fácil de leer. Veamos la diferencia entre una API fluida y una API no fluida usando la tubería de filtro / convolución de la Sección 10.1.4 (Listado 10.8) como ejemplo.
Y aunque primero aplicamos la operación filter () y luego pasamos el resultado a la operación reduce (), cuando leemos el código de izquierda a derecha, veremos reduce () antes que filter (). También es bastante difícil averiguar qué argumentos se refieren a una función particular en una canalización. La API fluida hace que su código sea mucho más fácil de leer.
Actualmente, todos nuestros algoritmos toman un objeto iterable como primer argumento y devuelven un iterador. La programación orientada a objetos mejorará nuestra API. Es posible recopilar todos nuestros algoritmos en una clase contenedora iterable. Y luego llame a cualquiera de los iterables sin especificarlo explícitamente como primer argumento, porque ahora el iterable es un miembro de la clase. Haremos esto para map (), filter () y reduce (), agrupándolos en una nueva clase FluentIterable <T> que envuelve un objeto Iterable, como se muestra en el Listado 10.9.
Basándonos en Iterable <T>, podemos crear un FluentIterable <T>, por lo que podemos reescribir nuestra tubería de filtro / reducción para que sea más fluida. Creemos un objeto FluentIterable <T>, llamemos a filter () en él, creemos un nuevo objeto FluentIterable <T> basado en sus resultados y llamemos a reduce () en él, como se muestra en el Listado 10.10.
Ahora filter () viene antes de reduce (), y está bastante claro que los argumentos se refieren a esta función. El único problema es la necesidad de crear un nuevo FluentIterable <T> después de cada llamada de función. Puede mejorar esta API reescribiendo las funciones map () y filter () para devolver un FluentIterable <T> en lugar de un IterableIterator <T>. Tenga en cuenta que no es necesario cambiar el método reduce () porque reduce () devuelve un valor único de tipo T, no un iterable.
Pero como estamos usando generadores, no podemos simplemente cambiar el tipo de retorno. La razón de ser de los generadores es proporcionar una sintaxis conveniente para las funciones, pero siempre devuelven un IterableIterator <T>. En su lugar, podemos mover las implementaciones a dos métodos privados, mapImpl () y filterImpl (), y convertir de IterableIterator <T> a FluentIterable <T> en los métodos públicos map () y filter (), como se muestra en el listado 10.11.
Esta implementación mejorada hace que sea más fácil encadenar algoritmos porque ahora todos devuelven un FluentIterable en el que todos los algoritmos se describen como métodos, como se muestra en el listado 10.12.
Ahora, en esta versión verdaderamente fluida, el código es fácil de leer de izquierda a derecha, y la sintaxis para concatenar cualquier número de algoritmos que componen la tubería parece bastante natural. Se utiliza un enfoque similar en la mayoría de las bibliotecas algorítmicas, lo que facilita al máximo el encadenamiento de múltiples algoritmos.
Dependiendo del lenguaje de programación, uno de los inconvenientes de las API de Fluent es abarrotar la clase FluentIterable con métodos para todos los algoritmos, lo que dificulta la extensión. Si está incluido en la biblioteca, entonces el código de llamada no tiene forma de agregar un nuevo algoritmo sin modificar la clase. C # tiene los llamados métodos de extensión que le permiten agregar métodos a una clase o interfaz sin tener que modificar su código. Sin embargo, no todos los idiomas tienen estas características. No obstante, en la mayoría de los casos es mejor utilizar una biblioteca de algoritmos existente en lugar de implementar una nueva desde cero.
10.2.3. Ejercicios
- Extienda la clase FluentIterable para incluir un algoritmo take () que devuelva los primeros n elementos del iterador.
- Extienda la clase FluentIterable para incluir un algoritmo drop () que omita los primeros n elementos del iterador y devuelva el resto.
10.3. Limitar los tipos de parámetros
Ya hemos visto cómo las estructuras de datos genéricas definen una forma de datos que no depende de un parámetro de tipo particular T.También observamos un conjunto de algoritmos que usan iteradores para procesar secuencias de valores de tipo T, independientemente del tipo es. Ahora, en el Listado 10.13, considere un escenario donde un tipo de datos en particular es importante: una función genérica renderAll () que toma un Iterable <T> como argumento y llama a render () en cada elemento devuelto por el iterador.
Intentar compilar esta función termina con el siguiente mensaje de error: La propiedad 'render' no existe en el tipo 'T' (al tipo 'T' le falta la propiedad 'render').
Estamos intentando llamar al método render () de un tipo genérico T, que puede no tener dicho método. En tal escenario, necesitaría restringir el tipo T solo a las encarnaciones específicas que contienen el método render ().
Limitaciones de los tipos de parámetros
Las restricciones informan al compilador sobre las capacidades que debe tener un tipo de argumento. Sin restricciones, el tipo de argumento puede ser cualquier cosa. Cuando se requiere que un tipo de datos genérico tenga ciertos miembros de clase, es con la ayuda de restricciones que reducimos el conjunto de tipos permitidos a aquellos que tienen estos miembros requeridos.
En nuestro caso, podemos definir la interfaz IRenderable, que declara el método render (), como se muestra en el Listado 10.14. Luego puede agregar una restricción en el tipo de T usando la palabra clave extiende para decirle al compilador que solo se permiten los tipos de argumentos que incorporan IRenderable.
10.3.1. Estructuras de datos genéricas restringidas
La mayoría de las estructuras de datos genéricas no requieren restricciones de tipo de parámetro. Cualquier tipo de valor se puede almacenar en una lista, árbol y matriz vinculados. Sin embargo, hay algunas excepciones, en particular, el conjunto hash.
La estructura de datos del conjunto modela el conjunto en un sentido matemático, por lo que se almacenan valores únicos en él y se descartan los duplicados. Las estructuras de datos de conjuntos generalmente incluyen métodos para unir, intersecar y restar de otros conjuntos, y también le permiten verificar si un valor dado está incluido en un conjunto. Para realizar esta verificación, puede comparar este valor con cada uno de los elementos del conjunto, aunque este no es un enfoque muy eficiente. En el peor de los casos, la comparación con cada uno de los elementos del conjunto requiere atravesar todo el conjunto. Dicho recorrido se realiza en tiempo lineal, O (n). Puede repasar estas notaciones en la barra lateral "Notación Big O", a continuación.
La implementación más eficaz es aplicar un hash a todos los valores y almacenarlos en una estructura de datos de valor clave, como un mapa hash o un diccionario. Estructuras como estas son más eficientes, pueden recuperar valores en tiempo constante , O (1). El conjunto hash envuelve el mapa hash, proporcionando una verificación eficiente para la inclusión de un elemento. Pero tiene una limitación: el tipo T debe proporcionar una función hash que tome un valor de tipo T y devuelva su valor hash de tipo número.
En algunos lenguajes de programación, el hash de todos los valores es posible describiendo el método hash en el tipo superior. Por ejemplo, el tipo de objeto Java superior incluye un método hashCode () y el tipo de objeto C # superior incluye el método GetHashCode (). Pero si el lenguaje no brinda esa posibilidad, entonces es necesaria una restricción de tipo para que solo los tipos que se pueden utilizar con hash puedan almacenarse en nuestras estructuras de datos. Por ejemplo, podemos definir la interfaz IHashable y usarla como una restricción de tipo en el tipo de clave de nuestro hashmap o diccionario genérico.
Sobre el Autor
Vlad Rishkutsia es un especialista en desarrollo de software en Microsoft con más de diez años de experiencia. Durante este tiempo, dirigió varios proyectos importantes de software y capacitó a muchos jóvenes profesionales.
Se pueden encontrar más detalles sobre el libro en el sitio web de la editorial
» Tabla de contenido
» Extracto
para los habitantes un 25% de descuento en el cupón - TypeScript
Tras el pago de la versión impresa del libro, se envía un libro electrónico por correo electrónico. correo.