Introducción

JavaScript funcional

Hace ya algún tiempo que han empezado a aparecer las técnicas de programación funcional en Javascript:

• Bibliotecas como UnderscoreJS permiten al desarrollador aprovechar funciones probadas como map, filter y reduce para crear programas más grandes a partir de programas más pequeños mediante composición:

  1   var sumOfPrimes =
  2       _.chain(_.range(1000))
  3        .filter(isPrime)
  4        .reduce(function(x, y) {
  5            return x + y;
  6        })
  7        .value();
  

• La programación asíncrona en NodeJS se apoya firmemente en las funciones como valores de primera clase para definir retrollamadas (callbacks).

  1   require('fs').readFile(sourceFile, function (error, data) {
  2     if (!error) {
  3       require('fs').writeFile(destFile, data, function (error) {
  4         if (!error) {
  5           console.log("File copied");
  6         }
  7       });
  8     }
  9   });
  

• Bibliotecas como React y virtual-dom modelan las vistas como funciones puras sobre el estado de la aplicación.

Las funciones permiten una forma simple de abstracción que puede resultar en grandes ganancias en productividad. Sin embargo, la programación funcional en JavaScript tiene sus propias desventajas. JavaScript es verboso, no tipado, y carece de formas potentes de abstracción. El JavaScript no restringido hace también el razonamiento ecuacional muy difícil.

PureScript es un lenguaje de programación cuyo objetivo es abarcar estos problemas. Proporciona sintaxis ligera, que nos permite escribir código muy expresivo que sigue siendo claro y legible. Usa un rico sistema de tipos para soportar abstracciones potentes. También genera código rápido e inteligible, cosa importante cuando hay que interoperar con JavaScript u otros lenguajes que compilan a JavaScript. Total, espero convencerte de que PureScript consigue un equilibrio muy práctico entre el poder teórico de la programación funcional pura y el estilo de programación rápida y flexible de JavaScript.

Tipos e inferencia de tipos

El debate sobre los lenguajes de tipado estático contra los de tipado dinámico está bien documentado. PuseScript es un lenguaje de tipado estático, lo que significa que el compilador puede dar a un programa correcto un tipo que indica su comportamiento. A la inversa, los programas a los que no se les puede dar un tipo son programas incorrectos, y serán rechazados por el compilador. En PureScript, al contrario que en los lenguajes de tipado dinámico, los tipos existen únicamente en tiempo de compilación, y no tienen representación en tiempo de ejecución.

Es importante notar que, de varias maneras, los tipos en Purescript no son como los tipos que has visto en otros lenguajes como Java o C#. Aunque sirven el mismo propósito a un nivel alto, los tipos en PureScript están inspirados por lenguajes como ML y Haskell. Los tipos de PureScript son expresivos, permitiendo al desarrollador hacer afirmaciones sólidas sobre sus programas. Más importante, el sistema de tipos de PureScript soporta inferencia de tipos requiriendo muchas menos anotaciones de tipo explícitas que otros lenguajes, convirtiendo el sistema de tipos en una herramienta en lugar de en un estorbo. Un simple ejemplo, el siguiente código define un número, pero no hay mención del tipo Number en ningún sitio del código:

1 iAmANumber =
2   let square x = x * x
3   in square 42.0

Un ejemplo más elaborado muestra que la corrección de los tipos puede ser confirmada sin anotación de tipos, incluso cuando existen tipos que son desconocidos para el compilador:

1 iterate f 0 x = x
2 iterate f n x = iterate f (n - 1) (f x)

Aquí, el tipo de x es desconocido, pero el compilador sigue pudiendo verificar que iterate obedece las reglas del sistema de tipos, sin importar qué tipo pueda tener x.

En este libro, intentaré convencerte (o reafirmar tu creencia) de que los tipos estáticos no sólo son medios para ganar confianza en la corrección de tus programas, sino que también ayudan al desarrollo por derecho propio. Refactorizar una base de código extensa en JavaScript puede ser difícil para cualquier cosa que no sean las abstracciones más simples, pero un sistema de tipos expresivo junto a un comprobador de tipos puede incluso convertir la refactorización en una experiencia divertida e interactiva.

Además, la red de seguridad proporcionada por un sistema de tipos permite formas de abstracción más avanzadas. De hecho, PureScript proporciona una poderosa forma de abstracción que es fundamentalmente guiada por tipos: las clases de tipos (type classes) populares en el lenguaje de programación funcional Haskell.

Programación web políglota

La programación funcional tiene sus historias de éxito, aplicaciones donde ha sido particularmente exitosa: análisis de datos, análisis sintáctico, implementación de compiladores, programación genérica o paralelismo por nombrar unas cuantas.

Sería posible practicar desarrollo de aplicaciones de extremo a extremo en un lenguaje funcional como PureScript. PureScript proporciona la habilidad de importar código JavaScript existente, proporcionando tipos para sus valores y funciones, y usar entonces esas funciones en código PureScript normal. Veremos este enfoque más tarde en el libro.

Sin embargo, una de las fortalezas de PureScript es su interoperabilidad con otros lenguajes que compilan a JavaScript. Otro enfoque sería usar PureScript como un subconjunto del desarrollo de tu aplicación y usar otro(s) lenguajes para escribir el resto del código JavaScript.

Aquí hay algunos ejemplos:

• Lógica central escrita en PureScript, con la interfaz de usuario escrita en JavaScript.
• Aplicación escrita en JavaScript u otro lenguaje que compile a JavaScript, con pruebas escritas en PureScript.
• PureScript usado para automatizar las pruebas de interfaz de usuario para una aplicación ya existente.

En este libro, nos vamos a enfocar en resolver pequeños problemas con PureScript. Las soluciones se podrían integrar en una aplicación más grande, pero también veremos como llamar a código PureScript desde JavaScript y viceversa.

Prerrequisitos

Los requerimientos de software para este libro son mínimos: El primer capítulo te guiará para preparar un entorno de desarrollo desde cero, y las herramientas que vamos a usar están disponibles en los repositorios estándar de la mayoría de sistemas operativos modernos.

El compilador de PureScript se puede descargar como una distribución binaria o se puede construir a partir de los fuentes en cualquier sistema que tenga una instalación reciente del compilador de Haskell GHC, el siguiente capítulo dará los pasos.

El código de esta versión es compatible con las versiones 0.11.* del compilador de PureScript.

Sobre ti

Voy a asumir que estas familiarizado con JavaScript. Cualquier familiaridad previa con herramientas comunes del ecosistema JavaScript como NPM y Gulp serán beneficiosas si deseas adaptar la configuración estándar para tus necesidades, pero dicho conocimiento no es necesario.

No se necesita ningún conocimiento previo de programación funcional, pero ciertamente no hace daño. Las ideas nuevas estarán acompañadas de ejemplos prácticos, de manera que seas capaz de formar una intuición para los conceptos de programación funcional que usaremos.

Los lectores que estén familiarizados con el lenguaje de programación Haskell reconocerán un montón de las ideas y sintaxis presentadas en este libro, ya que PureScript está fuertemente influenciado por Haskell. Sin embargo, dichos lectores deben entender que hay unas cuantas diferencias importantes entre PureScript y Haskell. No siempre va a ser apropiado intentar aplicar ideas de un lenguaje en el otro, aunque muchos de los conceptos presentados aquí tendrán una interpretación en Haskell.

Cómo leer este libro

Los capítulos de este libro son bastante autocontenidos. Sin embargo, un principiante con poca experiencia en programación funcional debería estudiar los capítulos en orden. Los primeros capítulos sientan las bases requeridas para entender el material que aparece más tarde en el libro. Un lector que se sienta cómodo con las ideas de la programación funcional (especialmente uno con experiencia en un lenguaje fuértemente tipado como ML o Haskell) probablemente será capaz de adquirir una comprensión general del código en los capítulos posteriores del libro sin leer los capítulos iniciales.

Cada capítulo se va a enfocar en un único ejemplo práctico, proporcionando la motivación para cualquier idea nueva introducida. El código de cada capítulo está disponible en este repositorio GitHub. Algunos capítulos incluirán fragmentos de código tomados del código fuente del capítulo, pero para adquirir un entendimiento completo debes leer el código del repositorio junto al material del libro. Las secciones más largas contendrán fragmentos más cortos que puedes ejecutar en el modo interactivo (PSCi) para ayudarte a entender.

Los ejemplos de código aparecerán en una fuente monoespaciada, como sigue:

1 module Example where
2 
3 import Control.Monad.Eff.Console (log)
4 
5 main = log "Hello, World!"

Los comandos que deben escribirse en la línea de comandos estarán precedidos por un símbolo de dólar:

1 $ pulp build

Normalmente, estos comandos estarán orientados a usuarios de Unix, de manera que los usuarios de Windows tendrán que hacer pequeños cambios como modificar el separador de ficheros o reemplazar los comandos empotrados de shell con sus equivalentes de Windows.

Los comandos que se deben escribir en el indicador de comandos de modo interactivo de PSCi estarán precedidos por un signo ‘mayor que’.

1 > 1 + 2
2 3

Cada capítulo contendrá ejercicios etiquetados con su nivel de dificultad. Es muy recomendable que intentes hacer los ejercicios de cada capítulo para entender el material completamente.

Este libro pretende proporcionar una introducción al lenguaje PureScript para principiantes, pero no es la clase de libro que proporciona una lista de soluciones ‘plantilla’ para problemas. Para los principiantes, este libro debe ser un reto divertido, y lograrás sacarle el mayor partido si lees el material, intentas hacer los ejercicios y, lo más importante, intentas escribir algún código por tu cuenta.

Consiguiendo ayuda

Si te atascas en algún punto, hay un número de recursos disponibles online para aprender PureScript:

• El canal IRC de PureScript es un sitio estupendo para hablar sobre los problemas que puedas estar teniendo. Entra con tu cliente IRC en irc.freenode.net y conéctate al canal #purescript.
• El sitio web de PureScript contiene enlaces a varios recursos de aprendizaje, incluyendo ejemplos de código, videos y otros recursos para principiantes.
• El repositorio de documentación de PureScript contiene artículos y ejemplos de una amplia variedad de tópicos, escritos por desarrolladores y usuarios de PureScript.
• Try PureScript! es un sitio web que permite a los usuarios compilar código PureScript en el navegador web y contiene varios ejemplos de código simples.
• Pursuit es una base de datos donde puedes buscar tipos y funciones de PureScript.

Si prefieres aprender leyendo ejemplos, las organizaciones de Github purescript, purescript-node y purescript-contrib contienen un montón de ejemplos de código PureScript.

Acerca del autor

Soy el desarrollador original del compilador de PureScript. Vivo en Los Angeles, California, y empecé a programar a una edad temprana en BASIC sobre un ordenador personal de 8 bits, el Amstrad CPC. Desde entonces he trabajado profesionalmente en una variedad de lenguajes de programación (incluyendo Java, Scala, C#, F#, Haskell y PureScript).

No muy tarde en mi carrera profesional, empecé a apreciar la programación funcional y sus conexiones con las matemáticas, y disfrutaba aprendiendo conceptos de programación funcional usando el lenguaje de programación Haskell.

Empecé a trabajar en el compilador de PureScript como respuesta a mi experiencia con JavaScript. Me encontré usando técnicas de programación funcional que había adquirido en lenguajes como Haskell, pero quería un entorno más escrupuloso en el que aplicarlas. Las soluciones del momento incluían varios intentos de compilar Haskell a JavaScript conservando su semántica (Fay, Haste, GHCJS), pero estaba interesado en ver si tendría éxito afrontando el problema desde el otro lado - intentando mantener la semántica de JavaScript, disfrutando la sintaxis y el sistema de tipos de un lenguaje como Haskell.

Mantengo un blog, y se me puede encontrar en Twitter.

Acerca de la traducción

Este libro es una traducción de PureScript By Example de Phil Freeman

Dado que muchos de los términos usados en el libro son de uso común en su forma original inglesa y sus correspondientes traducciones (buenas o malas) no lo son tanto, he incluido en el texto (donde he considerado útil) el término original en itálica y entre paréntesis. La traducción al castellano está en este repositorio GitHub.

Agradecimientos

Me gustaría dar las gracias a los muchos contribuyentes que ayudaron a que PureScript alcanzara su estado actual. Sin el enorme esfuerzo colectivo que se ha hecho en el compilador, herramientas, bibliotecas, documentación y pruebas, el proyecto habría fracasado sin duda.

El logo de PureScript que aparece en la portada de este libro fue creado por Gareth Hughes, y es utilizado bajo los términos de la licencia Creative Commons Attribution 4.0.

Finalmente, me gustaría dar las gracias a todos los que me han aportado comentarios y correcciones sobre el contenido de este libro.

Empezando

Objetivos del capítulo

En este capítulo, el objetivo será preparar un entorno de desarrollo para PureScript y escribir nuestro primer programa en PureScript.

Nuestro primer proyecto será una biblioteca PureScript muy simple, que proporcionará una única función para calcular la longitud de la diagonal de un triángulo rectángulo.

Introducción

Estas son las herramientas que vamos a usar para preparar nuestro entorno de desarrollo para PureScript:

• purs - El propio compilador de PureScript.
• npm - El gestor de paquetes de Node, que nos ayudará a instalar el resto de herramientas de desarrollo.
• Pulp - Una herramienta de línea de comandos que automatiza muchas de las tareas asociadas a la gestión de proyectos PureScript.

El resto del capítulo te guiará en la instalación y configuración de estas herramientas.

Instalando PureScript

La manera recomendada de instalar el compilador de PureScript es descargar una distribución binaria para tu plataforma en el sitio web de PureScript.

Debes verificar que los ejecutables del compilador de PureScript están disponibles en tu ruta de ejecutables. Intenta ejecutar el compilador de PureScript en la línea de comandos para comprobarlo:

1 $ purs

Otras opciones para instalar el compilador de PureScript:

• Mediante NPM: npm install -g purescript.
• Construir el compilador a partir del código fuente. Las instrucciones están disponibles en el sitio web de PureScript.

Instalando las herramientas

Si no tienes una instalación funcional de NodeJS, debes instalarlo. Esto instalará también el gestor de paquetes npm en tu sistema. Asegúrate de que tienes npm instalado y disponible en tu ruta de ejecutables.

También necesitarás instalar la herramienta de línea de comandos Pulp y el gestor de paquetes Bower usando npm como sigue:

1 $ npm install -g pulp bower

Esto dejará las herramientas de línea de comandos pulp y bower en tu ruta de ejecutables. En este punto tienes todas las herramientas necesarias para crear tu primer proyecto PureScript.

¡Hola, PureScript!

Empecemos simple. Usaremos Pulp para compilar y ejecutar un simple programa “Hello World!”.

Comienza creando un proyecto en un directorio vacío usando el comando pulp init:

1 $ mkdir my-project
2 $ cd my-project
3 $ pulp init
4 
5 * Generating project skeleton in ~/my-project
6 
7 $ ls
8 
9 bower.json	src		test

Pulp ha creado por nosotros dos directorios, src y test, y un fichero de configuración bower.json. El directorio src contendrá nuestros ficheros fuente y el directorio test nuestras pruebas. Usaremos el directorio test más adelante.

Modifica el fichero src/Main.purs para que contenga lo siguiente:

1 module Main where
2 
3 import Control.Monad.Eff.Console
4 
5 main = log "Hello, World!"

Este pequeño ejemplo ilustra unas cuantas ideas clave:

• Todos los ficheros comienzan con una cabecera de módulo. Un nombre de módulo consiste en una o más palabras comenzando por mayúsculas y separadas por puntos. En este caso hemos usado una única palabra, pero Mi.Primer.Modulo seria un nombre de módulo igualmente válido.
• Los módulos se importan usando su nombre completo, incluyendo los puntos que separan las partes del nombre de módulo. Aquí, importamos el módulo Control.Monad.Eff.Console que proporciona la función log.
• El programa main está definido como una aplicación de función. En PureScript, la aplicación de función se indica con espacio en blanco separando el nombre de la función de sus argumentos.

Ejecutemos este código usando el siguiente comando:

1 $ pulp run
2 
3 * Building project in ~/my-project
4 * Build successful.
5 Hello, World!

¡Enhorabuena! Acabas de compilar y ejecutar tu primer programa PureScript.

Compilando para el navegador

Pulp puede usarse para convertir nuestro código PureScript en JavaScript susceptible de ser usado un un navegador web mediante el uso del comando pulp browserify:

1 $ pulp browserify
2 
3 * Browserifying project in ~/my-project
4 * Building project in ~/my-project
5 * Build successful.
6 * Browserifying...

A continuación de esto, debes ver un montón de código JavaScript impreso en la consola. Esto es la salida de la herramienta Browserify aplicada a una biblioteca estándar de PureScript llamada Prelude, así como el código del directorio src. Este código JavaScript puede redirigirse a un fichero e incluirse en un documento HTML. Si lo intentas, debes ver las palabras “Hello, World!” impresas en la consola de tu navegador.

Quitando código no usado

Pulp proporciona un comando alternativo, pulp build, que puede usarse con la opción -O para aplicar la fase de eliminación de código muerto responsable de quitar JavaScript innecesario de la salida. El resultado es mucho más pequeño:

1 $ pulp build -O --to output.js
2 
3 * Building project in ~/my-project
4 * Build successful.
5 * Bundling Javascript...
6 * Bundled.

De nuevo, el código generado se puede usar en un documento HTML. Si abres output.js, debes ver unos cuantos módulos compilados con esta pinta:

1 (function(exports) {
2   "use strict";
3 
4   var Control_Monad_Eff_Console = PS["Control.Monad.Eff.Console"];
5 
6   var main = Control_Monad_Eff_Console.log("Hello, World!");
7   exports["main"] = main;
8 })(PS["Main"] = PS["Main"] || {});

Esto ilustra unos cuantos puntos sobre el modo en que el compilador de PureScript genera el código JavaScript:

• Todo módulo se convierte en un objeto, creado por una función envoltorio, que contiene los miembros exportados por el módulo.
• PureScript intenta preservar los nombres de las variables cuando sea posible.
• La aplicación de funciones en PureScript se convierte en aplicación de funciones de JavaScript.
• El método principal se ejecuta después de que todos los módulos hayan sido definidos, y es generado como una simple llamada a método sin argumentos.
• El código PureScript no depende de ninguna biblioteca de tiempo de ejecución (runtime library). Todo el código que genera el compilador tiene su origen en un módulo PureScript del que tu código depende.

Estos puntos son importantes, ya que significan que PureScript genera código simple e inteligible. De hecho, el proceso de generación de código es una transformación bastante superficial. No es necesario un conocimiento avanzado del lenguaje para predecir qué código JavaScript será generado para cierto código de entrada.

Compilando módulos CommonJS

Pulp también puede usarse para generar módulos CommonJS a partir de código PureScript. Esto puede ser útil cuando usemos NodeJS o cuando estemos desarrollando un proyecto grande que usa módulos CommonJS para partir el código en componentes más pequeñas.

Para construir módulos CommonJS, usa el comando pulp build (sin la opción -O):

1 $ pulp build
2 
3 * Building project in ~/my-project
4 * Build successful.

Los módulos generados serán colocados en el directorio output por defecto. Cada módulo PureScript se compilará a su propio módulo CommonJS en su propio subdirectorio.

Seguimiento de dependencias con Bower

Para escribir la función diagonal (el objetivo de este capítulo), necesitaremos poder calcular raíces cuadradas. El paquete purescript-math contiene definiciones de tipos para las funciones definidas en el objeto JavaScript Math, así que instalémoslo:

1 $ bower install purescript-math --save

La opción --save hace que la dependencia se añada al fichero de configuración bower.json.

Los fuentes de la biblioteca purescript-math deben estar ahora disponibles en el subdirectorio bower_components y serán incluidos cuando compiles tu proyecto.

Calculando diagonales

Escribamos la función diagonal, que será un ejemplo de uso de una función de una biblioteca externa.

Primero importa el módulo Math añadiendo la siguiente línea al principio del fichero src/Main.purs:

1 import Math (sqrt)

También es necesario importar el módulo Prelude que define operaciones muy básicas como la suma y multiplicación de números:

1 import Prelude

Ahora define la función diagonal como sigue:

1 diagonal w h = sqrt (w * w + h * h)

Date cuenta de que no es necesario definir un tipo para nuestra función. El compilador es capaz de inferir que diagonal es una función que toma dos números y devuelve un número. Sin embargo, en general es una buena práctica proporcionar anotaciones de tipo como una forma de documentación.

Modifiquemos la función main para que use la nueva función diagonal:

1 main = logShow (diagonal 3.0 4.0)

Ahora compila y ejecuta el proyecto de nuevo usando pulp run:

1 $ pulp run
2 
3 * Building project in ~/my-project
4 * Build successful.
5 5.0

Probando el código usando el modo interactivo

El compilador PureScript viene con un REPL (Read Eval Print Loop) interactivo llamado PSCi. Puede ser muy util para probar tu código y experimentar con nuevas ideas. Usemos PSCi para probar la función diagonal.

Pulp puede cargar módulos fuente en PSCi automáticamente mediante el comando pulp repl.

1 $ pulp repl
2 >

Puedes escribir :? para ver una lista de comandos:

 1 > :?
 2 The following commands are available:
 3 
 4     :?                        Show this help menu
 5     :quit                     Quit PSCi
 6     :reset                    Reset
 7     :browse      <module>     Browse <module>
 8     :type        <expr>       Show the type of <expr>
 9     :kind        <type>       Show the kind of <type>
10     :show        import       Show imported modules
11     :show        loaded       Show loaded modules
12     :paste       paste        Enter multiple lines, terminated by ^D

Pulsando la tecla Tab puedes ver una lista de todas las funciones disponibles en tu propio código, así como las disponibles en las dependencias Bower y el módulo Prelude.

Empieza importando el módulo Prelude:

1 > import Prelude

Intenta evaluar unas cuantas expresiones ahora:

1 > 1 + 2
2 3
3 
4 > "Hello, " <> "World!"
5 "Hello, World!"

Probemos ahora nuestra nueva función diagonal en PSCi:

1 > import Main
2 > diagonal 5.0 12.0
3 
4 13.0

También puedes usar PSCi para definir funciones:

1 > double x = x * 2
2 
3 > double 10
4 20

No te preocupes si la sintaxis de estos ejemplos no te resulta muy clara. Tendrá más sentido según vayas leyendo el libro.

Finalmente, puedes comprobar el tipo de una expresión usando el comando :type:

1 > :type true
2 Boolean
3 
4 > :type [1, 2, 3]
5 Array Int

Prueba el modo interactivo ahora. Si te atascas en algún punto, usa el comando de Reset :reset para descargar cualquier módulo que pueda estar compilado en memoria.

Conclusión

En este capítulo hemos preparado un proyecto simple en PureScript usando la herramienta Pulp.

También hemos escrito nuestra primera función en PureScript y un programa JavaScript que puede ser ejecutado tanto en el navegador como en NodeJS.

Usaremos este entorno en los siguientes capítulos para compilar, depurar y probar nuestro código, así que debes asegurarte de que estás cómodo con las herramientas y técnicas involucradas.

Funciones y registros (records)

Objetivos del capítulo

Este capítulo presenta dos elementos esenciales de los programas PureScript: funciones y registros. Además veremos cómo estructurar programas PureScript y cómo usar los tipos como una ayuda en el desarrollo de programas.

Construiremos una aplicación de agenda simple para manejar una lista de contactos. Este código presentará algunas nuevas ideas de la sintaxis de PureScript.

La interfaz de nuestra aplicación será el modo interactivo PSCi, pero sería posible tomar como base este código para construir una interfaz en JavaScript. De hecho, haremos exactamente eso en capítulos posteriores, añadiendo validación de formulario y funcionalidad de salvado/carga.

Preparación del proyecto

El código fuente de este capítulo estará contenido en el fichero src/Data/AddressBook.purs. Este fichero comienza con una declaración de módulo y su lista de importación:

1 module Data.AddressBook where
2 
3 import Prelude
4 
5 import Control.Plus (empty)
6 import Data.List (List(..), filter, head)
7 import Data.Maybe (Maybe)

Aquí importamos varios módulos:

• El módulo Control.Plus que define el valor empty.
• El módulo Data.List proporcionado por el paquete purescript-lists que puede instalarse usando Bower. Contiene unas cuantas funciones que necesitaremos para trabajar con listas enlazadas.
• El módulo Data.Maybe que define tipos de datos y funciones para trabajar con valores opcionales.

Date cuenta de que lo que importamos de estos módulos está listado explícitamente entre paréntesis. Esto es generalmente una buena práctica, ya que ayuda a evitar conflictos entre los símbolos importados.

Asumiendo que has clonado el repositorio con el código fuente del libro, el proyecto para este capítulo puede construirse usando Pulp mediante los siguientes comandos:

1 $ cd chapter3
2 $ bower update
3 $ pulp build

Tipos simples

PureScript define tres tipos integrados que se corresponden con los tipos primitivos de JavaScript: números, cadenas y booleanos. Están definidos en el módulo Prim que se importa de manera implícita por todos los módulos. Se llaman Number, String y Boolean respectivamente y puedes verlos en PSCi usando el comando :type para imprimir los tipos de algunos valores simples:

 1 $ pulp repl
 2 
 3 > :type 1.0
 4 Number
 5 
 6 > :type "test"
 7 String
 8 
 9 > :type true
10 Boolean

PureScript define otros tipos integrados: enteros, caracteres, formaciones (arrays en adelante), registros (records) y funciones.

Los enteros se diferencian de los tipos de coma flotante de tipo Number en que carecen de coma decimal.

1 > :type 1
2 Int

Los caracteres literales van rodeados por comillas simples, a diferencia de las cadenas literales que usan dobles comillas:

1 > :type 'a'
2 Char

Los arrays se corresponden a arrays de JavaScript, pero al contrario que en JavaScript, todos los elementos de un array PureScript deben tener el mismo tipo:

1 > :type [1, 2, 3]
2 Array Int
3 
4 > :type [true, false]
5 Array Boolean
6 
7 > :type [1, false]
8 Could not match type Int with Boolean.

El error del último ejemplo es un error del comprobador de tipos, que intenta unificar sin éxito (es decir, igualar) los tipos de los dos elementos.

Los registros se corresponden con los objetos de JavaScript y los registros literales tienen la misma sintaxis que los objetos literales de JavaScript:

1 > author = { name: "Phil", interests: ["Functional Programming", "JavaScript"] }
2 
3 > :type author
4 { name :: String
5 , interests :: Array String
6 }

Este tipo indica que el objeto especificado tiene dos campos, un campo name de tipo String y un campo interests que tiene tipo Array String, es decir, un array de cadenas.

Los campos de los registros se pueden acceder usando un punto, seguido por la etiqueta del campo a acceder:

1 > author.name
2 "Phil"
3 
4 > author.interests
5 ["Functional Programming","JavaScript"]

Las funciones de PureScript se corresponden con las funciones de JavaScript. Las bibliotecas estándar de PureScript proporcionan un montón de ejemplos de funciones, y veremos más en este capítulo:

1 > import Prelude
2 > :type flip
3 forall a b c. (a -> b -> c) -> b -> a -> c
4 
5 > :type const
6 forall a b. a -> b -> a

Las funciones pueden ser definidas en el nivel superior de un fichero especificando los argumentos antes del signo igual:

1 add :: Int -> Int -> Int
2 add x y = x + y

De manera alternativa, las funciones se pueden definir en línea usando una barra diagonal inversa seguida de una lista de nombres de argumento delimitada por espacios. Para introducir una declaración de varias líneas en PSCi, podemos entrar en “modo paste” usando el comando :paste. En este modo, las declaraciones se finalizan usando la secuencia de teclas Control-D:

1 > :paste
2 … add :: Int -> Int -> Int
3 … add = \x y -> x + y
4 … ^D

Habiendo definido esta función en PSCi, podemos aplicarla a sus argumentos separando los dos argumentos del nombre de la función mediante espacio en blanco:

1 > add 10 20
2 30

Tipos cuantificados

En la sección anterior, vimos los tipos de algunas funciones definidas en el Prelude. Por ejemplo, la función flip tenía el siguiente tipo:

1 > :type flip
2 forall a b c. (a -> b -> c) -> b -> a -> c

La palabra clave forall indica aquí que flip tiene un tipo universalmente cuantificado. Significa que podemos sustituir cualquier tipo por a, b y c, y flip funcionará con esos tipos.

Por ejemplo, podemos elegir que el tipo de a sea Int, b sea String y c sea String. En ese caso, podríamos especializar el tipo de flip a:

1 (Int -> String -> String) -> String -> Int -> String

No tenemos que indicar en el código que queremos especializar un tipo cuantificado, sucede automáticamente. Por ejemplo, podemos simplemente usar flip como si ya tuviese este tipo:

1 > flip (\n s -> show n <> s) "Ten" 10
2 
3 "10Ten"

Aunque podemos elegir cualquier tipo para a, b y c, tenemos que ser consistentes. El tipo de la función que hemos pasado a flip tenía que ser consistente con los tipos de los otros argumentos. Es por eso que pasamos la cadena “Ten” como segundo argumento, y el número 10 como el tercero. No funcionaría si invirtiésemos los argumentos:

1 > flip (\n s -> show n <> s) 10 "Ten"
2 
3 Could not match type Int with type String

Notas sobre la sangría (indentation)

El código PureScript es sensible a la sangría, al igual que Haskell y al contrario que JavaScript. Esto significa que el espacio en blanco de tu código no carece de significado. Se usa para agrupar regiones de código, de la misma manera que se usan las llaves en los lenguajes tipo C.

Si una declaración abarca múltiples líneas, entonces cualquier línea excepto la primera debe tener sangría más allá del nivel de la primera línea.

Así, lo siguiente es código PureScript válido:

1 add x y z = x +
2   y + z

Pero esto no es código válido:

1 add x y z = x +
2 y + z

En el segundo caso, el compilador de PureScript intentará analizar dos declaraciones, una por cada línea.

Generalmente, las declaraciones definidas en el mismo bloque deben tener sangría al mismo nivel. Por ejemplo, en PSCi, las declaraciones en una sentencia let deben deben tener la misma sangría. Esto es válido:

1 > :paste
2 … x = 1
3 … y = 2
4 … ^D

Pero esto no lo es:

1 > :paste
2 … x = 1
3 …  y = 2
4 … ^D

Algunas palabras clave de PureScript (como where, of y let) introducen un nuevo bloque de código, en el cual las declaraciones deben tener mayor nivel de sangría:

1 example x y z = foo + bar
2   where
3     foo = x * y
4     bar = y * z

Date cuenta de que las declaraciones de foo y bar tienen mayor nivel de sangría que la declaración de example.

La única excepción a esta regla es la palabra clave where en la declaración de module inicial al comienzo del fichero fuente.

Definiendo nuestros tipos

Un buen primer paso cuando se aborda un nuevo problema en PureScript es escribir las definiciones de tipos para cualquier valor con el que vayas a trabajar. Primero, definamos un tipo para los registros de nuestra agenda:

1 type Entry =
2   { firstName :: String
3   , lastName  :: String
4   , address   :: Address
5   }

Esto define un sinónimo de tipo llamado Entry. El tipo Entry es equivalente al tipo a la derecha del símbolo igual: un registro con tres campos: firstName, lastName y address. Los dos campos de nombre tendrán tipo String, y el campo address tendrá tipo Address definido como sigue:

1 type Address =
2   { street :: String
3   , city   :: String
4   , state  :: String
5   }

Date cuenta de que los registros pueden contener otros registros.

Ahora definamos un tercer sinónimo de tipo para nuestra estructura de datos de agenda, que será representada simplemente como una lista enlazada de entradas:

1 type AddressBook = List Entry

Date cuenta de que List Entry no es lo mismo que Array Entry, que representa un array de entradas.

Constructores de tipo (type constructors) y familias (kinds)

List es un ejemplo de un constructor de tipo. Los valores no tienen el tipo List directamente, sino List a para algún tipo a. Esto es, List toma un argumento de tipo a y construye un nuevo tipo List a.

Date cuenta de que al igual que la aplicación de función, los constructores de tipo se aplican a otros tipos simplemente por yuxtaposición: el tipo List Entry es de hecho el constructor de tipo List aplicado al tipo Entry, representa una lista de entradas.

Si tratamos de definir incorrectamente un valor de tipo List (usando el operador de anotación de tipo ::), veremos un nuevo tipo de error:

1 > import Data.List
2 > Nil :: List
3 In a type-annotated expression x :: t, the type t must have kind Type

Esto es un error de familia. Al igual que los valores se distinguen por su tipo, los tipos se distinguen por su familia, y al igual que los valores erróneamente tipados acaban en errores de tipo, los tipos mal expresados resultan en errores de familia.

Hay una familia especial llamada Type que representa la familia de todos los tipos que tienen valores, como Number y String.

Hay también familias para constructores de tipo. Por ejemplo, la familia Type -> Type representa una función de tipos a tipos, como List. Así, el error ha ocurrido aquí porque se espera que los valores tengan tipos de familia Type, pero List tiene familia Type -> Type.

Para averiguar la familia de un tipo, usa el comando :kind en PSCi. Por ejemplo:

1 > :kind Number
2 Type
3 
4 > import Data.List
5 > :kind List
6 Type -> Type
7 
8 > :kind List String
9 Type

El sistema de familias de PureScript soporta otras familias interesantes que veremos más adelante en el libro.

Mostrando entradas de la agenda

Escribamos nuestra primera función, que representará una entrada de la agenda como una cadena. Empezamos dando a la función un tipo. Esto es opcional, pero es una buena práctica, ya que actúa como una forma de documentación. De hecho, el compilador de PureScript emitirá un aviso si una declaración del nivel superior no contiene una anotación de tipo. Una declaración de tipo separa con el símbolo :: el nombre de la función de su tipo:

1 showEntry :: Entry -> String

La firma de tipo dice que showEntry es una función que toma Entry como argumento y devuelve una cadena. Aquí está el código para showEntry:

1 showEntry entry = entry.lastName <> ", " <>
2                   entry.firstName <> ": " <>
3                   showAddress entry.address

Esta función concatena los tres campos del registro Entry en una única cadena, usando la función showAddress para convertir el registro contenido en el campo address a una cadena. showAddress se define de forma similar:

1 showAddress :: Address -> String
2 showAddress addr = addr.street <> ", " <>
3                    addr.city <> ", " <>
4                    addr.state

Una definición de función comienza con el nombre de la función, seguida por una lista de nombres de argumento. El resultado de la función se especifica tras el signo igual. Los campos se acceden con un punto seguido del nombre de campo. En PureScript, la concatenación usa el operador diamante (<>), en lugar del operador de suma que usa JavaScript.

Prueba temprano, prueba a menudo

El modo interactivo PSCi permite prototipado rápido con retroalimentación inmediata, así que usémoslo para verificar que nuestras primeras funciones se comportan como esperamos:

Primero, construye el código que has escrito:

1 $ pulp build

A continuación, carga PSCi y usa el comando import para importar tu nuevo módulo:

1 $ pulp repl
2 
3 > import Data.AddressBook

Podemos crear una entrada usando un registro literal, que tiene el mismo aspecto que un objeto anónimo en JavaScript. Vamos a ligarlo a un nombre con una expresión let:

1 > address = { street: "123 Fake St.", city: "Faketown", state: "CA" }

Ahora intenta aplicar nuestra función al ejemplo:

1 > showAddress address
2 
3 "123 Fake St., Faketown, CA"

Probemos también showEntry creando una entrada de la agenda conteniendo nuestra dirección de ejemplo:

1 > entry = { firstName: "John", lastName: "Smith", address: address }
2 > showEntry entry
3 
4 "Smith, John: 123 Fake St., Faketown, CA"

Creando agendas

Ahora escribamos algunas funciones útiles para trabajar con agendas. Necesitaremos un valor que representa una agenda vacía: una lista vacía.

1 emptyBook :: AddressBook
2 emptyBook = empty

Necesitaremos también una función para insertar un valor en una agenda existente. Llamaremos a esta función insertEntry. Comienza dándole su tipo:

1 insertEntry :: Entry -> AddressBook -> AddressBook

La firma de tipo dice que insertEntry toma Entry como primer argumento y AddressBook como segundo argumento, y devuelve un nuevo AddressBook.

No modificamos el AddressBook directamente. En su lugar, devolvemos un nuevo AddressBook que contiene la nueva entrada. Así, AddressBook es un ejemplo de una estructura de datos inmutable. Esta es una idea importante en PureScript: la mutación es un efecto secundario del código e inhibe nuestra habilidad para razonar de manera efectiva sobre su comportamiento, de manera que preferimos funciones puras y datos inmutables donde sea posible.

Para implementar insertEntry, usamos la función Cons de Data.List. Para ver su tipo, abre PSCi y usa el comando :type:

1 $ pulp repl
2 
3 > import Data.List
4 > :type Cons
5 
6 forall a. a -> List a -> List a

La firma de tipo dice que Cons toma un valor de cierto tipo a y una lista de elementos de tipo a, y devuelve una nueva lista con entradas del mismo tipo. Especialicemos esto con nuestro tipo Entry en el papel de a:

1 Entry -> List Entry -> List Entry

Pero List Entry es lo mismo que AddressBook, de manera que esto es equivalente a:

1 Entry -> AddressBook -> AddressBook

En nuestro caso, ya tenemos las entradas apropiadas: un Entry y un AddressBook, de manera que podemos aplicar Cons y obtener un nuevo AddressBook, ¡que es exactamente lo que queremos!

Aquí está nuestra implementación de insertEntry:

1 insertEntry entry book = Cons entry book

Esto usa los dos argumentos entry y book declarados a la izquierda del símbolo igual y les aplica la función Cons para crear el resultado.

Funciones currificadas (curried functions)

Las funciones en PureScript toman exactamente un argumento. Aunque parece que la función insertEntry toma dos argumentos, es de hecho un ejemplo de una función currificada.

El operador -> en el tipo de insertEntry se asocia a la derecha, lo que significa que el compilador analiza el tipo como:

1 Entry -> (AddressBook -> AddressBook)

Esto es, insertEntry es una función que devuelve una función. Toma un único argumento, un Entry, y devuelve una nueva función que a su vez toma un único argumento AddressBook y devuelve un nuevo AddressBook.

Esto significa que podemos aplicar parcialmente insertEntry especificando únicamente su primer argumento, por ejemplo. En PSCi podemos ver el tipo resultante:

1 > :type insertEntry entry
2 
3 AddressBook -> AddressBook

Como esperábamos, el tipo de retorno es una función. Podemos aplicar la función resultante a un segundo argumento:

1 > :type (insertEntry entry) emptyBook
2 AddressBook

Date cuenta de que los paréntesis son innecesarios. Lo que sigue es equivalente:

1 > :type insertEntry example emptyBook
2 AddressBook

Esto es porque la aplicación de función asocia a la izquierda, y esto explica por qué podemos simplemente especificar argumentos de función uno tras otro, separados por espacio en blanco.

En el resto del libro hablaremos de cosas como “funciones de dos argumentos”. Sin embargo, hay que entender que esto significa una función currificada que toma un primer argumento y devuelve otra función.

Ahora considera la definición de insertEntry:

1 insertEntry :: Entry -> AddressBook -> AddressBook
2 insertEntry entry book = Cons entry book

Si ponemos entre paréntesis de manera explícita la parte derecha, tenemos (Cons entry) book. Esto es, insertEntry entry es una función cuyo argumento se pasa sin más a la función (Cons entry). Pero si dos funciones tienen el mismo resultado para cualquier entrada entonces son la misma función. Así que podemos quitar el argumento book de ambos lados:

1 insertEntry :: Entry -> AddressBook -> AddressBook
2 insertEntry entry = Cons entry

Pero ahora, con el mismo razonamiento, podemos quitar entry de ambos lados:

1 insertEntry :: Entry -> AddressBook -> AddressBook
2 insertEntry = Cons

Este proceso se llama conversión eta, y se puede usar (junto a otras técnicas) para reescribir funciones en forma libre de puntos (point-free form), que significa que las funciones están definidas sin referencia a sus argumentos.

En el caso de insertEntry, la conversión eta ha resultado en una definición muy clara de nuestra función: “insertEntry es simplemente cons sobre listas”. Sin embargo, es discutible si la forma libre de puntos es mejor en general.

Consultando la agenda

La última función que necesitamos implementar para nuestra aplicación de agenda mínima buscará una persona por nombre y devolverá la Entry correcta. Esto será una buena aplicación de la idea de construir programas componiendo pequeñas funciones, una idea clave en la programación funcional.

Podemos primero filtrar la agenda, manteniendo sólo las entradas con los nombres y apellidos correctos. Entonces podemos simplemente devolver la cabeza (es decir, el primer elemento) de la lista resultante.

Con esta especificación de alto nivel de nuestra estrategia, podemos calcular el tipo de nuestra función. Primero abre PSCi y busca los tipos de las funciones filter y head:

 1 $ pulp repl
 2 
 3 > import Data.List
 4 > :type filter
 5 
 6 forall a. (a -> Boolean) -> List a -> List a
 7 
 8 > :type head
 9 
10 forall a. List a -> Maybe a

Vamos a desmontar estos dos tipos para entender su significado.

filter es una función currificada de dos argumentos. Su primer argumento es una función que toma un elemento de una lista y devuelve un valor Boolean como resultado. Su segundo argumento es una lista de elementos, y el valor de retorno es otra lista.

head toma una lista como argumento y devuelve un tipo que no hemos visto antes: Maybe a. Maybe a representa un valor opcional de tipo a, y proporciona una alternativa de tipo seguro al uso de null para indicar un valor inexistente en lenguajes como JavaScript. La veremos de nuevo en más detalle en capítulos posteriores.

Los tipos universalmente cuantificados de filter y head pueden ser especializados por el compilador de PureScript a los siguientes tipos:

1 filter :: (Entry -> Boolean) -> AddressBook -> AddressBook
2 
3 head :: AddressBook -> Maybe Entry

Sabemos que necesitaremos pasar el nombre y apellidos que queremos buscar como argumentos a nuestra función.

También sabemos que necesitaremos una función para pasar a filter. Llamemos a esta función filterEntry. filterEntry tendrá tipo Entry -> Boolean. La aplicación filter filterEntry tendrá entonces tipo AddressBook -> AddressBook. Si pasamos el resultado de esta función a la función head, obtenemos nuestro resultado de tipo Maybe Entry.

Juntando esto, una firma de tipo razonable para nuestra función, que llamaremos findEntry, es:

1 findEntry :: String -> String -> AddressBook -> Maybe Entry

Esta firma de tipo dice que findEntry toma dos cadenas, nombre y apellido, un AddressBook, y retorna un Entry opcional. El resultado opcional contendrá un valor sólo si el nombre se encuentra en la agenda.

Y aquí está la definición de findEntry:

1 findEntry firstName lastName book = head $ filter filterEntry book
2   where
3     filterEntry :: Entry -> Boolean
4     filterEntry entry = entry.firstName == firstName && entry.lastName == lastNa\
5 me

Vamos a repasar el código paso a paso.

findEntry pone en contexto tres nombres: firstName y lastName, ambos representando cadenas, y book, un AddressBook.

La parte derecha de la definición combina las funciones filter y head: primero, la lista de entradas es filtrada y luego, la función head se aplica al resultado.

La función predicado filterEntry se define como una declaración auxiliar dentro de una cláusula where. De esta manera, la función filterEntry está disponible dentro de la definición de nuestra función pero no fuera de ella. También, puede depender de los argumentos de la función contenedora, lo que es esencial aquí porque filterEntry usa los argumentos firstName y lastName para filtrar la Entry especificada.

Date cuenta de que al igual que en el caso de las declaraciones de nivel superior, no es necesario especificar una firma de tipo para filterEntry. Sin embargo, se recomienda hacerlo como una forma de documentación.

Aplicación de funciones infija

En el código de findEntry de arriba, usamos una forma diferente de aplicación de función: la función head ha sido aplicada a la expresión filter filterEntry book usando el símbolo infijo $.

Esto es equivalente a la aplicación usual head (filter filterEntry book).

($) es simplemente una función normal llamada apply, definida en el Prelude como sigue:

1 apply :: forall a b. (a -> b) -> a -> b
2 apply f x = f x
3 
4 infixr 0 apply as $

Así, apply toma una función y un valor, y aplica la función al valor. La palabra reservada infixr se usa para definir ($) como un alias de apply.

Pero ¿por qué podríamos querer usar $ en lugar de aplicación de función normal? La razón es que $ es un operador de baja precedencia asociativo por la derecha. Esto significa que $ nos permite quitar pares de paréntesis para aplicaciones anidadas profundamente.

Por ejemplo, la siguiente aplicación de función anidada que encuentra la calle en la dirección del jefe de un empleado:

1 street (address (boss employee))

Es probablemente más legible cuando se expresa usando $:

1 street $ address $ boss employee

Composición de funciones

Al igual que hemos sido capaces de simplificar la función insertEntry usando conversión eta, podemos simplificar la definición de findEntry razonando sobre sus argumentos.

Date cuenta de que el argumento book se pasa a la función filter filterEntry, y el resultado de esta aplicación se pasa a head. En otras palabras, book se pasa a la composición de las funciones filter filterEntry y head.

En PureScript, los operadores de composición de función son <<< y >>>. El primero es “composición hacia atrás” (backwards composition) y el segundo es “composición hacia delante” (forwards composition).

Podemos reescribir la parte derecha de findEntry usando cualquier operador. Usando composición hacia atrás, la parte derecha sería:

1 (head <<< filter filterEntry) book

En esta forma, podemos aplicar el truco anterior de conversión eta para llegar a la forma final de findEntry:

1 findEntry firstName lastName = head <<< filter filterEntry
2   where
3     ...

Una parte derecha igualmente válida sería:

1 filter filterEntry >>> head

De cualquier modo, esto nos da una definición clara de la función findEntry: “findEntry es la composición de una función de filtrado y la función head”.

Voy a dejar que tomes tu propia decisión sobre qué definición es más fácil de entender, pero a menudo es útil pensar en las funciones como bloques de construcción de esta manera. Cada función ejecutando una única tarea y soluciones ensambladas usando composición de funciones.

Prueba, prueba, prueba…

Ahora que tenemos el núcleo de una aplicación, probémosla usando PSCi:

1 $ pulp repl
2 
3 > import Data.AddressBook

Vamos primero a intentar buscar una entrada en una agenda vacía (obviamente esperamos que esto devuelva un resultado vacío):

 1 > findEntry "John" "Smith" emptyBook
 2 
 3 No type class instance was found for
 4 
 5     Data.Show.Show { firstName :: String
 6                    , lastName :: String
 7                    , address :: { street :: String
 8                                 , city :: String
 9                                 , state :: String
10                                 }
11                    }

¡Un error! No hay que preocuparse, este error simplemente significa que PSCi no sabe cómo imprimir un valor de tipo Entry como String.

El tipo de retorno de findEntry es Maybe Entry, que podemos convertir a String a mano.

Nuestra función showEntry espera un argumento de tipo Entry, pero tenemos un valor de tipo Maybe Entry. Recuerda que esto significa que la función devuelve un valor opcional de tipo Entry. Lo que necesitamos es aplicar la función showEntry si el valor opcional está presente y propagar el valor ausente si no lo está.

Afortunadamente, el módulo Prelude proporciona una manera de hacer esto. El operador map se puede usar para elevar (lift) una función sobre un constructor de tipo apropiado como Maybe (veremos más sobre esta función y otras como ella más tarde cuando hablemos de funtores):

1 > import Prelude
2 > map showEntry (findEntry "John" "Smith" emptyBook)
3 
4 Nothing

Eso está mejor. El valor de retorno Nothing indica que el valor de retorno opcional no contiene un valor, como esperábamos.

Para facilitar el uso, podemos crear una función que imprime Entry como una String, de manera que no tengamos que usar showEntry cada vez:

1 > printEntry firstName lastName book = map showEntry (findEntry firstName lastNa\
2 me book)

Ahora creemos una agenda no vacía e intentemos de nuevo. Reutilizaremos nuestra entrada de ejemplo anterior:

1 > book1 = insertEntry entry emptyBook
2 
3 > printEntry "John" "Smith" book1
4 
5 Just ("Smith, John: 123 Fake St., Faketown, CA")

Esta vez, el resultado contenía el valor correcto. Intenta definir una agenda book2 con dos nombres insertando otro nombre en book1 y busca cada entrada por nombre.

Conclusión

En este capítulo hemos cubierto varios conceptos de programación funcional:

• Cómo usar el modo interactivo PSCi para experimentar con funciones y probar ideas.
• El papel de los tipos como herramienta de corrección e implementación.
• El uso de funciones currificadas para representar funciones de múltiples argumentos.
• Crear programas a partir de componentes más pequeñas mediante composición.
• Estructurar el código de manera limpia usando expresiones where.
• Como evitar valores nulos usando el tipo Maybe.
• El uso de técnicas como la conversión eta y la composición de funciones para refactorizar código.

En los siguientes capítulos nos basaremos en estas ideas.

Recursividad, asociaciones (maps) y pliegues (folds)

Objetivos del capítulo

En este capítulo, vamos a ver cómo las funciones recursivas pueden ser usadas para estructurar algoritmos. La recursividad es una técnica básica usada en la programación funcional que vamos a usar por todo el libro.

También cubriremos algunas funciones estándar de las bibliotecas estándar de PureScript. Veremos las funciones map y fold, así como algunos casos especiales útiles, como filter y concatMap.

El ejemplo motivador para este capítulo es una biblioteca de funciones para trabajar con un sistema de ficheros virtual. Aplicaremos técnicas aprendidas en este capítulo para escribir funciones que calculan propiedades de los ficheros representados por un modelo de un sistema de ficheros.

Preparación del proyecto

El código fuente para este capítulo está contenido en los dos ficheros src/Data/Path.purs y src/FileOperations.purs.

El módulo Data.Path contiene un modelo de un sistema de ficheros virtual. No necesitas modificar el contenido de este módulo.

El módulo FileOperations contiene funciones que usan la API Data.Path. Las soluciones a los ejercicios se deben implementar en este fichero.

El proyecto tiene las siguientes dependencias de Bower:

• purescript-maybe, que define el constructor de tipo Maybe.
• purescript-arrays, que define funciones para trabajar con arrays.
• purescript-strings, que define funciones para trabajar con cadenas JavaScript.
• purescript-foldable-traversable, que define funciones para plegar arrays y otras estructuras de datos.
• purescript-console, que define funciones para imprimir en la consola.

Introducción

La recursividad es una técnica importante en la programación en general, pero es particularmente común en la programación funcional porque, como veremos en este capítulo, la recursividad ayuda a reducir el estado mutable en nuestros programas.

La recursividad está estrechamente vinculada a la estrategia divide y vencerás: para resolver un problema para ciertas entradas, podemos descomponer las entradas en partes más pequeñas, resolver el problema sobre esas partes, y ensamblar una solución a partir de las soluciones parciales.

Veamos algunos ejemplos simples de recursividad en PureScript.

Aquí tenemos el habitual ejemplo de función factorial:

1 fact :: Int -> Int
2 fact 0 = 1
3 fact n = n * fact (n - 1)

Aquí, podemos ver cómo la función factorial se calcula reduciendo el problema a un subproblema: el de calcular el factorial de un entero más pequeño. Cuando llegamos a cero, la respuesta es inmediata.

Aquí tenemos otro ejemplo común que calcula la función de Fibonnacci:

1 fib :: Int -> Int
2 fib 0 = 1
3 fib 1 = 1
4 fib n = fib (n - 1) + fib (n - 2)

De nuevo, este problema se resuelve considerando las soluciones a subproblemas. En este caso, hay dos subproblemas, que corresponden a las expresiones fib (n - 1) y fib (n - 2). Cuando estos dos subproblemas están resueltos, ensamblamos el resultado sumando los resultados parciales.

Recursividad sobre arrays

¡No estamos limitados a definir funciones recursivas sobre el tipo Int! Veremos funciones recursivas definidas sobre una amplia variedad de tipos de datos cuando abarquemos el ajuste de patrones (pattern matching) más tarde en el libro, pero por ahora, nos ceñiremos a arrays y números.

Igual que podemos ramificar dependiendo de si la entrada es distinta de cero, en el caso de arrays ramificaremos dependiendo de si la entrada es no-vacía. Considera esta función que calcula la longitud de un array usando recursividad:

 1 import Prelude
 2 
 3 import Data.Array (null)
 4 import Data.Array.Partial (tail)
 5 import Partial.Unsafe (unsafePartial)
 6 
 7 length :: forall a. Array a -> Int
 8 length arr =
 9   if null arr
10     then 0
11     else 1 + length (unsafePartial tail arr)

En esta función, usamos una expresión if .. then .. else para ramificar basándonos en si el array está vacío. La función null devuelve true para un array vacío. Los arrays vacíos tienen una longitud de cero, y cualquier array no vacío tiene una longitud que es uno más que la longitud de su cola.

Este ejemplo es obviamente una manera muy poco práctica de encontrar la longitud de un array en JavaScript, pero debe proporcionar suficiente ayuda para permitirte completar los siguientes ejercicios:

Asociaciones (maps)

La función map es un ejemplo de una función recursiva sobre arrays. Se usa para transformar los elementos de un array aplicando una función a cada uno de sus elementos. Así, cambian el contenido del array, pero preserva su forma (es decir, su longitud).

Cuando veamos las clases de tipo más adelante en el libro, veremos que la función map es un ejemplo de un patron más general de funciones que preservan la forma y que transforman una clase de constructores de tipo llamados funtores (functors).

Probemos la función map en PSCi:

1 $ pulp repl
2 
3 > import Prelude
4 > map (\n -> n + 1) [1, 2, 3, 4, 5]
5 [2, 3, 4, 5, 6]

Date cuenta de cómo se usa map: proporcionamos como primer argumento una función que debe ser “mapeada sobre” el array, y proporcionamos el array como segundo argumento.

Operadores infijos

La función map también se puede escribir entre la función de mapeo y el array rodeándola de comillas inversas:

1 > (\n -> n + 1) `map` [1, 2, 3, 4, 5]
2 [2, 3, 4, 5, 6]

Esta sintaxis se llama aplicación de función infija, y cualquier función se puede hacer infija de esta manera. Normalmente es más apropiada para funciones de dos argumentos.

Hay un operador que es equivalente a la función map cuando se usa con arrays, llamado <$>. Este operador se puede usar de manera infija como cualquier otro operador binario:

1 > (\n -> n + 1) <$> [1, 2, 3, 4, 5]
2 [2, 3, 4, 5, 6]

Veamos el tipo de map:

1 > :type map
2 forall a b f. Functor f => (a -> b) -> f a -> f b

El tipo de map es de hecho más general de lo que necesitamos en este capítulo. Para nuestros propósitos, podemos tratar map como si tuviese el siguiente tipo menos general:

1 forall a b. (a -> b) -> Array a -> Array b

Este tipo dice que podemos elegir dos tipos cualesquiera, a y b, con los que aplicar la función map. a es el tipo de elementos del array original y b es el tipo de elementos del array resultante. En particular, no hay ninguna razón por la que map tenga que preservar el tipo de los elementos del array. Podemos usar map o <$> para transformar enteros a cadenas, por ejemplo:

1 > show <$> [1, 2, 3, 4, 5]
2 
3 ["1","2","3","4","5"]

Aunque el operador infijo <$> parece una sintaxis especial, es de hecho un simple apodo (alias) para una función PureScript normal. La función es simplemente aplicada usando notación infija. De hecho, la función se puede usar como una función normal poniendo el nombre entre paréntesis. Esto significa que podemos usar el nombre entre paréntesis (<$>) en lugar de map sobre arrays:

1 > (<$>) show [1, 2, 3, 4, 5]
2 ["1","2","3","4","5"]

Los nombres de función infijos se definen como apodos para nombres de función existentes. Por ejemplo, el módulo Data.Array define un operador infijo (..) como sinónimo de la funcion range como sigue:

1 infix 8 range as ..

Podemos usar este operador como sigue:

1 > import Data.Array
2 
3 > 1 .. 5
4 [1, 2, 3, 4, 5]
5 
6 > show <$> (1 .. 5)
7 ["1","2","3","4","5"]

Nota: Los operadores infijos pueden ser una gran herramienta para definir lenguajes específicos del dominio con una sintaxis natural. Sin embargo, si se usan excesivamente, pueden volver el código ilegible para principiantes, de manera que es una buena cosa tener precaución al definir cualquier operador nuevo.

En el ejemplo anterior, hemos puesto la expresión 1 .. 5 entre paréntesis, pero de hecho no era necesario, porque el módulo Data.Array asigna un nivel de precedencia mayor al operador .. que el asignado al operador <$>. En el ejemplo anterior, la precedencia del operador .. se definía como 8, el número tras la palabra clave infix. Este valor es más alto que el nivel de precedencia de <$>, lo que significa que no necesitamos añadir paréntesis:

1 > show <$> 1 .. 5
2 ["1","2","3","4","5"]

Si quisiésemos asignar una asociatividad (a izquierda o derecha) a un operador infijo, podríamos hacerlo con las palabras clave infixl o infixr.

Filtrando arrays

El módulo Data.Array proporciona otra función filter que se usa a menudo junto a map. Proporciona la capacidad de crear un nuevo array, a partir de uno existente, manteniendo únicamente los elementos que coinciden con una función predicado.

Por ejemplo, supongamos que queremos calcular un array de todos los números pares entre 1 y 10. Lo podríamos hacer como sigue:

1 > import Data.Array
2 
3 > filter (\n -> n `mod` 2 == 0) (1 .. 10)
4 [2,4,6,8,10]

Aplanando arrays

Otra función estándar sobre arrays es la función concat, definida en Data.Array. concat aplana un array de arrays en un único array:

1 > import Data.Array
2 
3 > :type concat
4 forall a. Array (Array a) -> Array a
5 
6 > concat [[1, 2, 3], [4, 5], [6]]
7 [1, 2, 3, 4, 5, 6]

Hay una función relacionada llamada concatMap que es como una combinación de las funciones concat y map. Si map toma una función de valores a valores (posiblemente de un tipo diferente), concatMap toma una función de valores a arrays de valores.

Veámosla en acción:

1 > import Data.Array
2 
3 > :type concatMap
4 forall a b. (a -> Array b) -> Array a -> Array b
5 
6 > concatMap (\n -> [n, n * n]) (1 .. 5)
7 [1,1,2,4,3,9,4,16,5,25]

Aquí llamamos concatMap con la función \n -> [n, n * n] que envía un entero al array de dos elementos consistente en el propio entero y su cuadrado. El resultado es un array de diez enteros: los enteros de 1 a 5 junto a sus cuadrados.

Date cuenta que concatMap concatena sus resultados. Llama a la función proporcionada una vez para cada elemento del array original, generando un array para cada uno. Finalmente, colapsa todos estos arrays en un único array que será su resultado.

map, filter y concatMap forman la base de todo un rango de funciones sobre arrays llamadas arrays por comprensión.

Arrays por comprensión (array comprehensions)

Supongamos que queremos encontrar los factores de un número n. Una forma simple de hacerlo sería por fuerza bruta: podemos generar todos los pares de números entre 1 y n, y tratar de multiplicarlos. Si el producto fuese n, habríamos encontrado un par de factores de n.

Podemos realizar este cálculo usando un array por comprensión. Lo haremos por pasos, usando PSCi como nuestro entorno de desarrollo interactivo.

El primer paso es generar un array de pares de números inferiores a n, cosa que podemos hacer usando concatMap.

Empecemos mapeando cada número al array 1 .. n:

1 > pairs n = concatMap (\i -> 1 .. n) (1 .. n)

Podemos probar nuestra función:

1 > pairs 3
2 [1,2,3,1,2,3,1,2,3]

Esto no es exactamente lo que queremos. En lugar de simplemente devolver el segundo elemento de cada par, necesitamos mapear una función sobre la copia interna de 1 .. n que nos permitirá mantener el par completo:

1 > :paste
2 … pairs' n =
3 …   concatMap (\i ->
4 …     map (\j -> [i, j]) (1 .. n)
5 …   ) (1 .. n)
6 … ^D
7 
8 > pairs' 3
9 [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

Esto tiene mejor pinta. Sin embargo, estamos generando demasiados pares: tenemos [1, 2] y [2, 1] por ejemplo. Podemos excluir el segundo caso asegurándonos de que j sólo va de i a n:

1 > :paste
2 … pairs'' n =
3 …   concatMap (\i ->
4 …     map (\j -> [i, j]) (i .. n)
5 …   ) (1 .. n)
6 … ^D
7 > pairs'' 3
8 [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]

¡Estupendo! Ahora que tenemos todos los pares de factores potenciales, podemos usar filter para elegir los pares cuya multiplicación da n:

1 > import Data.Foldable
2 
3 > factors n = filter (\pair -> product pair == n) (pairs'' n)
4 
5 > factors 10
6 [[1,10],[2,5]]

Este código usa la función product del módulo Data.Foldable en la biblioteca purescript-foldable-traversable.

¡Excelente! Hemos conseguido encontrar el conjunto correcto de pares de factores sin duplicados.

Notación ‘do’ (do notation)

Sin embargo, podemos mejorar la legibilidad de nuestro código considerablemente. map y concatMap son tan fundamentales que forman la base (o más bien, sus generalizaciones map y bind forman la base) de una sintaxis especial llamada notación do.

Nota: Igual que map y concatMap nos permitían escribir arrays por comprensión, los operadores más generales map y bind nos permiten escribir las llamadas mónadas por comprensión (monad comprehensions). Veremos muchos mas ejemplos de mónadas mas adelante, pero en este capítulo vamos a considerar únicamente arrays.

Podemos reescribir nuestra función factors usando notación do como sigue:

1 factors :: Int -> Array (Array Int)
2 factors n = filter (\xs -> product xs == n) $ do
3   i <- 1 .. n
4   j <- i .. n
5   pure [i, j]

La palabra clave do comienza un bloque de código que usa notación do. El bloque consiste de expresiones de estos tipos:

• Expresiones que ligan elementos de un array a un nombre. Estas se indican con la flecha apuntando hacia atrás <-, con un nombre a la izquierda y una expresión a la derecha de tipo array.
• Expresiones que no ligan elementos del array a nombres. La última línea pure [i, j] es un ejemplo de este tipo de expresión.
• Expresiones que dan nombre a expresiones, usando la palabra clave let.

Con suerte, esta nueva notación hará la estructura del algoritmo más clara. Si reemplazas mentalmente la flecha <- con la palabra “elige”, puedes leerlo como sigue: “elige un elemento i entre 1 y n, luego elige un elemento j entre i y n, y finalmente devuelve [i, j]”.

En la última línea usamos la función pure. Esta función puede ser evaluada en PSCi, pero tenemos que proporcionar un tipo:

1 > pure [1, 2] :: Array (Array Int)
2 [[1, 2]]

En el caso de arrays, pure simplemente construye un array de un único elemento. De hecho, podemos modificar nuestra función factors para que use esta forma en lugar de usar pure:

1 factors :: Int -> Array (Array Int)
2 factors n = filter (\xs -> product xs == n) $ do
3   i <- 1 .. n
4   j <- i .. n
5   [[i, j]]

El resultado será el mismo.

Guardas (guards)

Otra mejora que podemos hacer a la función factors es poner el filtro dentro del array por comprensión. Esto es posible usando la función guard del módulo Control.MonadZero (del paquete purescript-control):

1 import Control.MonadZero (guard)
2 
3 factors :: Int -> Array (Array Int)
4 factors n = do
5   i <- 1 .. n
6   j <- i .. n
7   guard $ i * j == n
8   pure [i, j]

Al igual que pure, podemos aplicar la función guard en PSCi para entender cómo funciona. El tipo de la función guard es más general de lo que necesitamos aquí:

1 > import Control.MonadZero
2 
3 > :type guard
4 forall m. MonadZero m => Boolean -> m Unit

En nuestro caso, podemos asumir que PSCi reportó el siguiente tipo:

1 Boolean -> Array Unit

Para nuestros propósitos, los siguientes cálculos nos dicen todo lo que necesitamos saber de la función guard sobre arrays:

1 > import Data.Array
2 
3 > length $ guard true
4 1
5 
6 > length $ guard false
7 0

Esto es, si a guard se le pasa una expresión que evalúa a true, devuelve un array con un único elemento. Si la expresión devuelve false, su resultado está vacío.

Esto significa que si la guarda falla, la rama actual del array por comprensión terminará de manera temprana sin resultados. Lo que significa que una llamada a guard es equivalente a usar filter en el array intermedio. Dependiendo de la aplicación, puede que prefieras usar guard en lugar de filter. Prueba las dos definiciones de factors para verificar que dan el mismo resultado.

Pliegues (folds)

Los pliegues por la izquierda y por la derecha sobre arrays proporcionan otra clase de funciones interesantes que se pueden implementar usando recursividad.

Comienza importando el módulo Data.Foldable e inspecciona los tipos de las funciones foldl y foldr usando PSCi

1 > import Data.Foldable
2 
3 > :type foldl
4 forall a b f. Foldable f => (b -> a -> b) -> b -> f a -> b
5 
6 > :type foldr
7 forall a b f. Foldable f => (a -> b -> b) -> b -> f a -> b

Estos tipos son más necesarios de lo que nos interesa por ahora. Para los propósitos de este capítulo, podemos asumir que PSCi nos da la siguiente respuesta (más específica):

1 > :type foldl
2 forall a b. (b -> a -> b) -> b -> Array a -> b
3 
4 > :type foldr
5 forall a b. (a -> b -> b) -> b -> Array a -> b

En ambos casos, el tipo a corresponde a los tipos de los elementos de nuestro array. El tipo b se puede considerar como el tipo de un “acumulador”, que acumulará un resultado según recorremos el array.

La diferencia entre las funciones foldl y foldr es la dirección del recorrido. foldl pliega el array “desde la izquierda”, mientras que foldr lo pliega “desde la derecha”.

Veamos estas funciones en acción. Usemos foldl para sumar un array de enteros. El tipo a será Int, y podemos también elegir que el tipo resultante b sea Int. Necesitamos proporcionar tres argumentos: una función Int -> Int -> Int que sumará el siguiente elemento al acumulador, un valor inicial para el acumulador de tipo Int, y un array de Int a sumar. Para el primer argumento, podemos simplemente usar el operador de suma, y el valor inicial del acumulador será cero:

1 > foldl (+) 0 (1 .. 5)
2 15

En este caso, no importa si usamos foldl o foldr ya que el resultado es el mismo, no importa el orden en que sucedan las sumas:

1 > foldr (+) 0 (1 .. 5)
2 15

Escribamos un ejemplo donde la elección de la función de pliegue importa para ilustrar la diferencia. En lugar de la función de suma, usemos la concatenación de cadenas para construir una cadena:

1 > foldl (\acc n -> acc <> show n) "" [1,2,3,4,5]
2 "12345"
3 
4 > foldr (\n acc -> acc <> show n) "" [1,2,3,4,5]
5 "54321"

Esto ilustra la diferencia entre ambas funciones. La expresión de pliegue por la izquierda es equivalente a la siguiente aplicación:

1 ((((("" <> show 1) <> show 2) <> show 3) <> show 4) <> show 5)

Mientras que el pliegue por la derecha es equivalente a esto:

1 ((((("" <> show 5) <> show 4) <> show 3) <> show 2) <> show 1)

Recursividad final (tail recursion)

La recursividad es una técnica potente para especificar algoritmos, pero tiene un problema: evaluar funciones recursivas en JavaScript puede llevar a errores de desbordamiento de pila si las entradas son demasiado grandes.

Es fácil verificar el problema con el siguiente código en PSCi:

1 > f 0 = 0
2 > f n = 1 + f (n - 1)
3 
4 > f 10
5 10
6 
7 > f 100000
8 RangeError: Maximum call stack size exceeded

Esto es un problema. Si vamos a adoptar la recursividad como una técnica estándar de la programación funcional, necesitamos una forma de tratar con la recursividad posiblemente infinita.

PureScript proporciona una solución parcial a este problema en la forma de optimización de recursividad final (tail recursion optimization).

Nota: se pueden implementar soluciones al problema más completas en bibliotecas usando el llamado trampolining, pero eso está fuera del ámbito de este capítulo. El lector interesado puede consultar la documentación de los paquetes purescript-free y purescript-tailrec.

La observación clave que permite la optimización de la recursividad final es la siguiente: una llamada recursiva en una posición de cola (tail position) a una función se puede reemplazar por un salto, que no reserva una trama de pila. Una llamada está en posición de cola cuando es la última llamada hecha antes de que la función retorne. Esta es la razón por la que hemos observado un desbordamiento de pila en el ejemplo - la llamada recursiva a f no estaba en posición de cola.

En la práctica, el compilador de PureScript no sustituye la llamada recursiva por un salto, en su lugar sustituye la función recursiva por un bucle while.

Aquí hay un ejemplo de una función recursiva con todas las llamadas recursivas en posición de cola:

1 fact :: Int -> Int -> Int
2 fact 0 acc = acc
3 fact n acc = fact (n - 1) (acc * n)

Date cuenta de que la llamada recursiva a fact es lo último que sucede en esta función - está en posición de cola.

Acumuladores (accumulators)

Una forma común de convertir una función que no es recursiva final en una función recursiva final es usar un parámetro acumulador. Un parámetro acumulador es un parámetro adicional que se añade a una función para acumular un valor de retorno, en contraposición a usar el valor de retorno para acumular el resultado.

Por ejemplo, considera esta recursividad de array que invierte el array de entrada añadiendo elementos de la cabeza del array de entrada al final del resultado:

1 reverse :: forall a. Array a -> Array a
2 reverse [] = []
3 reverse xs = snoc (reverse (unsafePartial tail xs))
4                   (unsafePartial head xs)

Esta implementación no es recursiva final, de manera que el JavaScript generado provocará un desbordamiento de pila cuando se ejecute sobre un array de entrada grande. Sin embargo, podemos hacerla recursiva final introduciendo un segundo argumento para acumular el resultado:

1 reverse :: forall a. Array a -> Array a
2 reverse = reverse' []
3   where
4     reverse' acc [] = acc
5     reverse' acc xs = reverse' (unsafePartial head xs : acc)
6                                (unsafePartial tail xs)

En este caso, delegamos a la función auxiliar reverse', que realiza la tarea pesada de invertir el array. Date cuenta de que la función reverse' es recursiva final. Su única llamada recursiva está en el último caso y está en posición de cola. Esto significa que el código generado será un bucle while y no desbordará la pila para entradas grandes.

Para entender la segunda implementación de reverse, date cuenta de que la función auxiliar reverse' usa esencialmente el parámetro acumulador para mantener un trozo adicional de estado, el resultado parcialmente construido. El resultado comienza vacío y crece en un elemento para cada elemento del array de entrada. Sin embargo, dado que los elementos posteriores se añaden al principio del array, el resultado es el array original invertido.

Date cuenta también de que mientras que podemos considerar el acumulador como “estado”, no sucede una mutación directa. El acumulador es un array inmutable y simplemente usamos argumentos de función para hilar el estado durante el cálculo.

Prefiere pliegues a recursividad explícita

Si podemos escribir nuestras funciones recursivas usando recursividad final podemos beneficiarnos de las optimizaciones de recursividad final, de manera que parece tentador intentar escribir todas nuestras funciones de esta forma. Sin embargo, es fácil olvidar que muchas funciones se puedes escribir directamente como un pliegue sobre un array o una estructura de datos similar. Escribir algoritmos directamente en términos de combinadores como map y fold tiene la ventaja de la simplicidad del código. Estos combinadores se comprenden bien y, de esta manera, comunican la intención del algoritmo mucho mejor que la recursividad explícita.

Por ejemplo, el ejemplo reverse se puede escribir como un pliegue al menos de dos maneras. Aquí hay una versión que usa foldr:

1 > import Data.Foldable
2 
3 > :paste
4 … reverse :: forall a. Array a -> Array a
5 … reverse = foldr (\x xs -> xs <> [x]) []
6 … ^D
7 
8 > reverse [1, 2, 3]
9 [3,2,1]

Escribir reverse en términos de foldl se deja como ejercicio para el lector.

Un sistema de ficheros virtual

En esta sección, vamos a aplicar lo que hemos aprendido escribiendo funciones para trabajar sobre un modelo de un sistema de ficheros. Usaremos asociaciones, pliegues y filtros para trabajar con un API predefinido.

El módulo Data.Path define un API para un sistema de ficheros virtual como sigue:

• Hay un tipo Path que representa rutas en el sistema de ficheros.
• Hay una ruta root que representa el directorio raíz.
• La función ls enumera los ficheros de un directorio.
• La función filename devuelve el nombre de fichero para un Path.
• La función size devuelve el tamaño de fichero para un Path que representa un fichero.
• La función isDirectory comprueba si un Path es un fichero o un directorio.

En términos de tipos, tenemos las siguientes definiciones de tipos:

1 root :: Path
2 
3 ls :: Path -> Array Path
4 
5 filename :: Path -> String
6 
7 size :: Path -> Maybe Number
8 
9 isDirectory :: Path -> Boolean

Podemos probar la API en PSCi:

 1 $ pulp repl
 2 
 3 > import Data.Path
 4 
 5 > root
 6 /
 7 
 8 > isDirectory root
 9 true
10 
11 > ls root
12 [/bin/,/etc/,/home/]

El módulo FileOperations define funciones que usan la API de Data.Path. No necesitas modificar el módulo Data.Path o entender su implementación. Trabajaremos en el módulo FileOperations.

Listando todos los ficheros

Escribamos una función que realiza una enumeración profunda de todos los ficheros dentro de un directorio. La función tendrá el siguiente tipo:

1 allFiles :: Path -> Array Path

Podemos definir esta función mediante recursividad. Primero, podemos usar ls para enumerar los hijos inmediatos de un directorio. Para cada hijo, podemos aplicar recursivamente allFiles, que devolverá un array de rutas. concatMap nos permitirá aplicar allFiles y aplanar los resultados al mismo tiempo.

Finalmente, podemos usar el operador cons : para incluir el fichero actual:

1 allFiles file = file : concatMap allFiles (ls file)

Nota: El operador cons : tiene de hecho un rendimiento pobre en arrays inmutables, de manera que en general no se recomienda. El rendimiento se puede mejorar usando otras estructuras de datos como listas enlazadas y secuencias.

Probemos esta función en PSCi:

1 > import FileOperations
2 > import Data.Path
3 
4 > allFiles root
5 
6 [/,/bin/,/bin/cp,/bin/ls,/bin/mv,/etc/,/etc/hosts, ...]

¡Estupendo! Ahora veamos si podemos escribir esta función usando un array por comprensión usando notación do.

Recuerda que una flecha hacia atrás corresponde a elegir un elemento de un array. El primer paso es elegir el elemento de los hijos inmediatos del argumento. A continuación, llamamos a la función recursivamente para ese fichero. Como estamos usando notación do, hay una llamada implícita a concatMap que concatena todos los resultados recursivos.

Aquí está la nueva versión:

1 allFiles' :: Path -> Array Path
2 allFiles' file = file : do
3   child <- ls file
4   allFiles' child

Prueba la nueva versión en PSCi. Debes obtener el mismo resultado. Te dejo decidir qué versión ves más clara.

Conclusión

En este capítulo hemos cubierto las bases de la recursividad en PureScript como una manera de expresar algoritmos de manera concisa. También hemos introducido los operadores infijos definidos por el usuario, funciones estándar sobre arrays como asociaciones, filtros y pliegues, y los arrays por comprensión que combinan estas ideas. Finalmente, hemos mostrado la importancia de la recursividad final para evitar errores de desbordamiento de pila, y como usar parámetros acumuladores para convertir funciones a forma recursiva final.

Ajuste de patrones (pattern matching)

Objetivos del capítulo

Este capítulo presentará dos nuevos conceptos: tipos de datos algebraicos (algebraic data types) y ajuste de patrones. También cubriremos brevemente una interesante característica del sistema de tipos de PureScript: polimorfismo de fila (row polymorphism).

El ajuste de patrones es una técnica común en la programación funcional y permite al desarrollador escribir funciones compactas que expresan ideas potencialmente complejas partiendo su implementación en múltiples casos.

Los tipos de datos algebraicos son una característica del sistema de tipos de PureScript que permiten un nivel similar de expresividad en el lenguaje de los tipos; están estrechamente relacionados con el ajuste de patrones.

El objetivo del capítulo será escribir una biblioteca para describir y manipular gráficos vectoriales simples usando tipos de datos algebraicos y ajuste de patrones.

Preparación del proyecto

El código fuente de este capítulo está definido en el fichero src/Data/Picture.purs.

El proyecto usa algunos paquetes de Bower que ya hemos visto y añade las siguientes dependencias nuevas:

• purescript-globals, que proporciona acceso a algunos valores y funciones comunes en JavaScript.
• purescript-math, que proporciona acceso al modulo Math de JavaScript.

El módulo Data.Picture define un tipo de datos Shape para formas simples y un tipo Picture para colecciones de formas, junto a funciones para trabajar con esos tipos.

El módulo importa el módulo Data.Foldable, que proporciona funciones para plegar estructuras de datos:

1 module Data.Picture where
2 
3 import Prelude
4 import Data.Foldable (foldl)

El módulo Data.Picture también importa los módulos Global y Math, pero esta vez usando la palabra reservada as:

1 import Global as Global
2 import Math as Math

Esto deja disponibles los tipos y funciones de esos módulos, pero sólo usando nombres cualificados (qualified names), como Global.infinity y Math.max. Esto puede ser útil para evitar importaciones superpuestas o simplemente para dejar claro de qué modulo se importan ciertas cosas.

Nota: no es necesario usar el mismo nombre de módulo que el original en un import cualificado. Nombres cualificados más cortos como import Math as M son posibles y bastante comunes.

Ajuste de patrones simple

Comencemos viendo un ejemplo. Aquí hay una función que calcula el máximo común divisor de dos enteros usando ajuste de patrones:

1 gcd :: Int -> Int -> Int
2 gcd n 0 = n
3 gcd 0 m = m
4 gcd n m = if n > m
5             then gcd (n - m) m
6             else gcd n (m - n)

Este algoritmo se llama Algoritmo de Euclides. Si buscas su definición, probablemente encontrarás un conjunto que ecuaciones matemáticas que se parecen bastante al código de arriba. Este es uno de los beneficios del ajuste de patrones: te permite definir el código por casos, escribiendo código simple y declarativo que parece una especificación de una función matemática.

Una función escrita usando ajuste de patrones funciona emparejando conjuntos de condiciones con sus resultados. Cada línea se llama alternativa o caso. Las expresiones a la izquierda del signo igual se llaman patrones (patterns), y cada caso consiste en uno o más patrones separados por espacios. Los casos describen qué condiciones deben satisfacer los argumentos antes de que se evalúe y devuelva la expresión a la derecha del signo igual. Cada caso se intenta por orden y el primer caso cuyos patrones se ajusten a sus entradas determina el valor de retorno.

Por ejemplo, la función gcd se evalúa usando los siguientes pasos:

• Se prueba con el primer caso: si el segundo argumento es cero, la función devuelve n (el primer argumento).
• Si no, se prueba con el segundo caso: si el primer argumento es cero, la función devuelve m (el segundo argumento).
• De otra manera, la función se evalúa y devuelve la expresión de la última línea.

Date cuenta de que los patrones pueden ligar valores a nombres; cada línea en el ejemplo liga uno o dos de los nombres n y m a sus valores de entrada. Según vayamos aprendiendo distintos tipos de patrones veremos que diferentes tipos de patrones corresponden a diferentes formas de elegir nombres para los argumentos de entrada.

Patrones simples

El ejemplo de código anterior demuestra dos tipos de patrones:

• Patrones enteros literales, que se ajustan a algo de tipo Int sólo si el valor coincide exactamente.
• Patrones variables, que ligan su argumento a un nombre.

Hay otros tipos de patrones simples:

• Literales Number, String, Char y Boolean.
• Patrones comodín (wildcard patterns), indicados mediante un subrayado (_), que van a ajustarse a cualquier argumento y que no ligan ningún nombre.

Aquí tenemos dos ejemplos más que demuestran el uso de estos patrones simples:

1 fromString :: String -> Boolean
2 fromString "true" = true
3 fromString _      = false
4 
5 toString :: Boolean -> String
6 toString true  = "true"
7 toString false = "false"

Prueba estas funciones en PSCi.

Guardas

En el ejemplo del Algoritmo de Euclides, hemos usado una expresión if .. then .. else para decidir entre las dos alternativas m > n y m <= n. Otra opción en este caso sería usar una guarda.

Una guarda es una expresión de valor booleano que debe ser satisfecha junto a las restricciones impuestas por los patrones. Aquí esta el Algoritmo de Euclides reescrito para usar una guarda:

1 gcd :: Int -> Int -> Int
2 gcd n 0 = n
3 gcd 0 n = n
4 gcd n m | n > m     = gcd (n - m) m
5         | otherwise = gcd n (m - n)

En este caso, la tercera línea usa una guarda para imponer la condición extra de que el primer argumento es estrictamente mayor que el segundo.

Como este ejemplo muestra, las guardas aparecen a la izquierda del símbolo igual, separadas de la lista de patrones por un carácter barra (|).

Patrones de array (array patterns)

Los patrones de array literales proporcionan una forma de ajustarse a arrays de una longitud fija. Por ejemplo, supongamos que queremos escribir una función isEmpty que identifica arrays vacíos. Podríamos hacer esto usando un patrón de array vacío ([]) en la primera alternativa:

1 isEmpty :: forall a. Array a -> Boolean
2 isEmpty [] = true
3 isEmpty _ = false

Aquí tenemos otra función que se ajusta a arrays de longitud 5, ligando cada uno de sus cinco argumentos de distinta manera:

1 takeFive :: Array Int -> Int
2 takeFive [0, 1, a, b, _] = a * b
3 takeFive _ = 0

El primer patrón sólo se ajusta a arrays de cinco elementos, cuyo primer y segundo elemento son 0 y 1 respectivamente. En ese caso, la función devuelve el producto del tercer y cuarto elemento. En cualquier otro caso, la función devuelve cero. Por ejemplo, en PSCi:

 1 > :paste
 2 … takeFive [0, 1, a, b, _] = a * b
 3 … takeFive _ = 0
 4 … ^D
 5 
 6 > takeFive [0, 1, 2, 3, 4]
 7 6
 8 
 9 > takeFive [1, 2, 3, 4, 5]
10 0
11 
12 > takeFive []
13 0

Los patrones de array literales nos permiten ajustar arrays de una longitud fija, pero PureScript no proporciona ningún medio para ajustar arrays de una longitud no especificada, ya que descomponer arrays inmutables de esta manera resulta en rendimiento pobre. Si necesitas una estructura de datos que soporte este tipo de ajuste, la manera recomendada es usar Data.List. Existen otras estructuras de datos que proporcionan rendimiento asintótico mejorado para distintas operaciones.

Patrones de registro (record patterns) y polimorfismo de fila (row polymorphism)

Los patrones de registro se usan para ajustar (lo has adivinado) registros.

Los patrones de registro tienen el mismo aspecto que los registros literales, pero en lugar de especificar valores a la derecha de los dos puntos, especificamos un símbolo a ligar para cada campo.

Por ejemplo: este patrón se ajusta a cualquier registro que contenga campos llamados first y last, y liga sus valores a los nombres x e y respectivamente:

1 showPerson :: { first :: String, last :: String } -> String
2 showPerson { first: x, last: y } = y <> ", " <> x

Los patrones de registro proporcionan un buen ejemplo de una característica interesante del sistema de tipos de PureScript: polimorfismo de fila. Supongamos que hemos definido showPerson sin la firma de tipos de arriba. ¿Cuál sería su tipo inferido? Curiosamente, no es el mismo tipo que le dimos:

1 > showPerson { first: x, last: y } = y <> ", " <> x
2 
3 > :type showPerson
4 forall r. { first :: String, last :: String | r } -> String

¿Qué es la variable de tipo r aquí? Bien, si probamos showPerson en PSCi vemos algo interesante:

1 > showPerson { first: "Phil", last: "Freeman" }
2 "Freeman, Phil"
3 
4 > showPerson { first: "Phil", last: "Freeman", location: "Los Angeles" }
5 "Freeman, Phil"

Podemos añadir campos adicionales al registro y la función showPerson sigue funcionando. Siempre y cuando el registro contenga los campos first y last de tipo String, la aplicación de función está bien tipada. Sin embargo, no es válido llamar a showPerson con menos campos:

1 > showPerson { first: "Phil" }
2 
3 Type of expression lacks required label "last"

Podemos leer la nueva firma de tipos de showPerson como “toma cualquier registro con campos first y last que son de tipo String y cualquier otro campo, y devuelve un String”.

Esta función es polimórfica en la fila r de los campos del registro, de ahí el nombre polimorfismo de fila.

Date cuenta de que también podríamos haber escrito:

1 > showPerson p = p.last <> ", " <> p.first

y PSCi habría inferido el mismo tipo.

Veremos el polimorfismo de fila de nuevo más tarde cuando veamos los efectos extensibles.

Patrones anidados (nested patterns)

Tanto los patrones de array como los patrones de registro combinan patrones más pequeños para construir patrones más grandes. Mayormente, los ejemplos anteriores sólo han usado patrones simples dentro de patrones array y registro, pero es importante notar que los patrones se pueden anidar arbitrariamente, lo que permite definir funciones usando condiciones en tipos de datos potencialmente complejos.

Por ejemplo, este código combina dos patrones de registro:

1 type Address = { street :: String, city :: String }
2 
3 type Person = { name :: String, address :: Address }
4 
5 livesInLA :: Person -> Boolean
6 livesInLA { address: { city: "Los Angeles" } } = true
7 livesInLA _ = false

Patrones nombrados (named patterns)

Los patrones pueden ser nombrados para traer nombres adicionales al contexto cuando se usan patrones anidados. Cualquier patrón puede nombrarse usando el símbolo @.

Por ejemplo, esta función ordena arrays de dos elementos, nombrando los dos elementos, pero también nombrando el propio array:

1 sortPair :: Array Int -> Array Int
2 sortPair arr@[x, y]
3   | x <= y = arr
4   | otherwise = [y, x]
5 sortPair arr = arr

De esta manera, nos ahorramos reservar un nuevo array si el par está ya ordenado.

Expresiones “case” (case expressions)

Los patrones no sólo aparecen en las declaraciones de función de nivel superior. Es posible usar patrones para ajustarse a un valor intermedio de un cálculo usando una expresión case. Las expresiones case proporcionan una utilidad similar a las funciones anónimas: no siempre es deseable dar un nombre a una función, y una expresión case nos permite evitar nombrar una función sólo porque queremos usar un patrón.

Aquí tenemos un ejemplo. Esta función calcula el “sufijo cero más largo” de un array (el sufijo más largo que suma cero):

1 import Data.Array.Partial (tail)
2 import Partial.Unsafe (unsafePartial)
3 
4 lzs :: Array Int -> Array Int
5 lzs [] = []
6 lzs xs = case sum xs of
7            0 -> xs
8            _ -> lzs (unsafePartial tail xs)

Por ejemplo:

1 > lzs [1, 2, 3, 4]
2 []
3 
4 > lzs [1, -1, -2, 3]
5 [-1, -2, 3]

Esta función trabaja por análisis de casos. Si el array está vacío, nuestra única opción es devolver un array vacío. Si el array no está vacío, usamos una expresión case para partir en dos casos. Si la suma del array es cero, devolvemos el array completo. Si no, recurrimos sobre la cola del array.

Fallos de ajuste de patrones (pattern match failures) y funciones parciales (partial functions)

Si los patrones de una expresión case se prueban por orden, ¿qué pasa en el caso en que ninguno de los patrones de las alternativas se ajustan a sus entradas? En este caso, la expresión case fallará en tiempo de ejecución con un fallo de ajuste de patrones.

Podemos ver este comportamiento con un ejemplo simple:

1 import Partial.Unsafe (unsafePartial)
2 
3 partialFunction :: Boolean -> Boolean
4 partialFunction = unsafePartial \true -> true

Esta función contiene un único caso, que sólo se ajusta a una única entrada, true. Si compilamos este fichero y probamos en PSCi con cualquier otro argumento, veremos un error en tiempo de ejecución:

1 > partialFunction false
2 
3 Failed pattern match

Las funciones que devuelven un valor para cualquier combinación de entradas se llaman funciones totales, y las funciones que no se llaman parciales.

Generalmente se considera mejor definir funciones totales donde sea posible. Si se sabe que una función no devuelve un resultado para algún conjunto válido de entradas, normalmente es mejor devolver un valor de tipo Maybe a para algún a, usando Nothing para indicar fallo. De esta manera, la presencia o ausencia de un valor se puede indicar de una forma segura a nivel de tipos.

El compilador de PureScript generará un error si puede detectar que tu función no es total debido a un ajuste de patrones incompleto. La función unsafePartial se puede usar para silenciar estos errores (¡si estas seguro de que tu función parcial es segura!). Si quitamos la llamada a la función unsafePartial en la función de antes, el compilador generará el siguiente error:

1 A case expression could not be determined to cover all inputs.
2 The following additional cases are required to cover all inputs:
3 
4   false

Esto nos dice que el valor false no coincide con ningún patrón. En general, estos avisos pueden incluir múltiples casos sin ajuste.

Si también omitimos la firma de tipos de antes:

1 partialFunction true = true

PSCi infiere un tipo curioso:

1 > :type partialFunction
2 
3 Partial => Boolean -> Boolean

Veremos más tipos que involucran el símbolo => más tarde en el libro (están relacionados con las clases de tipos), pero por ahora, basta observar que PureScript lleva el registro de las funciones parciales usando el sistema de tipos, y que debemos decir explícitamente al comprobador de tipos cuándo son seguras.

El compilador generará también un aviso en ciertos casos cuando puede detectar casos redundantes (esto es, un caso sólo se ajusta a valores que habrían sido ajustados por un caso anterior):

1 redundantCase :: Boolean -> Boolean
2 redundantCase true = true
3 redundantCase false = false
4 redundantCase false = false

En este caso, el último caso se identifica correctamente como redundante:

1 Redundant cases have been detected.
2 The definition has the following redundant cases:
3 
4   false

Nota: PSCi no muestra avisos, de manera que para reproducir este ejemplo tendrás que salvar esta función a un fichero y compilarla usando pulp build.

Tipos de datos algebraicos (algebraic data types)

Esta sección introducirá una característica del sistema de tipos de PureScript llamada tipos de datos algebraicos (o ADTs), que se relacionan fundamentalmente con el ajuste de patrones.

Sin embargo, vamos primero a considerar un ejemplo motivador que proporcionará la base para una solución al problema de este capítulo de implementar una biblioteca de gráficos vectoriales simple.

Supongamos que queremos definir un tipo para representar algunos tipos simples de formas: líneas, rectángulos, círculos, texto, etc. En un lenguaje orientado a objetos, probablemente definiríamos una interfaz o clase abstracta Shape, y una subclase concreta para cada tipo de forma con la que queramos trabajar.

Sin embargo, esta aproximación tiene un inconveniente importante: para trabajar con Shapes de manera abstracta, es necesario identificar todas las operaciones que uno quiera realizar y definirlas en la interfaz Shape. Se vuelve difícil añadir nuevas operaciones sin romper la modularidad.

Los tipos de datos algebraicos proporcionan una forma segura a nivel de tipos de resolver este tipo de problemas si el conjunto de formas se conoce por anticipado. Es posible definir nuevas operaciones sobre Shape de una forma modular manteniendo la seguridad a nivel de tipos.

Así es como Shape se puede representar como un tipo de datos algebraico:

1 data Shape
2   = Circle Point Number
3   | Rectangle Point Number Number
4   | Line Point Point
5   | Text Point String

El tipo Point se puede definir también como un tipo de datos algebraico como sigue:

1 data Point = Point
2   { x :: Number
3   , y :: Number
4   }

El tipo de datos Point ilustra algunos puntos interesantes:

• Los datos portados por un constructor de ADT no están restringidos a tipos primitivos: los constructores pueden incluir registros, arrays, o incluso otros ADTs.
• Aunque los ADTs son útiles para describir datos con múltiples constructores, también pueden ser útiles cuando hay un único constructor.
• Los constructores de un tipo de datos algebraico pueden tener el mismo nombre que el propio ADT. Esto es bastante común y es importante no confundir el constructor de tipo Point con el constructor de datos Point; viven en espacios de nombres distintos.

Esta declaración define Shape como una suma de diferentes constructores, y para cada constructor identifica los datos que se incluyen. Una Shape es o bien un Circle que contiene un Point para el centro y un radio (un número), o un Rectangle, o una Line, o Text. No hay otras formas de construir un valor de tipo Shape.

Los tipos de datos algebraicos se presentan usando la palabra reservada data, seguida del nombre del tipo nuevo y cualquier argumento de tipo. Los constructores de tipo se definen tras el signo igual y se separan con barras (|).

Veamos otro ejemplo de las bibliotecas estándar de PureScript. Vimos antes el tipo Maybe que se usa para definir valores opcionales. Aquí está su definición del paquete purescript-maybe:

1 data Maybe a = Nothing | Just a

Este ejemplo muestra el uso del parámetro de tipo a. Leyendo la barra como la palabra “o”, su definición es bastante legible: “un valor de tipo Maybe a es o bien Nothing o Just un valor de tipo a”.

Los constructores de datos se pueden usar también para definir estructuras de datos recursivas. Aquí hay otro ejemplo definiendo un tipo de datos para listas enlazadas de elementos de tipo a:

1 data List a = Nil | Cons a (List a)

Este ejemplo está sacado del paquete purescript-lists. Aquí, el constructor Nil representa una lista vacía, y Cons se usa para crear listas no vacías a partir de un elemento de cabeza y una cola. Date cuenta como la cola se define usando el tipo de datos List a, convirtiéndose en un tipo de datos recursivo.

Usando ADTs

Es bastante simple usar los constructores de un tipo de datos algebraico para construir un valor: simplemente los aplicamos como funciones, proporcionando argumentos correspondientes a los datos incluidos en el constructor apropiado.

Por ejemplo, el constructor Line definido arriba requería dos Points, así que para construir un Shape usando el constructor Line tenemos que proporcionar dos argumentos de tipo Point:

1 exampleLine :: Shape
2 exampleLine = Line p1 p2
3   where
4     p1 :: Point
5     p1 = Point { x: 0.0, y: 0.0 }
6 
7     p2 :: Point
8     p2 = Point { x: 100.0, y: 50.0 }

Para construir los puntos p1 y p2, aplicamos el constructor Point a su único argumento, que es un registro.

Así, construir valores de tipos de datos algebraicos es simple, pero ¿cómo los usamos? Aquí es donde aparece la conexión importante con el ajuste de patrones: la única forma de consumir valores de un tipo algebraico de datos es usar ajuste de patrones para ajustarse a su constructor.

Veamos un ejemplo. Supongamos que queremos convertir una Shape en String. Tenemos que usar ajuste de patrones para descubrir qué constructor se usó para construir la Shape. Lo podemos hacer como sigue:

1 showPoint :: Point -> String
2 showPoint (Point { x: x, y: y }) =
3   "(" <> show x <> ", " <> show y <> ")"
4 
5 showShape :: Shape -> String
6 showShape (Circle c r)      = ...
7 showShape (Rectangle c w h) = ...
8 showShape (Line start end)  = ...
9 showShape (Text p text) = ...

Cada constructor se puede usar como un patrón, y los argumentos al constructor se pueden ligar usando sus propios patrones. Considera el primer caso de showShape: si la Shape coincide con el constructor Circle, metemos en contexto los argumentos de Circle (centro y radio) usando dos patrones variables c y r. Los otros casos son similares.

showPoint es otro ejemplo de ajuste de patrones. En este caso, sólo hay un único caso, pero usamos un patrón anidado para ajustarnos a los nombres del registro contenido dentro del constructor Point.

Doble sentido en registros (record puns)

La función showPoint se ajusta a un registro dentro de su argumento, ligando las propiedades x e y a valores con los mismos nombres. En PureScript podemos simplificar este tipo de ajuste de patrones como sigue:

1 showPoint :: Point -> String
2 showPoint (Point { x, y }) = ...

Aquí, únicamente especificamos los nombres de las propiedades y no necesitamos especificar los nombres de los valores que queremos ligar. Es lo que se llama un doble sentido en registro.

También es posible usar doble sentido en registro para construir registros. Por ejemplo, si tenemos valores llamados x e y en el ámbito, podemos construir un Point usando Point{ x, y}`:

1 origin :: Point
2 origin = Point { x, y }
3   where
4     x = 0.0
5     y = 0.0

Esto puede ser útil para mejorar la legibilidad del código en algunas circunstancias.

Newtypes

Hay un caso especial importante de tipos de datos algebraicos llamados newtypes. Los newtypes se presentan usando la palabra reservada newtype en lugar de data.

Los newtypes deben definir exactamente un constructor, y ese constructor debe tomar exactamente un argumento. Esto es, un newtype da un nuevo nombre a un tipo existente. De hecho, los valores de un newtype tienen la misma representación en tiempo de ejecución que el tipo subyacente. Son, sin embargo, distintos desde el punto de vista del sistema de tipos. Esto da un nivel adicional de seguridad de tipos.

Como ejemplo, podemos querer definir newtypes como sinónimos de Number para atribuir unidades como píxeles y pulgadas:

1 newtype Pixels = Pixels Number
2 newtype Inches = Inches Number

De esta forma, es imposible pasar un valor de tipo Pixels a una función que espera Inches, pero no hay sobrecoste de rendimiento en tiempo de ejecución.

Los newtypes cobrarán importancia cuando veamos las clases de tipos en el siguiente capítulo, ya que nos permiten adjuntar comportamiento diferente a un tipo sin cambiar su representación en tiempo de ejecución.

Una biblioteca para gráficos vectoriales

Usemos los tipos de datos que hemos definido antes para crear una biblioteca simple para usar gráficos vectoriales.

Definamos un sinónimo de tipo para una Picture, un simple array de Shapes:

1 type Picture = Array Shape

Para depurar, querremos ser capaces de convertir una Picture en algo legible. La función showPicture nos permite hacerlo:

1 showPicture :: Picture -> Array String
2 showPicture = map showShape

Probémosla. Compila tu módulo con pulp build y abre PSCi con pulp repl:

 1 $ pulp build
 2 $ pulp repl
 3 
 4 > import Data.Picture
 5 
 6 > :paste
 7 … showPicture
 8 …   [ Line (Point { x: 0.0, y: 0.0 })
 9 …          (Point { x: 1.0, y: 1.0 })
10 …   ]
11 … ^D
12 
13 ["Line [start: (0.0, 0.0), end: (1.0, 1.0)]"]

Calculando rectángulos de delimitación

El código de ejemplo para este módulo contiene una función bounds que calcula el rectángulo de delimitación mínimo para una Picture.

El tipo de datos Bounds define un rectángulo de delimitación. También está definido como un tipo algebraico de datos con un único constructor:

1 data Bounds = Bounds
2   { top    :: Number
3   , left   :: Number
4   , bottom :: Number
5   , right  :: Number
6   }

bounds usa la función foldl de Data.Foldable para recorrer el array de Shapes en una Picture, y acumular el rectángulo de delimitación mínimo:

1 bounds :: Picture -> Bounds
2 bounds = foldl combine emptyBounds
3   where
4     combine :: Bounds -> Shape -> Bounds
5     combine b shape = union (shapeBounds shape) b

En el caso base, necesitamos encontrar el rectángulo de delimitación mínimo de una Picture vacía, y el rectángulo de delimitación mínimo vacío definido por emptyBounds es suficiente.

La función de acumulación combine se define en un bloque where. combine toma un rectángulo de delimitación calculado por la llamada recursiva foldl y la siguiente Shape del array, y usa la función union para calcular la unión de dos rectángulos de delimitación. La función shapeBounds calcula la delimitación de un único shape usando ajuste de patrones.

Conclusión

En este capítulo, hemos visto el ajuste de patrones, una técnica básica pero potente de la programación funcional. Hemos visto cómo usar patrones simples así como patrones de array y de registro para ajustar partes de estructuras de datos profundas.

Este capítulo también ha presentado los tipos de datos algebraicos, que están estrechamente relacionados con el ajuste de patrones. Hemos visto cómo los tipos de datos algebraicos permiten descripciones concisas de estructuras de datos y proporcionan una forma modular de extender tipos de datos con nuevas operaciones.

Finalmente, hemos visto el polimorfismo de línea, un potente tipo de abstracción que permite dar un tipo a muchas funciones idiomáticas de JavaScript. Veremos esta idea de nuevo más adelante.

En el resto del libro, usaremos ADTs y ajuste de patrones extensamente, de manera que va a resultar rentable familiarizarse con ellos ya. Intenta crear tus propios tipos de datos algebraicos y escribir funciones que los consuman usando ajuste de patrones.

Clases de tipos (type classes)

Objetivos del capítulo

Este capítulo presentará una poderosa forma de abstracción disponible en el sistema de tipos de PureScript: las clases de tipos.

El ejemplo motivador de este capítulo será una biblioteca para resumir (hashing) estructuras de datos. Veremos cómo la maquinaria de las clases de tipos nos permiten resumir estructuras de datos complejas sin tener que pensar directamente en la estructura de los propios datos.

Veremos también una colección de clases de tipos estándar del Prelude de PureScript y de las bibliotecas estándar. El código PureScript se apoya firmemente en la potencia de las clases de tipos para expresar ideas de manera concisa, así que será beneficioso que te familiarices con estas clases.

Preparación del proyecto

El código fuente de este capítulo está definido en el fichero src/Data/Hashable.purs.

El proyecto tiene las siguientes dependencias Bower:

• purescript-maybe, definiendo el tipo de datos Maybe, que representa valores opcionales.
• purescript-tuples, definiendo el tipo de datos Tuple, que representa pares de valores.
• purescript-either, definiendo el tipo de datos Either, que representa uniones disjuntas.
• purescript-strings, que define funciones que operan sobre cadenas.
• purescript-functions, que define algunas funciones auxiliares para definir funciones PureScript.

El módulo Data.Hashable importa varios módulos proporcionados por estos paquetes Bower. ## ¡Muéstrame!

Nuestro primer ejemplo simple de clase de tipos viene dado por una función que hemos visto varias veces: la función show, que toma un valor y lo representa como una cadena.

show está definido por una clase de tipos del módulo Prelude llamada Show, definida como sigue:

1 class Show a where
2   show :: a -> String

Este código declara una nueva clase de tipos llamada Show, que está parametrizada por la variable de tipo a.

Una instancia de clase de tipos contiene implementaciones de las funciones definidas en una clase de tipos, especializada para un tipo particular.

Por ejemplo, aquí está la definición de la instancia de clase de tipos Show para valores Boolean, tomada del Prelude:

1 instance showBoolean :: Show Boolean where
2   show true = "true"
3   show false = "false"

Este código declara una instancia de clase de tipos llamada showBoolean; en PureScript, las instancias de clases de tipos tienen nombre para ayudar con la legibilidad del JavaScript generado. Decimos que el tipo Boolean pertenece a la clase de tipos Show.

Podemos probar la clase de tipos Show en PSCi mostrando unos cuantos valores de diferentes tipos:

 1 > import Prelude
 2 
 3 > show true
 4 "true"
 5 
 6 > show 1.0
 7 "1.0"
 8 
 9 > show "Hello World"
10 "\"Hello World\""

Estos ejemplos muestran cómo usar show para mostrar valores de varios tipos primitivos, pero también podemos usar show para mostrar valores de tipos más complejos:

1 > import Data.Tuple
2 
3 > show (Tuple 1 true)
4 "(Tuple 1 true)"
5 
6 > import Data.Maybe
7 
8 > show (Just "testing")
9 "(Just \"testing\")"

Si intentamos mostrar un valor del tipo Data.Either obtenemos un mensaje de error interesante:

1 > import Data.Either
2 > show (Left 10)
3 
4 The inferred type
5 
6     forall a. Show a => String
7 
8 has type variables which are not mentioned in the body of the type. Consider add\
9 ing a type annotation.

El problema aquí no es que no haya una instancia Show para el tipo que tratamos de mostrar, sino que PSCi ha sido incapaz de inferir el tipo. Esto viene indicado por el tipo desconocido a en el tipo inferido.

Podemos anotar la expresión con un tipo usando el operador ::, de manera que PSCi pueda elegir la instancia de clase de tipos correcta:

1 > show (Left 10 :: Either Int String)
2 "(Left 10)"

Algunos tipos ni siquiera tienen una instancia Show definida. Un ejemplo es el tipo función ->. Si tratamos de mostrar una función de Int a Int, obtenemos un mensaje de error apropiado del comprobador de tipos:

1 > import Prelude
2 > show $ \n -> n + 1
3 
4 No type class instance was found for
5 
6   Data.Show.Show (Int -> Int)

Clases de tipos comunes

En esta sección, vamos a ver algunas clases de tipos estándar definidas en el Prelude y en las bibliotecas estándar. Estas clases de tipos forman la base de muchos patrones comunes de abstracción en el código PureScript idiomático, de manera que una comprensión básica de sus funciones es altamente recomendable.

Eq

La clase de tipos Eq define la función eq que comprueba la igualdad entre dos valores. El operador == es un sinónimo de eq.

1 class Eq a where
2   eq :: a -> a -> Boolean

Date cuenta de que en cualquier caso, los dos argumentos deben tener el mismo tipo. No tiene sentido comprobar la igualdad entre dos valores de distinto tipo.

Prueba la clase de tipos Eq en PSCi:

1 > 1 == 2
2 false
3 
4 > "Test" == "Test"
5 true

Ord

La clase de tipos Ord define la función compare, que se puede usar para comparar dos valores para tipos que soporten ordenación. Los operadores de comparación < y > junto a sus compañeros no estrictos <= y >= se pueden definir en términos de compare.

1 data Ordering = LT | EQ | GT
2 
3 class Eq a <= Ord a where
4   compare :: a -> a -> Ordering

La función compare compara dos valores y devuelve un Ordering con tres alternativas:

• LT - si el primer argumento es menor que el segundo.
• EQ - si el primer argumento es igual al segundo.
• GT - si el primer argumento es mayor que el segundo.

De nuevo, podemos probar la función compare en PSCi:

1 > compare 1 2
2 LT
3 
4 > compare "A" "Z"
5 LT

Field

La clase de tipos Field identifica los tipos que soportan operadores numéricos como suma, resta, multiplicación y división. Se proporciona para abstraer sobre esos operadores de manera que puedan ser reutilizados donde sea apropiado.

Nota: Al igual que las clases de tipos Eq y Ord, la clase de tipos Field tiene soporte especial en el compilador de PureScript, de manera que expresiones simples como 1 + 2 * 3 se traduzcan a JavaScript simple, en contraposición a llamadas de función que se despachan en base a una implementación de clase de tipos.

1 class EuclideanRing a <= Field a

La clase de tipos Field está compuesta de varias superclases generales más. Esto nos permite hablar de manera abstracta de tipos que soportan algunas, no todas, de las operaciones de Field. Por ejemplo, un tipo de números naturales sería cerrado bajo la suma y la multiplicación, pero no necesariamente bajo la resta, de manera que ese tipo puede tener una instancia de la clase Semiring (que es una superclase de Num), pero no una instancia de Ring o Field.

Las superclases se explicarán más tarde en este capítulo, pero la jerarquía completa de tipos numéricos está más allá del ámbito de este capítulo. Animamos al lector interesado a leer la documentación de las superclases de Field en purescript-prelude.

Semigrupos (semigroups) y Monoides (monoids)

La clase de tipos Semigroup identifica aquellos tipos que soportan una operación append para combinar dos valores:

1 class Semigroup a where
2   append :: a -> a -> a

Las cadenas forman un semigrupo bajo la concatenación de cadenas normal, y lo mismo es cierto para los arrays. Muchas otras instancias estándar se proporcionan en el paquete purescript-monoid.

El operador de concatenación <>, que ya hemos visto, se proporciona como un sinónimo de append.

La clase de tipos Monoid (proporcionada por el paquete purescript-monoid) extiende el tipo Semigroup con el concepto de un valor vacío llamado mempty:

1 class Semigroup m <= Monoid m where
2   mempty :: m

De nuevo, las cadenas y los arrays son ejemplos simples de monoides.

Una instancia de la clase de tipos Monoid para un tipo describe cómo acumular un resultado con ese tipo, comenzando por un valor “vacío” y combinando nuevos resultados. Por ejemplo, podemos escribir una función que concatena un grupo de valores en algún monoide usando un pliegue. En PSCi:

1 > import Data.Monoid
2 > import Data.Foldable
3 
4 > foldl append mempty ["Hello", " ", "World"]  
5 "Hello World"
6 
7 > foldl append mempty [[1, 2, 3], [4, 5], [6]]
8 [1,2,3,4,5,6]

El paquete purescript-monoid proporciona muchos ejemplos de monoides y semigrupos que usaremos en el resto del libro.

Foldable

Si la clase de tipos Monoid identifica los tipos que pueden actuar como resultado de un pliegue, la clase de tipos Foldable identifica los constructores de tipos que pueden ser usados como la fuente de un pliegue.

La clase de tipos Foldable se suministra en el paquete purescript-foldable-traversable, que también contiene instancias para algunos contenedores estándar como Array y Maybe.

Las firmas de tipo de las funciones pertenecientes a Foldable son un poco más complicadas que las que hemos visto hasta ahora:

1 class Foldable f where
2   foldr :: forall a b. (a -> b -> b) -> b -> f a -> b
3   foldl :: forall a b. (b -> a -> b) -> b -> f a -> b
4   foldMap :: forall a m. Monoid m => (a -> m) -> f a -> m

Es instructivo especializar para el caso en que f es el constructor de tipo array. En este caso, podemos reemplazar f a con Array a para cualquier a, y nos damos cuenta de que los tipos de foldl y foldr se convierten en los tipos que vimos cuando encontramos por primera vez los pliegues sobre arrays.

¿Qué pasa con foldMap? Bien, esa se convierte en forall a m. Monoid m => (a -> m) -> Array a -> m. Esta firma de tipo dice que podemos elegir cualquier tipo m para nuestro tipo resultado, siempre y cuando ese tipo sea una instancia de la clase de tipos Monoid. Si podemos proporcionar una función que convierte nuestros elementos de array en valores en ese monoide, entonces podemos acumular sobre nuestro array usando la estructura del monoide y devolver un único valor.

Probemos foldMap en PSCi:

1 > import Data.Foldable
2 
3 > foldMap show [1, 2, 3, 4, 5]
4 "12345"

Aquí, elegimos el monoide para cadenas, que concatena cadenas, y la función show que representa un Int como un String. Entonces, pasando un array de enteros, vemos que los resultados de mostrar cada entero han sido concatenados en una única String.

Pero los arrays no son los únicos tipos plegables. purescript-foldable-traversable también define instancias de Foldable para tipos como Maybe y Tuple, y otras bibliotecas como purescript-lists definen instancias de Foldable para sus propios tipos de datos. Foldable captura la noción de contenedor ordenado.

Funtor (functor) y leyes de clases de tipos (type class laws)

El Prelude también define una colección de clases de tipos que permiten un estilo de programación funcional con efectos secundarios en PureScript: Functor, Applicative y Monad. Veremos estas abstracciones más adelante, pero por ahora veamos la definición de la clase de tipos Functor, que ya hemos visto en forma de la función map:

1 class Functor f where
2   map :: forall a b. (a -> b) -> f a -> f b

La función map (y su sinónimo <$>) permite “elevar” una función a una estructura de datos. La definición precisa de la palabra “elevar” depende de la estructura de datos en cuestión, pero ya hemos visto su comportamiento para algunos tipos simples:

 1 > import Prelude
 2 
 3 > map (\n -> n < 3) [1, 2, 3, 4, 5]
 4 [true, true, false, false, false]
 5 
 6 > import Data.Maybe
 7 > import Data.String (length)
 8 
 9 > map length (Just "testing")
10 (Just 7)

¿Cómo podemos entender el significado de la función map cuando actúa sobre muchas estructuras diferentes de una manera diferente cada vez?

Podemos intuir que la función map aplica la función que se le da a cada elemento del contenedor y construye un nuevo contenedor a partir de los resultados, con la misma forma que el original. ¿Pero cómo podemos precisar este concepto?

Se espera que las instancias de la clase de tipos Functor obedezcan un conjunto de leyes llamadas las leyes del funtor (functor laws):

• map id xs = xs
• map g (map f xs) = map (g <<< f) xs

La primera ley es la ley de identidad. Dice que elevar la función identidad (la función que devuelve su argumento sin cambios) sobre una estructura devuelve la estructura original. Esto tiene sentido, ya que la función identidad no modifica su entrada.

La segunda ley es la ley de composición. Dice que mapear una función sobre una estructura y mapear una segunda función es lo mismo que mapear la composición de las dos funciones sobre la estructura.

Signifique lo que signifique “elevar” en el sentido general, debe ser cierto que cualquier definición razonable de elevar una función sobre una estructura de datos debe obedecer estas reglas.

Muchas clases de tipos estándar vienen con su propio conjunto de leyes similares. Las leyes dadas a una clase de tipos dan estructura a las funciones de esa clase de tipos y nos permiten estudiar sus instancias en general. El lector interesado puede investigar las leyes atribuidas a las clases de tipos estándar que ya hemos visto.

Anotaciones de tipo (type annotations)

Los tipos de las funciones pueden ser restringidos usando clases de tipos. Aquí tenemos un ejemplo: supongamos que queremos escribir una función que comprueba si tres valores son iguales, usando la igualdad definida por una instancia de clase de tipos Eq.

1 threeAreEqual :: forall a. Eq a => a -> a -> a -> Boolean
2 threeAreEqual a1 a2 a3 = a1 == a2 && a2 == a3

La declaración de tipo parece un tipo polimórfico ordinario definido usando forall. Sin embargo, a continuación hay una restricción de clase de tipos Eq a separada del resto del tipo por una flecha doble =>.

Este tipo dice que podemos llamar threeAreEqual con cualquier elección de tipo a, siempre y cuando haya una instancia Eq disponible para a en uno de los módulos importados.

Los tipos restringidos pueden contener varias instancias de clases de tipos, y los tipos de las instancias no están limitados a simples variables de tipo. Aquí hay otro ejemplo que usa instancias Ord y Show para comparar dos valores:

1 showCompare :: forall a. Ord a => Show a => a -> a -> String
2 showCompare a1 a2 | a1 < a2 =
3   show a1 <> " is less than " <> show a2
4 showCompare a1 a2 | a1 > a2 =
5   show a1 <> " is greater than " <> show a2
6 showCompare a1 a2 =
7   show a1 <> " is equal to " <> show a2

Date cuenta de que se pueden especificar restricciones múltiples usando el símbolo => múltiples veces, de la misma manera que especificamos funciones currificadas de varios argumentos. Pero recuerda no confundir ambos símbolos:

• a -> b denota el tipo de funciones del tipo a al tipo b, mientras que
• a => b aplica la restricción a al tipo b.

El compilador PureScript intentará inferir los tipos restringidos cuando no se proporcione una anotación de tipo. Esto puede ser util si queremos usar el tipo más general posible para una función.

Para verlo, intenta usar una de las clases de tipos estándar como Semiring en PSCi:

1 > import Prelude
2 
3 > :type \x -> x + x
4 forall a. Semiring a => a -> a

Aquí, podríamos haber anotado esta función como Int -> Int, o Number -> Number, pero PSCi nos muestra que el tipo más general funciona para cualquier Semiring, permitiéndonos usar nuestra función tanto con Ints como con Numbers.

Instancias superpuestas (overlapping instances)

PureScript tiene otra regla relativa a las instancias de clases de tipos, llamada la regla de instancias superpuestas (overlapping instances rule). Cuando una instancia de clase de tipos se necesita en un punto de llamada a función, PureScript usará la información inferida por el comprobador de tipos para elegir la instancia correcta. En ese momento, debe haber exactamente una instancia apropiada para ese tipo. Si hay varias instancias válidas, el compilador emitirá un aviso.

Para mostrar esto, podemos intentar crear dos instancias de clase de tipos en conflicto para un tipo de ejemplo. En el siguiente código, creamos dos instancias superpuestas de Show para le tipo T:

 1 module Overlapped where
 2 
 3 import Prelude
 4 
 5 data T = T
 6 
 7 instance showT1 :: Show T where
 8   show _ = "Instance 1"
 9 
10 instance showT2 :: Show T where
11   show _ = "Instance 2"

Este módulo compilará sin avisos. Sin embargo, si usamos show sobre el tipo T (requiriendo al compilador que encuentre una instancia Show), la regla de instancias superpuestas se aplicará dando un aviso:

1 Overlapping instances found for Prelude.Show T

La regla de instancias superpuestas debe cumplirse para que la selección de instancias de clases de tipos sea un proceso predecible. Si permitiésemos que existiesen dos instancias de clase de tipos para un tipo, cualquiera podría elegirse dependiendo del orden de importación de los módulos, y podría llevar a comportamiento impredecible del programa en tiempo de ejecución, algo no deseable.

Si realmente es cierto que hay dos instancias de clase de tipos válidas para un tipo que satisfacen las leyes apropiadas, una aproximación común es definir newtypes para envolver el tipo existente. Como se permite que los newtypes diferentes tengan diferentes instancias de clases de tipos, para la regla de instancias superpuestas ya no es un problema. Esta aproximación se usa en las bibliotecas estándar de PureScript, por ejemplo en purescript-maybe, donde el tipo Maybe a tiene múltiples instancias válidas para la clase de tipos Monoid.

Dependencias de instancia (instance dependencies)

Al igual que la implementación de funciones puede depender de las instancias de clases de tipos usando tipos restringidos, también puede la implementación de instancias de clases de tipos depender de otras instancias de clases de tipos. Esto proporciona una forma poderosa de inferencia de programa, en la que la implementación de un programa se puede inferir usando sus tipos.

Por ejemplo, considera la clase de tipos Show. Podemos escribir una instancia de clase de tipos para mostrar arrays de elementos, siempre y cuando tengamos una manera de mostrar los propios elementos.

1 instance showArray :: Show a => Show (Array a) where
2   ...

Si una instancia de una clase de tipos depende de varias instancias, esas instancias deben agruparse en paréntesis y separarse por comas a la izquierda del símbolo =>:

1 instance showEither :: (Show a, Show b) => Show (Either a b) where
2   ...

Estas dos instancia de clase de tipos se proporciona el la biblioteca purescript-prelude.

Cuando se compila el programa, se elige la instancia correcta de clase de tipos para Show basándose en el tipo inferido del argumento pasado a show. La instancia seleccionada puede depender de muchas relaciones de instancia, pero esta complejidad no se expone al desarrollador.

Clases de tipos de varios parámetros (multi parameter type classes)

No es cierto que una clase de tipos pueda tomar un único tipo como argumento. Es el caso más común, pero de hecho, una clase de tipos se puede parametrizar por cero o más argumentos de tipo.

Veamos un ejemplo de una clase de tipos con dos argumentos de tipo.

 1 module Stream where
 2 
 3 import Data.Array as Array
 4 import Data.Maybe (Maybe)
 5 import Data.String as String
 6 
 7 class Stream stream element where
 8   uncons :: stream -> Maybe { head :: element, tail :: stream }
 9 
10 instance streamArray :: Stream (Array a) a where
11   uncons = Array.uncons
12 
13 instance streamString :: Stream String Char where
14   uncons = String.uncons

El módulo Stream define una clase Stream que identifica tipos que se pueden ver como flujos de elementos, donde los elementos pueden ser extraídos del frente del flujo usando la función uncons.

Date cuenta de que la clase de tipos Stream está parametrizada no sólo por el tipo del flujo, sino también por sus elementos. Esto permite definir instancias de clase de tipos para el mismo tipo de flujo pero con diferentes tipos de elementos.

El módulo define dos instancias de clase de tipos: una instancia para arrays, donde uncons quita el elemento de cabeza del array usando ajuste de patrones, y una instancia para String que quita el primer carácter de una String.

Podemos escribir funciones que trabajan sobre flujos arbitrarios. Por ejemplo, aquí hay una función que acumula un resultado en algún Monoid basándose en los elementos de un flujo:

1 import Prelude
2 import Data.Monoid (class Monoid, mempty)
3 
4 foldStream :: forall l e m. Stream l e => Monoid m => (e -> m) -> l -> m
5 foldStream f list =
6   case uncons list of
7     Nothing -> mempty
8     Just cons -> f cons.head <> foldStream f cons.tail

Intenta usar foldStream en PSCi para diferentes tipos de Stream y diferentes tipos de Monoid.

Dependencias funcionales (functional dependencies)

Las clases de tipos multiparamétricas pueden ser muy útiles, pero pueden llevar fácilmente a tipos confusos e incluso problemas con la inferencia de tipos. Como ejemplo simple, supongamos que tenemos que escribir una función tail genérica sobre flujos usando la clase Stream dada arriba:

1 genericTail xs = map _.tail (uncons xs)

Esto nos da un mensaje de error algo confuso:

1 The inferred type
2 
3   forall stream a. Stream stream a => stream -> Maybe stream
4 
5 has type variables which are not mentioned in the body of the type. Consider add\
6 ing a type annotation.

El problema es que la función genericTail no usa el tipo element mencionado en la definición de la clase de tipos Stream, de manera que el tipo queda sin resolver.

Peor aún, ni siquiera podemos usar genericTail aplicándolo a un tipo específico de flujo:

1 > map _.tail (uncons "testing")
2 
3 The inferred type
4 
5   forall a. Stream String a => Maybe String
6 
7 has type variables which are not mentioned in the body of the type. Consider add\
8 ing a type annotation.

Aquí, podemos esperar que el compilador elija la instancia streamString. Después de todo, una String es un flujo de Chars, y no puede ser un flujo de ningún otro tipo de elementos.

El compilador no es capaz de hacer esa deducción automáticamente, y no puede confiar en la instancia streamString. Sin embargo, podemos ayudar al compilador añadiendo una pista en la definición de la clase de tipo:

1 class Stream stream element | stream -> element where
2   uncons :: stream -> Maybe { head :: element, tail :: stream }

Aquí, stream -> element se llama dependencia funcional. Una dependencia funcional asegura una relación funcional entre los argumentos de tipo de una clase de tipo multiparamétrica. Esa dependencia funcional dice al compilador que hay una función de tipos de flujo a tipos de elemento (únicos), de manera que si el compilador sabe el tipo del flujo, puede conocer el tipo del elemento.

Esta pista es suficiente para que el compilador infiera el tipo correcto para nuestra función tail genérica de arriba:

1 > :type genericTail
2 forall stream element. Stream stream element => stream -> Maybe stream
3 
4 > genericTail "testing"
5 (Just "esting")

Las dependencias funcionales pueden ser bastante útiles cuando se usan clases de tipo multiparamétricas para diseñar ciertas APIs.

Clases de tipos nularias (nullary type classes)

¡Podemos incluso definir clases de tipos sin argumentos de tipo! Se corresponden a aseveraciones (asserts) en tiempo de compilación sobre nuestras funciones, permitiéndonos seguir la pista a propiedades globales de nuestro código en el sistema de tipos.

Un ejemplo importante es la clase Partial que vimos anteriormente cuando hablábamos de las funciones parciales. Hemos visto ya las funciones parciales head y tail definidas en Data.Array.Partial:

1 head :: forall a. Partial => Array a -> a
2 
3 tail :: forall a. Partial => Array a -> Array a

¡Date cuenta de que no hay instancias definidas para la clase de tipos Partial! Hacerlo anularía su propósito: intentar usar la función head directamente resultará en un error de tipo:

1 > head [1, 2, 3]
2 
3 No type class instance was found for
4 
5   Prim.Partial

En su lugar, podemos volver a publicar la restricción Partial para cualquier función que haga uso de funciones parciales:

1 secondElement :: forall a. Partial => Array a -> a
2 secondElement xs = head (tail xs)

Ya hemos visto la función unsafePartial que nos permite tratar una función parcial como una función normal (de manera insegura). Esta función está definida en el módulo Partial.Unsafe:

1 unsafePartial :: forall a. (Partial => a) -> a

Date cuenta de que la restricción Partial aparece entre paréntesis a la izquierda de la flecha de función, pero no en el forall de fuera. Esto es, unsafePartial es una función de valores parciales a valores normales.

Superclases (superclasses)

Al igual que podemos expresar relaciones entre instancias de clases de tipos haciendo que una instancia dependa de otra, podemos expresar relaciones entre las propias clases de tipos usando las llamadas superclases.

Decimos que una clase de tipos es una superclase de otra si se requiere que toda instancia de la segunda clase sea una instancia de la primera, e indicamos una relación de superclase en la definición de clase usando una doble flecha hacia atrás.

Hemos visto ya algunos ejemplos de relaciones de superclase: La clase Eq es una superclase de Ord, y la clase Semigroup es una superclase de Monoid. Para todas las instancias de clase de tipos de la clase Ord tiene que haber una instancia correspondiente de Eq para el mismo tipo. Esto tiene sentido, ya que en muchos casos, cuando la función compare informa de que dos valores son incomparables, a menudo queremos usar la clase Eq para determinar si de hecho son iguales.

En general, tiene sentido definir una relación de superclase cuando las leyes de la subclase mencionan los miembros de la superclase. Por ejemplo, es razonable asumir, para cualquier par de instancias Ord y Eq, que si dos valores son iguales bajo la instancia Eq, entonces la función compare debe devolver EQ. En otras palabras, a == b debe ser ciero exactamente cuando compare a b se evalúa a EQ. Esta relación a nivel de leyes justifica la relación de superclase entre Eq y Ord.

Otra razón para definir una relación de superclase es en el caso donde hay una clara relación “es-un” entre las dos clases. Esto es, todos los miembros de la subclase son miembros de la superclase también.

Una clase de tipos para funciones resumen

En la última sección de este capítulo vamos a usar las lecciones del resto del capítulo para crear una biblioteca para resumir estructuras de datos.

Date cuenta de que esta biblioteca es para propósitos de demostración solamente y no pretende proporcionar un mecanismo de resumen robusto.

¿Qué propiedades podemos esperar de una función resumen?

• Una función resumen debe ser determinista y mapear valores iguales a códigos resumen iguales.
• Una función resumen debe distribuir sus resultados de manera aproximadamente uniforme sobre el conjunto de códigos resumen.

La primera propiedad se parece bastante a una ley para una clase de tipos, mientras que la segunda propiedad es más bien un contrato informal y ciertamente no sería realizable con el sistema de tipos de PureScript. Sin embargo, esto debe proporcionar la intuición para la siguiente clase de tipos:

1 newtype HashCode = HashCode Int
2 
3 hashCode :: Int -> HashCode
4 hashCode h = HashCode (h `mod` 65535)
5 
6 class Eq a <= Hashable a where
7   hash :: a -> HashCode

Con la ley asociada de que a == b implica hash a == hash b.

Pasaremos el resto de esta sección construyendo una biblioteca de instancias y funciones asociadas a la clase de tipos Hashable.

Necesitaremos una forma de combinar códigos hash de una forma determinista:

1 combineHashes :: HashCode -> HashCode -> HashCode
2 combineHashes (HashCode h1) (HashCode h2) = hashCode (73 * h1 + 51 * h2)

La función combineHashes mezclará dos códigos resumen y redistribuirá el resultado sobre el intervalo 0-65535.

Escribamos una función que usa la restricción Hashable para restringir los tipos de sus entradas. Una tarea común que requiere una función resumen es determinar si dos valores se mapean al mismo código resumen. La relación hashEqual proporciona dicha capacidad:

1 hashEqual :: forall a. Hashable a => a -> a -> Boolean
2 hashEqual = eq `on` hash

Esta función usa la función on de Data.Function para definir la igualdad de resumen en términos de igualdad de códigos resumen, y debe leerse como una definición declarativa de la igualdad de resumen: dos valores son iguales a nivel de resumen si son iguales después de que cada valor haya pasado a través de la función hash.

Escribamos algunas instancias de Hashable para algunos tipos primitivos. Comencemos con una instancia para enteros. Ya que HashCode es en realidad un entero envuelto, esto es fácil, podemos usar la función auxiliar hashCode:

1 instance hashInt :: Hashable Int where
2   hash = hashCode

Podemos también definir una instancia simple para valores Boolean usando ajuste de patrones:

1 instance hashBoolean :: Hashable Boolean where
2   hash false = hashCode 0
3   hash true  = hashCode 1

Con una instancia para resumir enteros, podemos crear una instancia para resumir Chars usando la función toCharCode de Data.Char:

1 instance hashChar :: Hashable Char where
2   hash = hash <<< toCharCode

Para definir una instancia para arrays, podemos mapear la función hash sobre los elementos del array (si el tipo elemental es también una instancia de Hashable) y entonces realizar un pliegue por la izquierda sobre los códigos resultantes usando la función combineHashes:

1 instance hashArray :: Hashable a => Hashable (Array a) where
2   hash = foldl combineHashes (hashCode 0) <<< map hash

Date cuenta de cómo construimos instancias usando las instancias más simples que ya hemos escrito. Usemos nuestra nueva instancia para Array para definir una instancia para Strings, convirtiendo una String en un array de Chars:

1 instance hashString :: Hashable String where
2   hash = hash <<< toCharArray

¿Cómo podemos probar que estas instancias de Hashable satisfacen las leyes de clase de tipos que hemos enunciado antes? Necesitamos asegurarnos de que valores iguales tienen códigos resumen iguales. En casos como Int, Char, String y Boolean, esto es simple porque no hay valores de esos tipos que sean iguales en el sentido de Eq pero no sean idénticamente iguales.

¿Y en el caso de los tipos más interesantes? Para probar la ley de clase para la instancia de Array podemos usar inducción sobre la longitud del array. El único array con longitud cero es []. Cualquier par de arrays no vacíos son iguales sólo si tienen elementos iguales a la cabeza y sus colas son iguales, por la definición de Eq sobre arrays. Por hipótesis inductiva, las colas tienen códigos resumen iguales, y sabemos que los elementos de la cabeza tienen códigos resumen iguales si la instancia de Hashable a tiene que satisfacer la ley. Por lo tanto, los dos arrays tienen códigos resumen iguales, de manera que el Hashable (Array a) obedece la ley de clase de tipos también.

El código fuente para este capítulo incluye varios ejemplos de instancias Hashable, como instancias para los tipos Maybe y Tuple.

Conclusión

En este capítulo hemos visto las clases de tipos, una forma de abstracción orientada a tipos que permite formas potentes de reutilización de código. Hemos visto una colección de clases de tipos estándar de las bibliotecas estándar de PureScript, y hemos definido nuestra propia biblioteca basada en una clase de tipos para calcular códigos de función resumen.

Este capítulo también ha presentado la noción de leyes de clases de tipos, una técnica para probar propiedades acerca del código que usa clases de tipos como forma de abstracción. Las leyes de clases de tipos son parte de un tema más amplio llamado razonamiento ecuacional (equational reasoning), en el que las propiedades de un lenguaje de programación y su sistema de tipos se usan para permitir razonamiento lógico acerca de sus programas. Esta es una idea importante y es un tema al que vamos a volver durante el resto del libro.

Validación aplicativa (applicative validation)

Objetivos del capítulo

En este capítulo, vamos a conocer una importante abstracción nueva, el funtor aplicativo (applicative functor), descrito por la clase de tipos Applicative. No te preocupes si el nombre suena raro. Daremos un motivo para el concepto con un ejemplo práctico: validar datos de formulario. Esta técnica nos permite convertir código que normalmente implica un montón de código de comprobación repetitivo en una descripción declarativa de nuestro formulario.

Veremos también otra clase de tipos, Traversable, que describe los funtores transitables (traversable functors), y veremos cómo este concepto también aparece de manera muy natural a partir de soluciones a problemas del mundo real.

El código de ejemplo para este capítulo será una continuación del ejemplo de la agenda del capítulo 3. Esta vez, extenderemos los tipos de datos de nuestra agenda y escribiremos funciones para validar los valores de esos tipos. Estas funciones podrían usarse, por ejemplo, en una interfaz de usuario web para mostrar errores al usuario como parte del formulario de entrada de datos.

Preparación del proyecto

El código fuente para este capítulo está definido en los ficheros src/Data/AddressBook.purs y src/Data/AddressBook/Validation.purs.

El proyecto tiene unas cuantas dependencias Bower, muchas de las cuales ya hemos visto. Hay dos dependencias nuevas:

• purescript-control, que define funciones para abstraer el control de flujo usando clases de tipos como Applicative.
• purescript-validation, que define un funtor para validación aplicativa, el tema de este capítulo.

El módulo Data.AddressBook define tipos de datos e instancias Show para los tipos de nuestro proyecto, y el módulo Data.AddressBook.Validation contiene reglas de validación para esos tipos.

Generalizando la aplicación de funciones

Para explicar el concepto de un funtor aplicativo, consideremos el constructor de tipo Maybe que vimos antes.

El código fuente para este módulo define una función address que tiene el siguiente tipo:

1 address :: String -> String -> String -> Address

Esta función se usa para construir valores de tipo Address a partir de tres cadenas: un nombre de calle, una ciudad y un estado.

Podemos aplicar esta función fácilmente y ver el resultado en PSCi:

1 > import Data.AddressBook
2 
3 > address "123 Fake St." "Faketown" "CA"
4 Address { street: "123 Fake St.", city: "Faketown", state: "CA" }

Sin embargo, supongamos que no necesariamente tendremos una calle, ciudad, o estado, y queremos usar el tipo Maybe para indicar la ausencia de valor en cada uno de esos tres casos.

En un caso, podemos carecer de la ciudad. Si intentamos aplicar nuestra función directamente, recibiremos un error del comprobador de tipos:

 1 > import Data.Maybe
 2 > address (Just "123 Fake St.") Nothing (Just "CA")
 3 
 4 Could not match type
 5 
 6   Maybe String
 7 
 8 with type
 9 
10   String

Por supuesto, esperábamos este error. address toma cadenas como argumentos, no valores de tipo Maybe String.

Sin embargo, es razonable esperar que podamos “elevar” la función address para trabajar con valores opcionales descritos por el tipo Maybe. De hecho podemos, y el módulo Control.Apply proporciona la función lift3 que hace exactamente lo que necesitamos:

1 > import Control.Apply
2 > lift3 address (Just "123 Fake St.") Nothing (Just "CA")
3 
4 Nothing

En este caso, el resultado es Nothing porque uno de los argumentos (la ciudad) no está presente. Si proporcionamos los tres argumentos usando el constructor Just, el resultado contendrá un valor también:

1 > lift3 address (Just "123 Fake St.") (Just "Faketown") (Just "CA")
2 
3 Just (Address { street: "123 Fake St.", city: "Faketown", state: "CA" })

El nombre de la función lift3 indica que se puede usar para elevar funciones de 3 argumentos. Hay funciones similares definidas en Control.Apply para funciones de otro número de argumentos.

Elevando funciones arbitrarias

Podemos elevar funciones de un pequeño número de argumentos usando lift2, lift3, etc. ¿Pero cómo podemos generalizar esto a funciones arbitrarias?

Es instructivo ver el tipo de lift3:

1 > :type lift3
2 forall a b c d f. Apply f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d

En el ejemplo de Maybe anterior, el constructor de tipo f es Maybe, de manera que lift3 se especializa al siguiente tipo:

1 forall a b c d. (a -> b -> c -> d) -> Maybe a -> Maybe b -> Maybe c -> Maybe d

Este tipo dice que podemos tomar cualquier función de tres argumentos y elevarla para darnos una nueva función cuyos tipos de argumento y resultado están envueltos en Maybe.

Ciertamente esto no es posible para cualquier constructor de tipo f, de manera que ¿qué tiene Maybe que nos permite hacer esto? Bien, al especializar el tipo antes, hemos quitado la restricción de clase de tipos sobre f de la clase Apply. Apply se define en el Prelude como sigue:

1 class Functor f where
2   map :: forall a b. (a -> b) -> f a -> f b
3 
4 class Functor f <= Apply f where
5   apply :: forall a b. f (a -> b) -> f a -> f b

La clase de tipos Apply es una subclase de Functor y define una función adicional apply. Al igual que <$> se ha definido como un sinónimo de map, el módulo Prelude define <*> como un alias para apply. Como veremos, estos dos operadores se usan a menudo juntos.

El tipo de apply se parece bastante al tipo de map. La diferencia entre map y apply es que map toma una función como argumento, mientras que el primer argumento de apply está envuelto en el constructor de tipo f. Veremos cómo se usa pronto, pero primero veamos cómo implementar la clase de tipos Apply para el tipo Maybe:

1 instance functorMaybe :: Functor Maybe where
2   map f (Just a) = Just (f a)
3   map f Nothing  = Nothing
4 
5 instance applyMaybe :: Apply Maybe where
6   apply (Just f) (Just x) = Just (f x)
7   apply _        _        = Nothing

Esta instancia de clase de tipos dice que podemos aplicar una función opcional a un valor opcional, y el resultado está definido sólo si ambos están definidos.

Ahora veremos cómo map y apply se pueden usar juntas para elevar funciones de un número arbitrario de argumentos.

Para funciones de un argumento, podemos simplemente usar map directamente.

Para funciones de dos argumentos, digamos que tenemos una función currificada g de tipo a -> b -> c. Esto es equivalente al tipo a -> (b -> c), de manera que podemos aplicar map a g para obtener una nueva función de tipo f a -> f (b -> c) para cualquier constructor de tipo f con una instancia de Functor. Al aplicar parcialmente esta función al primer argumento elevado (de tipo f a), obtenemos una nueva función envuelta de tipo f (b -> c). Si también tenemos una instancia de Apply para f, podemos entonces usar apply para aplicar el segundo argumento elevado (de tipo f b) para obtener nuestro valor final de tipo f c.

Para juntarlo todo, vemos que si tenemos valores x :: f a y y :: f b, entonces la expresión (g <$> x) <*> y tiene tipo f c (recuerda, esta expresión es equivalente a apply (map g x) y). Las reglas de precedencia definidas en el Prelude nos permiten quitar los paréntesis: g <$> x <*> y.

En general, podemos usar <$> sobre el primer argumento y <*> para los argumentos restantes, como se muestra aquí para lift3:

1 lift3 :: forall a b c d f
2        . Apply f
3       => (a -> b -> c -> d)
4       -> f a
5       -> f b
6       -> f c
7       -> f d
8 lift3 f x y z = f <$> x <*> y <*> z

Se deja como ejercicio para el lector verificar los tipos involucrados en esta expresión.

Como ejemplo, podemos intentar elevar la función address sobre Maybe directamente usando las funciones <$> y <*>:

1 > address <$> Just "123 Fake St." <*> Just "Faketown" <*> Just "CA"
2 Just (Address { street: "123 Fake St.", city: "Faketown", state: "CA" })
3 
4 > address <$> Just "123 Fake St." <*> Nothing <*> Just "CA"
5 Nothing

Intenta elevar otras funciones de varios argumentos sobre Maybe de esta manera.

La clase de tipos Applicative

Hay una clase de tipos relacionada llamada Applicative, definida como sigue:

1 class Apply f <= Applicative f where
2   pure :: forall a. a -> f a

Applicative es una subclase de Apply y define la función pure. pure toma un valor y devuelve un valor cuyo tipo ha sido envuelto en el constructor de tipo f.

Aquí está la instancia Applicative para Maybe:

1 instance applicativeMaybe :: Applicative Maybe where
2   pure x = Just x

Si pensamos en los funtores aplicativos como funtores que permiten elevar funciones, entonces pure puede verse como una función que eleva funciones de cero argumentos.

Intuición para Applicative

Las funciones en PureScript son puras y no soportan efectos secundarios. Los funtores aplicativos nos permiten trabajar en “lenguajes de programación” más grandes que soportan algún tipo de efectos secundarios codificados por el funtor f.

Por ejemplo, el funtor Maybe representa el efecto secundario de valores potencialmente ausentes. Otros ejemplos incluyen Either err, que representa el efecto secundario de posibles errores de tipo err, y el funtor flecha r -> que representa el efecto secundario de leer de una configuración global. Por ahora consideraremos el funtor Maybe.

Si el funtor f representa este lenguaje de programación más grande con efectos, entonces las instancias Apply y Applicative nos permiten elevar valores y aplicación de funciones de nuestro lenguaje de programación más pequeño (PureScript) al nuevo lenguaje.

pure eleva valores puros (libres de efectos secundarios) al lenguaje mayor, y para funciones podemos usar map y apply como hemos descrito antes.

Esto plantea una pregunta: si podemos usar Applicative para empotrar funciones y valores PureScript en este nuevo lenguaje, ¿de que manera es el nuevo lenguaje mayor? La respuesta depende del funtor f. Si podemos encontrar expresiones de tipo f a que no pueden expresarse como pure x para algún x, entonces esa expresión representa un término que sólo existe en el lenguaje mayor.

Cuando f es Maybe, un ejemplo es la expresión Nothing: no podemos escribir Nothing como pure x para cualquier x. Por lo tanto, podemos pensar que PureScript se ha agrandado para incluir el nuevo término Nothing que representa un valor ausente.

Más efectos

Veamos unos cuantos ejemplos de elevar funciones sobre distintos funtores aplicativos.

Aquí hay una simple función de ejemplo definida en PSCi que une tres nombres para formar un nombre completo:

1 > import Prelude
2 
3 > fullName first middle last = last <> ", " <> first <> " " <> middle
4 
5 > fullName "Phillip" "A" "Freeman"
6 Freeman, Phillip A

Ahora supongamos que esta función forma la implementación de un servicio web con tres argumentos proporcionados como parámetros de la consulta. Queremos asegurarnos de que el usuario ha proporcionado los tres parámetros, así que usamos el tipo Maybe para indicar la presencia o ausencia de un parámetro. Podemos elevar fullName sobre Maybe para crear una implementación del servicio web que comprueba parámetros ausentes:

1 > import Data.Maybe
2 
3 > fullName <$> Just "Phillip" <*> Just "A" <*> Just "Freeman"
4 Just ("Freeman, Phillip A")
5 
6 > fullName <$> Just "Phillip" <*> Nothing <*> Just "Freeman"
7 Nothing

Date cuenta de que la función elevada devuelve Nothing si cualquiera de los argumentos era Nothing.

Esto es bueno, porque ahora podemos devolver una respuesta de error desde nuestro servicio web si los parámetros son inválidos. Sin embargo, sería mejor si pudiésemos indicar qué campo era incorrecto en la respuesta.

En lugar de elevar sobre Maybe, podemos elevar sobre Either String que permite devolver un mensaje de error. Primero, escribamos un operador para convertir entradas opcionales en cálculos que señalan un error usando Either String:

1 > :paste
2 … withError Nothing  err = Left err
3 … withError (Just a) _   = Right a
4 … ^D

Nota: En el funtor aplicativo Either err, el constructor Left indica un error y el Right indica éxito.

Ahora podemos elevar sobre Either String proporcionando un mensaje de error apropiado para cada parámetro:

1 > :paste
2 … fullNameEither first middle last =
3 …   fullName <$> (first  `withError` "First name was missing")
4 …            <*> (middle `withError` "Middle name was missing")
5 …            <*> (last   `withError` "Last name was missing")
6 … ^D
7 
8 > :type fullNameEither
9 Maybe String -> Maybe String -> Maybe String -> Either String String

Ahora nuestra función toma tres parámetros opcionales usando Maybe y devuelve o bien un mensaje de error String o un resultado String.

Podemos probar la función con diferentes entradas:

1 > fullNameEither (Just "Phillip") (Just "A") (Just "Freeman")
2 (Right "Freeman, Phillip A")
3 
4 > fullNameEither (Just "Phillip") Nothing (Just "Freeman")
5 (Left "Middle name was missing")
6 
7 > fullNameEither (Just "Phillip") (Just "A") Nothing
8 (Left "Last name was missing")

En este caso, vemos que el mensaje de error correspondiente al primer campo ausente, o un resultado exitoso si todos los campos han sido proporcionados. Sin embargo, si carecemos de varias entradas sólo vemos el primer error:

1 > fullNameEither Nothing Nothing Nothing
2 (Left "First name was missing")

Esto puede ser suficientemente bueno, pero si queremos ver una lista de todos los campos ausentes en el error necesitamos algo más potente que Either String. Veremos una solución más adelante en este capítulo.

Combinando efectos

Como ejemplo de la forma de trabajar con funtores aplicativos de manera abstracta, esta sección mostrará cómo escribir una función que combinará de manera genérica efectos secundarios codificados por un funtor aplicativo f.

¿Qué significa esto? Bien, supongamos que tenemos una lista de valores envueltos de tipo f a para algún a. Esto es, supongamos que tenemos una lista de tipo List (f a). De manera intuitiva, esto representa una lista de cálculos con efectos secundarios registrados por f, cada uno con tipo de retorno a. Si pudiésemos ejecutar todos estos cálculos en orden, obtendríamos una lista de resultados de tipo List a. Sin embargo, seguiríamos teniendo efectos secundarios registrados por f. Esto es, esperamos ser capaces de convertir algo de tipo List (f a) en algo de tipo f (List a) “combinando” los efectos dentro de la lista original.

Para cualquier lista de tamaño fijo n, hay una función de n argumentos que construye una lista de tamaño n a partir de esos argumentos. Por ejemplo, si n es 3, la función es \x y z -> x : y : z : Nil. Esta función tiene tipo a -> a -> a -> List a. Podemos usar la instancia de Applicative para List para elevar esta función sobre f, obteniendo una función de tipo f a -> f a -> f a -> f (List a). Pero ya que podemos hacer esto para cualquier n, tiene sentido que podamos ser capaces de realizar la misma elevación para cualquier lista de argumentos.

Esto significa que debemos ser capaces de escribir esta función:

1 combineList :: forall f a. Applicative f => List (f a) -> f (List a)

Esta función toma una lista de argumentos, que posiblemente tienen efectos secundarios, y devolverá una única lista envuelta, aplicando los efectos secundarios de cada uno.

Para escribir esta función, consideraremos la longitud de la lista de argumentos. Si la lista está vacía, no necesitamos realizar ningún efecto y podemos usar pure para simplemente devolver una lista vacía:

1 combineList Nil = pure Nil

De hecho, !esto es lo único que podemos hacer!

Si la lista no está vacía, tenemos un elemento a la cabeza que es un argumento envuelto de tipo f a, y una cola de tipo List (f a). Podemos combinar los efectos de manera recursiva en la cola, devolviendo un resultado de tipo f (List a). Podemos entonces usar <$> y <*> para elevar el constructor Cons sobre la cabeza y la nueva cola:

1 combineList (Cons x xs) = Cons <$> x <*> combineList xs

De nuevo, esta era la única implementación sensata basándose en los tipos que nos han dado.

Podemos probar esta función en PSCi, usando el constructor de tipo Maybe como ejemplo:

1 > import Data.List
2 > import Data.Maybe
3 
4 > combineList (fromFoldable [Just 1, Just 2, Just 3])
5 (Just (Cons 1 (Cons 2 (Cons 3 Nil))))
6 
7 > combineList (fromFoldable [Just 1, Nothing, Just 2])
8 Nothing

Cuando se especializa a Maybe, nuestra función devuelve un Just sólo si todos los elementos de la lista eran Just, de otra manera devuelve Nothing. Esto es consistente con nuestra intuición de trabajar en un lenguaje mayor que soporta valores opcionales; una lista de cálculos que devuelven valores opcionales sólo tiene un resultado si todos los cálculos contenían un resultado.

Pero la función combineList ¡funciona para cualquier Applicative! Podemos usarla para combinar cálculos que posiblemente señalan un error usando Either err, o que leen de una configuración global usando r ->.

Veremos la función combineList de nuevo más tarde cuando consideremos los funtores Traversable.

Validación aplicativa

El código fuente para este capítulo define varios tipos de datos que pueden ser usados en aplicaciones de agenda. Omitimos los detalles aquí, pero las funciones clave que exporta el módulo Data.AddressBook tienen los siguientes tipos:

1 address :: String -> String -> String -> Address
2 
3 phoneNumber :: PhoneType -> String -> PhoneNumber
4 
5 person :: String -> String -> Address -> Array PhoneNumber -> Person

Donde PhoneType se define como un tipo de datos algebraico:

1 data PhoneType = HomePhone | WorkPhone | CellPhone | OtherPhone

Estas funciones se pueden usar para construir una Person representando una entrada de la agenda. Por ejemplo, el siguiente valor está definido en Data.AddressBook:

1 examplePerson :: Person
2 examplePerson =
3   person "John" "Smith"
4          (address "123 Fake St." "FakeTown" "CA")
5   	     [ phoneNumber HomePhone "555-555-5555"
6          , phoneNumber CellPhone "555-555-0000"
7   	     ]

Prueba este valor en PSCi (hemos dado formato al resultado):

 1 > import Data.AddressBook
 2 
 3 > examplePerson
 4 Person
 5   { firstName: "John",
 6   , lastName: "Smith",
 7   , address: Address
 8       { street: "123 Fake St."
 9       , city: "FakeTown"
10       , state: "CA"
11       },
12   , phones: [ PhoneNumber
13                 { type: HomePhone
14                 , number: "555-555-5555"
15                 }
16             , PhoneNumber
17                 { type: CellPhone
18                 , number: "555-555-0000"
19                 }
20             ]
21   }  

Vimos en una sección anterior cómo podíamos usar el funtor Either String para validar estructuras de datos de tipo Person. Por ejemplo, dadas las funciones para validar los dos nombres de la estructura, podemos validar la estructura de datos completa como sigue:

 1 nonEmpty :: String -> Either String Unit
 2 nonEmpty "" = Left "Field cannot be empty"
 3 nonEmpty _  = Right unit
 4 
 5 validatePerson :: Person -> Either String Person
 6 validatePerson (Person o) =
 7   person <$> (nonEmpty o.firstName *> pure o.firstName)
 8          <*> (nonEmpty o.lastName  *> pure o.lastName)
 9          <*> pure o.address
10          <*> pure o.phones

En las dos primeras líneas, usamos la función nonEmpty para validar una cadena no vacía. nonEmpty devuelve un código de error (indicado por el constructor Left) si su entrada es vacía, o un valor exitoso vacío (unit) usando el constructor Right en caso contrario. Usamos el operador de secuenciación *> para indicar que queremos realizar dos validaciones, devolviendo el resultado del validador de la derecha. En este caso, el validador de la derecha simplemente usa pure para devolver la entrada sin cambios.

Las líneas finales no realizan ninguna validación sino que simplemente proporcionan los campos address y phones a la función person como argumentos restantes.

Podemos ver que esta función funciona en PSCi, pero tiene una limitación que ya hemos visto;

1 > validatePerson $ person "" "" (address "" "" "") []
2 (Left "Field cannot be empty")

El funtor aplicativo Either String sólo proporciona el primer error encontrado. Dada la entrada que hemos pasado, preferiríamos ver dos errores, uno para el nombre y otro para el apellido.

Hay otro funtor aplicativo proporcionado por la biblioteca purescript-validation. Este funtor se llama V y proporciona la capacidad de devolver errores en cualquier semigrupo. por ejemplo, podemos usar V (Array String) para devolver un array de Strings como errores, concatenando nuevos errores al final del array.

El módulo Data.AddressBook.Validation usa el funtor aplicativo V (Array String) para validar las estructuras de datos del módulo Data.AddressBook.

Aquí hay un ejemplo de validador tomado del módulo Data.AddressBook.Validation:

 1 type Errors = Array String
 2 
 3 nonEmpty :: String -> String -> V Errors Unit
 4 nonEmpty field "" = invalid ["Field '" <> field <> "' cannot be empty"]
 5 nonEmpty _     _  = pure unit
 6 
 7 lengthIs :: String -> Number -> String -> V Errors Unit
 8 lengthIs field len value | S.length value /= len =
 9   invalid ["Field '" <> field <> "' must have length " <> show len]
10 lengthIs _     _   _     =
11   pure unit
12 
13 validateAddress :: Address -> V Errors Address
14 validateAddress (Address o) =
15   address <$> (nonEmpty "Street" o.street *> pure o.street)
16           <*> (nonEmpty "City"   o.city   *> pure o.city)
17           <*> (lengthIs "State" 2 o.state *> pure o.state)

validateAddress valida una estructura Address. Comprueba que los campos street y city no están vacíos y comprueba que la cadena del campo state tiene longitud 2.

Date cuenta de cómo las funciones validadoras nonEmpty y lengthIs usan la función invalid proporcionada por el módulo Data.Validation para indicar un error. Como estamos trabajando en el semigrupo Array String, invalid toma un array de cadenas como argumento.

Podemos probar esta función en PSCi:

 1 > import Data.AddressBook
 2 > import Data.AddressBook.Validation
 3 
 4 > validateAddress $ address "" "" ""
 5 (Invalid [ "Field 'Street' cannot be empty"
 6          , "Field 'City' cannot be empty"
 7          , "Field 'State' must have length 2"
 8          ])
 9 
10 > validateAddress $ address "" "" "CA"
11 (Invalid [ "Field 'Street' cannot be empty"
12          , "Field 'City' cannot be empty"
13          ])

Esta vez, recibimos un array de todos los errores de validación.

Validadores con expresiones regulares (regular expression validators)

La función validatePhoneNumber usa una expresión regular para validar la forma de sus argumentos. La clave es una función de validación matches, que usa una Regex del módulo Data.String.Regex para validar su entrada:

1 matches :: String -> R.Regex -> String -> V Errors Unit
2 matches _     regex value | R.test regex value =
3   pure unit
4 matches field _     _     =
5   invalid ["Field '" <> field <> "' did not match the required format"]

De nuevo, date cuenta de cómo pure se usa para indicar una validación exitosa, e invalid se usa para señalar un array de errores.

validatePhoneNumber se construye sobre matches igual que antes:

1 validatePhoneNumber :: PhoneNumber -> V Errors PhoneNumber
2 validatePhoneNumber (PhoneNumber o) =
3   phoneNumber <$> pure o."type"
4               <*> (matches "Number" phoneNumberRegex o.number *> pure o.number)

De nuevo, intenta ejecutar este validador contra entradas válidas e inválidas en PSCi:

1 > validatePhoneNumber $ phoneNumber HomePhone "555-555-5555"
2 Valid (PhoneNumber { type: HomePhone, number: "555-555-5555" })
3 
4 > validatePhoneNumber $ phoneNumber HomePhone "555.555.5555"
5 Invalid (["Field 'Number' did not match the required format"])

Funtores transitables (traversable functors)

El validador restante es validatePerson, que combina los validadores que hemos visto hasta ahora para validar una estructura Person completa:

 1 arrayNonEmpty :: forall a. String -> Array a -> V Errors Unit
 2 arrayNonEmpty field [] =
 3   invalid ["Field '" <> field <> "' must contain at least one value"]
 4 arrayNonEmpty _     _  =
 5   pure unit
 6 
 7 validatePerson :: Person -> V Errors Person
 8 validatePerson (Person o) =
 9   person <$> (nonEmpty "First Name" o.firstName *>
10               pure o.firstName)
11          <*> (nonEmpty "Last Name"  o.lastName  *>
12               pure o.lastName)
13 	       <*> validateAddress o.address
14          <*> (arrayNonEmpty "Phone Numbers" o.phones *>
15               traverse validatePhoneNumber o.phones)

Hay otra función interesante aquí que no hemos visto todavía: traverse, que aparece en la última línea.

traverse se define en el módulo Data.Traversable en la clase de tipos Traversable:

1 class (Functor t, Foldable t) <= Traversable t where
2   traverse :: forall a b f. Applicative f => (a -> f b) -> t a -> f (t b)
3   sequence :: forall a f. Applicative f => t (f a) -> f (t a)

Traversable define la clase de funtores transitables. Los tipos de sus funciones pueden resultar un poco intimidatorios, pero validatePerson proporciona un buen ejemplo del motivo.

Todo funtor transitable es a la vez un Functor y un Foldable (recuerda que un funtor plegable era un constructor de tipo que soportaba una operación de pliegue, reduciendo una estructura a un valor único). Además, un funtor transitable proporciona la capacidad de combinar una colección de efectos secundarios que dependen de su estructura.

Esto puede sonar complicado, pero simplifiquemos las cosas especializando para el caso de los arrays. El constructor de tipo array es transitable, lo que significa que hay una función:

1 traverse :: forall a b f. Applicative f => (a -> f b) -> Array a -> f (Array b)

De manera intuitiva, dado cualquier funtor aplicativo f y una función que toma un valor de tipo a y devuelve un valor de tipo b (con efectos secundarios registrados por f), podemos aplicar la función a cada elemento del array de tipo Array a para obtener un resultado de tipo Array b (con efectos secundarios registrados por f).

¿Todavía no está claro? Especialicemos todavía más al caso en que m es el funtor aplicativo V Errors de arriba. Ahora tenemos una función de tipo:

1 traverse :: forall a b. (a -> V Errors b) -> Array a -> V Errors (Array b)

Esta firma de tipo dice que si tenemos una función de validación f para un tipo a, entonces traverse f es una función de validación para arrays de tipo Array a. ¡Pero eso es exactamente lo que necesitamos para poder validar el campo phones de la estructura de datos Person! Podemos pasar validatePhoneNumber a traverse para crear una función de validación que valida cada elemento sucesivamente.

En general, traverse recorre los elementos de una estructura de datos, realizando cálculos con efectos secundarios y acumulando un resultado.

La firma de tipo para la otra función de Traversable, sequence, nos puede parecer más familiar:

1 sequence :: forall a f. Applicative f => t (f a) -> f (t a)

De hecho, la función combineList que escribimos antes es sólo un caso especial de la función sequence de la clase de tipos Traversable. Fijando t para que sea el constructor de tipo List, podemos recuperar el tipo de la función combineList:

1 combineList :: forall f a. Applicative f => List (f a) -> f (List a)

Los funtores transitables capturan la idea de recorrer una estructura de datos, recopilando un conjunto de cálculos con efectos, y combinando sus efectos. De hecho, sequence y traverse son igualmente importantes para la definición de Traversable; cada uno puede ser implementado a partir del otro. Esto se deja como un ejercicio para el lector interesado.

La instancia Traversable para listas está en el módulo Data.List. La definición de traverse es esta:

1 -- traverse :: forall a b f. Applicative f => (a -> f b) -> List a -> f (List b)
2 traverse _ Nil = pure Nil
3 traverse f (Cons x xs) = Cons <$> f x <*> traverse f xs

En el caso de una lista vacía podemos simplemente devolver una lista vacía usando pure. Si la lista no está vacía, podemos usar la función f para crear un cálculo de tipo f b a partir del elemento frontal. Podemos también llamar a traverse recursivamente sobre la cola. Finalmente, podemos elevar el constructor Cons sobre el funtor aplicativo f para combinar estos dos resultados.

Pero hay más ejemplos de funtores transitables aparte de arrays y listas. El constructor de tipo Maybe que vimos antes también tiene una instancia de Traversable. Podemos probarlo en PSCi:

 1 > import Data.Maybe
 2 > import Data.Traversable
 3 
 4 > traverse (nonEmpty "Example") Nothing
 5 (Valid Nothing)
 6 
 7 > traverse (nonEmpty "Example") (Just "")
 8 (Invalid ["Field 'Example' cannot be empty"])
 9 
10 > traverse (nonEmpty "Example") (Just "Testing")
11 (Valid (Just unit))

Estos ejemplos muestran que recorrer el valor Nothing devuelve Nothing sin validación, y recorrer Just x usa la función de validación para validar x. Esto es, traverse toma una función de validación para el tipo a y devuelve una función de validación para Maybe a, es decir, una función de validación para valores opcionales de tipo a.