Translate

Mostrando las entradas con la etiqueta Haskell. Mostrar todas las entradas
Mostrando las entradas con la etiqueta Haskell. Mostrar todas las entradas

viernes, 4 de octubre de 2024

Pattern Matching en TypeScript


Pattern Matching es una característica poderosa que permite comparar una estructura de datos con un patrón y ejecutar el código dependiendo de cómo coincidan. Aunque TypeScript no tiene un soporte nativo de pattern matching al estilo de lenguajes como Scala o Haskell, pero se puede simular de manera efectiva utilizando algunas características como los tipos discriminados y el refinamiento de tipos para implementar pattern matching. Estos tipos combinan un campo común discriminante que puede diferenciar uniones de tipos de forma segura.

Veamos un ejemplo:


type Shape = 

  | { kind: 'circle', radius: number }

  | { kind: 'square', sideLength: number }

  | { kind: 'rectangle', width: number, height: number };


function area(shape: Shape): number {

  switch (shape.kind) {

    case 'circle':

      return Math.PI * shape.radius ** 2;

    case 'square':

      return shape.sideLength ** 2;

    case 'rectangle':

      return shape.width * shape.height;

  }

}


const myCircle: Shape = { kind: 'circle', radius: 5 };

console.log(area(myCircle)); // 78.53981633974483


Otra forma de hacer pattern matching es mediante guard clauses, que son condiciones específicas para cada caso. Aquí tienes un ejemplo:


function printNumber(x: number | string): string {

  if (typeof x === 'number') {

    return `Es un número: ${x}`;

  } else if (typeof x === 'string') {

    return `Es una cadena de texto: ${x}`;

  } else {

    return `Valor no soportado`;

  }

}


// Uso

console.log(printNumber(42));   // Es un número: 42

console.log(printNumber('42')); // Es una cadena de texto: 42


TypeScript también permite un estilo de pattern matching mediante desestructuración de objetos y arrays.


type Person = { name: string, age: number };

type Animal = { species: string };


function describe(input: Person | Animal): string {

  if ('name' in input) {

    return `Persona: ${input.name}, Edad: ${input.age}`;

  } else {

    return `Especie: ${input.species}`;

  }

}


// Uso

const person: Person = { name: 'John', age: 30 };

const animal: Animal = { species: 'Dog' };


console.log(describe(person)); // Persona: John, Edad: 30

console.log(describe(animal)); // Especie: Dog


El uso de `switch` puede complementarse con guardias para realizar un matching más fino de patrones, filtrando por condiciones adicionales.


function classifyNumber(x: number): string {

  switch (true) {

    case x < 0:

      return 'Número negativo';

    case x === 0:

      return 'Cero';

    case x > 0:

      return 'Número positivo';

    default:

      return 'Valor desconocido';

  }

}


console.log(classifyNumber(-5));  // Número negativo

console.log(classifyNumber(0));   // Cero

console.log(classifyNumber(10));  // Número positivo


Si bien TypeScript no tiene soporte nativo para el pattern matching al nivel de otros lenguajes funcionales, podemos simularlo utilizando sus características de refinamiento de tipos, tipos discriminados, guard clauses y desestructuración.

Con estos enfoques, puedes aplicar las ideas de pattern matching de forma clara y eficiente en TypeScript. Este tipo de técnica puede mejorar la legibilidad de tu código y hacerlo más fácil de mantener.


jueves, 11 de julio de 2024

Como podemos manejar las referencias nulas?


El error más frecuente en Java es NullPointerException y me imagino que en otros lenguajes alguno similar...  Para abordar esto, se han introducido estructuras y operadores que ayudan a manejar la ausencia de valores de manera más segura y explícita. 

Por ejemplo en Java se introdujo la clase `Optional` en la versión 8 para manejar valores potencialmente nulos de una manera más segura. `Optional` es un contenedor que puede o no contener un valor no nulo.

import java.util.Optional;


public class OptionalExample {

    public static void main(String[] args) {

        Optional<String> optional = Optional.of("Hello, World!");

        

        // Verificar si hay un valor presente

        if (optional.isPresent()) {

            System.out.println(optional.get());

        }

        

        // Uso del método ifPresent

        optional.ifPresent(System.out::println);

        

        // Proveer un valor predeterminado

        String value = optional.orElse("Default Value");

        System.out.println(value);

        

        // Proveer un valor predeterminado usando un Supplier

        value = optional.orElseGet(() -> "Default Value from Supplier");

        System.out.println(value);

    }

}


Scala utiliza la clase `Option` para representar un valor opcional. `Option` tiene dos subclases: `Some` y `None`, lo que proporciona una forma elegante y funcional de manejar valores que pueden estar ausentes. Esta idea es similar a la monada `Maybe` en Haskell.


object OptionExample extends App {

  val someValue: Option[String] = Some("Hello, World!")

  val noneValue: Option[String] = None


  // Uso de getOrElse

  println(someValue.getOrElse("Default Value"))

  println(noneValue.getOrElse("Default Value"))


  // Uso del patrón de coincidencia (Pattern Matching)

  someValue match {

    case Some(value) => println(value)

    case None => println("No value")

  }


  noneValue match {

    case Some(value) => println(value)

    case None => println("No value")

  }

}


Scala "copio" esta forma de Haskell. Haskell utiliza el tipo de datos `Maybe` para manejar valores opcionales `Maybe` puede ser `Just` un valor o `Nothing`.


main :: IO ()

main = do

    let someValue = Just "Hello, World!"

    let noneValue = Nothing


    -- Uso de fromMaybe

    putStrLn (fromMaybe "Default Value" someValue)

    putStrLn (fromMaybe "Default Value" noneValue)


    -- Uso del patrón de coincidencia (Pattern Matching)

    case someValue of

        Just value -> putStrLn value

        Nothing -> putStrLn "No value"


    case noneValue of

        Just value -> putStrLn value

        Nothing -> putStrLn "No value"


Kotlin es similar a Scala en muchos aspectos pero no en este. Kotlin introduce el operador `?` para facilitar la gestión de valores nulos. Este operador se utiliza para declarar tipos de datos que pueden ser nulos y para realizar operaciones seguras contra nulos.


fun main() {

    var nullableString: String? = "Hello, World!"


    // Uso del operador ?. para llamadas seguras

    println(nullableString?.length)


    // Uso del operador ?: para proporcionar un valor predeterminado

    val length = nullableString?.length ?: 0

    println(length)


    nullableString = null


    // Uso de let para ejecutar código solo si el valor no es nulo

    nullableString?.let {

        println(it)

    }

}


C# ha incluido varias características para manejar valores nulos, como el operador `?`, que facilita el manejo seguro de tipos que pueden ser nulos.


using System;


class Program

{

    static void Main()

    {

        string? nullableString = "Hello, World!";

        

        // Uso del operador ?. para llamadas seguras

        Console.WriteLine(nullableString?.Length);


        // Uso del operador ?? para proporcionar un valor predeterminado

        int length = nullableString?.Length ?? 0;

        Console.WriteLine(length);


        nullableString = null;


        // Uso de pattern matching para verificar nulos

        if (nullableString is string nonNullString)

        {

            Console.WriteLine(nonNullString);

        }

    }

}


Rust maneja la ausencia de valores y los errores de una manera robusta utilizando los tipos `Option` y `Result`. `Option` puede ser `Some` o `None`, mientras que `Result` puede ser `Ok` o `Err`.


fn main() {

    let some_value: Option<String> = Some("Hello, World!".to_string());

    let none_value: Option<String> = None;


    // Uso de unwrap_or

    println!("{}", some_value.unwrap_or("Default Value".to_string()));

    println!("{}", none_value.unwrap_or("Default Value".to_string()));


    // Uso del patrón de coincidencia (Pattern Matching)

    match some_value {

        Some(value) => println!("{}", value),

        None => println!("No value"),

    }


    match none_value {

        Some(value) => println!("{}", value),

        None => println!("No value"),

    }

}


Go no tiene un tipo de datos específico para manejar valores opcionales, pero utiliza la convención de retornar múltiples valores, incluyendo un valor y un `error`. Que la verdad no me gusta, te pasas preguntando todo el tiempo si hay error o si los valores son nulos. 


package main


import (

    "errors"

    "fmt"

)


func getValue() (string, error) {

    return "Hello, World!", nil

}


func getNullableValue() (string, error) {

    return "", errors.New("no value")

}


func main() {

    value, err := getValue()

    if err != nil {

        fmt.Println("Error:", err)

    } else {

        fmt.Println("Value:", value)

    }


    nullableValue, err := getNullableValue()

    if err != nil {

        fmt.Println("Error:", err)

    } else {

        fmt.Println("Value:", nullableValue)

    }

}


Python utiliza la palabra clave `None` para representar la ausencia de valor. Aunque no tiene una estructura específica como `Optional`, los desarrolladores pueden utilizar condicionales y manejo de excepciones.


def get_value():

    return "Hello, World!"


def get_nullable_value():

    return None


value = get_value()

nullable_value = get_nullable_value()


if value is not None:

    print(value)

else:

    print("Default Value")


if nullable_value is not None:

    print(nullable_value)

else:

    print("Default Value")


Ruby utiliza `nil` para representar la ausencia de valor. Al igual que en Python, no tiene una estructura específica para valores opcionales, pero proporciona métodos para manejar `nil`.


value = "Hello, World!"

nullable_value = nil


# Uso del operador ||

puts value || "Default Value"

puts nullable_value || "Default Value"


# Uso de condicionales

puts value.nil? ? "Default Value" : value

puts nullable_value.nil? ? "Default Value" : nullable_value


C++ utiliza punteros inteligentes (`smart pointers`) para gestionar la memoria y prevenir errores relacionados con punteros nulos. Los punteros inteligentes, como `std::unique_ptr` y `std::shared_ptr`, se encargan de la gestión automática de la memoria.


#include <iostream>

#include <memory>


int main() {

    std::unique_ptr<int> uniquePtr(new int(42));

    if (uniquePtr) {

        std::cout << *uniquePtr << std::endl;

    }


    std::shared_ptr<int> sharedPtr = std::make_shared<int>(42);

    if (sharedPtr) {

        std::cout << *sharedPtr << std::endl;

    }


    // Uso de weak_ptr para evitar ciclos de referencia

    std::weak_ptr<int> weakPtr = sharedPtr;

    if (auto lockedPtr = weakPtr.lock()) {

        std::cout << *lockedPtr << std::endl;

    }


    return 0;

}


TypeScript, un superconjunto de JavaScript, permite tipos opcionales y tiene un soporte robusto para manejar valores `null` y `undefined`.


let nullableString: string | null = "Hello, World!";


// Uso del operador ? para llamadas seguras

console.log(nullableString?.length ?? 0);


// Uso de if para asegurar valores no nulos

if (nullableString !== null) {

    console.log(nullableString);

}


TypeScript utiliza tipos opcionales para manejar valores que pueden ser `null` o `undefined`, proporcionando un enfoque seguro para evitar errores comunes relacionados con valores nulos. El operador `?.` permite realizar llamadas seguras, y el operador `??` proporciona valores predeterminados en caso de valores `null` o `undefined`.

En fin, aunque la gestión de valores nulos varía entre lenguajes, la idea subyacente es la misma: proporcionar mecanismos más seguros y expresivos para manejar la ausencia de valores. Ya sea mediante clases contenedoras como `Optional` en Java y `Option` en Scala, tipos de datos como `Maybe` en Haskell, operadores específicos como `?` en Kotlin y C#, punteros inteligentes en C++, o enfoques específicos en Rust, Go, Python y Ruby, estos enfoques ayudan a reducir los errores y a escribir un código más robusto y mantenible.


jueves, 9 de mayo de 2024

Que es un Higher-Kinded Type de Scala?


En Scala, un Higher-Kinded Type (HKT) es un tipo parametrizado que en sí mismo toma otro tipo parametrizado. Esto permite a los tipos ser abstractos sobre otros tipos parametrizados, lo que proporciona una mayor flexibilidad y abstracción en el diseño de bibliotecas y abstracciones de programación.

Para entender mejor qué es un HKT, es útil revisar algunos conceptos básicos:

Tipo parametrizado: En Scala, un tipo parametrizado es un tipo que toma uno o más parámetros de tipo. Por ejemplo, List[A] es un tipo parametrizado que toma un parámetro de tipo A.

Tipo de orden superior (Higher-Order Type): Un tipo de orden superior es un tipo que acepta otros tipos como parámetros. Por ejemplo, en el contexto de las funciones, una función de orden superior es una función que toma otra función como argumento.

Higher-Kinded Type (HKT): Un HKT es un tipo parametrizado que en sí mismo toma otro tipo parametrizado. En Scala, se denota utilizando el operador [_] o [*]. Por ejemplo, Option[_] o F[_] son HKTs, ya que pueden tomar tipos parametrizados como Option[Int] o Option[String].

Los HKTs son útiles en el contexto de la programación funcional y el diseño de bibliotecas genéricas. Permiten escribir código genérico que puede trabajar con diferentes tipos de datos sin conocer los detalles específicos de esos tipos. Por ejemplo, muchas bibliotecas de efectos en Scala, como Cats o Scalaz, utilizan HKTs para proporcionar abstracciones sobre diferentes tipos de efectos o contenedores de datos. Esto permite a los desarrolladores escribir código genérico que puede manipular efectos de diferentes tipos sin necesidad de modificar el código para cada tipo específico.

Vamos a crear una abstracción genérica para trabajar con contenedores de datos, independientemente de su tipo específico:


// Definición de un Higher-Kinded Type (HKT) F[_]

trait Container[F[_]] {

  def put[A](value: A): F[A]

  def get[A](container: F[A]): A

}


// Implementación de Container para List

object ListContainer extends Container[List] {

  def put[A](value: A): List[A] = List(value)

  def get[A](container: List[A]): A = container.head

}


// Implementación de Container para Option

object OptionContainer extends Container[Option] {

  def put[A](value: A): Option[A] = Some(value)

  def get[A](container: Option[A]): A = container.getOrElse(throw new NoSuchElementException("Empty container"))

}


object Main {

  def main(args: Array[String]): Unit = {

    // Uso de ListContainer

    val list = ListContainer.put(42)

    println("Value in list: " + ListContainer.get(list)) // Imprime: Value in list: 42

    

    // Uso de OptionContainer

    val option = OptionContainer.put(42)

    println("Value in option: " + OptionContainer.get(option)) // Imprime: Value in option: 42

  }

}

En este ejemplo, Container[F[_]] es un HKT que representa un contenedor genérico. La interfaz Container define métodos put y get que permiten poner y obtener valores de un contenedor F de tipo F[_]. Luego, proporcionamos implementaciones específicas de Container para diferentes tipos de contenedores: List y Option.

Esta abstracción nos permite escribir código genérico que funciona con cualquier tipo de contenedor, sin necesidad de conocer los detalles internos de cada uno. Por ejemplo, podemos utilizar ListContainer para trabajar con listas y OptionContainer para trabajar con opciones, todo usando la misma interfaz genérica Container. Esto proporciona una gran flexibilidad y reutilización de código en nuestras aplicaciones.

En Haskell, el concepto de Higher-Kinded Type (HKT) se manifiesta a través de los tipos de datos parametrizados que también son constructores de tipos. Esto permite definir abstracciones genéricas que pueden trabajar con diferentes tipos de datos sin conocer los detalles específicos de esos tipos.

Supongamos que queremos definir una abstracción genérica para trabajar con estructuras de datos que actúan como contenedores. Podemos utilizar un tipo de dato parametrizado f, donde f es un tipo de constructor de tipo, para representar nuestro contenedor genérico. Luego, definimos funciones genéricas que operan en este contenedor:


haskell

Copy code

-- Definición de un tipo de dato parametrizado f

class Container f where

  put :: a -> f a

  get :: f a -> a


-- Implementación de Container para List

instance Container [] where

  put x = [x]

  get (x:_) = x

  get _     = error "Empty list"


-- Implementación de Container para Maybe

instance Container Maybe where

  put = Just

  get (Just x) = x

  get Nothing  = error "Nothing"


-- Ejemplo de uso

main :: IO ()

main = do

  let list = put 42 :: [Int]

  putStrLn $ "Value in list: " ++ show (get list) -- Imprime: Value in list: 42

  

  let maybeVal = put 42 :: Maybe Int

  putStrLn $ "Value in Maybe: " ++ show (get maybeVal) -- Imprime: Value in Maybe: 42

En este ejemplo, Container es una clase de tipo que representa nuestra abstracción genérica para contenedores. La función put toma un valor y lo coloca en el contenedor, mientras que get extrae un valor del contenedor. Luego, proporcionamos instancias de Container para tipos específicos de contenedores como [] (lista) y Maybe.

Usando esta abstracción, podemos escribir código genérico que funciona con cualquier tipo de contenedor sin preocuparnos por los detalles internos de cada uno. Esto proporciona una gran flexibilidad y reutilización de código en nuestras aplicaciones Haskell.

jueves, 10 de febrero de 2022

Type class en Scala


Type class es un patrón de programación que se origina en Haskell. Nos permiten ampliar las bibliotecas existentes con nuevas funciones, sin utilizar la herencia tradicional y sin alterar el código fuente de la biblioteca original.

Type class es una especie de interfaz que define algún tipo de comportamiento. Si un tipo es miembro de una clase de tipos, significa que ese tipo soporta e implementa el comportamiento que define la clase de tipos. La gente que viene de lenguajes orientados a objetos es propensa a confundir las clases de tipos porque piensan que son como las clases en los lenguajes orientados a objetos. Bien, pues no lo son. Una aproximación más adecuada sería pensar que son como las interfaces de Java, o los protocolos de Objective-C, pero mejor.

Veamos un ejemplo: 

ghci> :t (==)

(==) :: (Eq a) => a -> a -> Bool

Interesante. Aquí vemos algo nuevo, el símbolo =>. Cualquier cosa antes del símbolo => es una restricción de clase. Podemos leer la declaración de tipo anterior como: la función de igualdad toma dos parámetros que son del mismo tipo y devuelve un Bool. El tipo de estos dos parámetros debe ser miembro de la clase Eq (esto es la restricción de clase).

El tipo de clase Eq proporciona una interfaz para las comparaciones de igualdad. Cualquier tipo que tenga sentido comparar dos valores de ese tipo por igualdad debe ser miembro de la clase Eq. Todos los tipos estándar de Haskell excepto el tipo IO (un tipo para manejar la entrada/salida) y las funciones forman parte de la clase Eq.

Hay tres componentes importantes para implementar este patrón en Scala. Type class en Scala se implementan usando valores y parámetros implícitos y, opcionalmente, usando clases implícitas. Las construcciones del lenguaje Scala corresponden a los componentes de los type class de la siguiente manera:

  • traits: type classes;
  • implicit values: instancia del type class;
  • implicit parameters: donde se usa el type class use
  • implicit classes: es opcional, y facilita el uso de type class
Veamos estos puntos en más detalle : 

traits : Una clase de tipo es una interfaz o API que representa alguna funcionalidad que queremos implementar. En Scala, una clase de tipo está representada por un rasgo o traits con al menos un parámetro de tipo. Por ejemplo, podemos representar el comportamiento genérico de "serializar a JSON" de la siguiente manera:

// Define a very simple JSON AST
sealed trait Json
  final case class JsObject(get: Map[String, Json]) extends Json
  final case class JsString(get: String) extends Json
  final case class JsNumber(get: Double) extends Json
  final case object JsNull extends Json

// The "serialize to JSON" behaviour is encoded in this trait
trait JsonWriter[A] {
  def write(value: A): Json
}

JsonWriter es nuestra clase de tipo en este ejemplo, con Json y sus subtipos proporcionando código de soporte. Cuando lleguemos a implementar instancias de JsonWriter, el parámetro de tipo A será el tipo concreto de datos que estamos escribiendo.

Las instancias de una clase de tipo proporcionan implementaciones de la clase de tipo para tipos específicos que nos interesan, que pueden incluir tipos de la biblioteca estándar de Scala y tipos de nuestro modelo de dominio.

En Scala, definimos instancias creando implementaciones concretas de la clase de tipo y etiquetándolas con la palabra clave implícita:

final case class Person(name: String, email: String)
  object JsonWriterInstances {
    implicit val stringWriter: JsonWriter[String] =
      new JsonWriter[String] {
        def write(value: String): Json =
          JsString(value)
      }

implicit val personWriter: JsonWriter[Person] =
  new JsonWriter[Person] {
    def write(value: Person): Json =
      JsObject(Map(
        "name" -> JsString(value.name),
        "email" -> JsString(value.email)
      ))
  }

//etc 
}

Puff me quedo relargo el post, seguimos con implicit parameters y implicit classes en el próximo post. 

jueves, 3 de diciembre de 2020

Functional Programming in Haskell: Supercharge Your Coding


Los que siguen el blog, notaron varios post de haskell medio seguidos, todo esto es gracias a un curso de futurelearn que les quiero recomendar, el nombre es : Functional Programming in Haskell: Supercharge Your Coding. 

Es gratuito y esta realizado por la universidad de Glasgow. 

Entre los capitulos tenemos, teoría, entrevistas, casos prácticos, etc... 

Dejo link: https://www.futurelearn.com/courses/functional-programming-haskell

sábado, 14 de noviembre de 2020

Maybe


Veamos la mónada Maybe, que facilita mucho el uso del tipo Maybe.

Ya conoces la definición del tipo Maybe:

    data Maybe a = Just a | Nothing

Las funciones de Head y Tail de Prelude no son seguras en el sentido de que fallan cuando se llaman en una lista vacía. Podemos definir versiones seguras usando Maybe:


    myHead :: [a] -> Maybe a

    myHead [] = Nothing

    myHead (x:xs) = Just x


    myTail :: [a] -> Maybe []

    myTail [] = Nothing

    myTail (x:xs) = Just xs


Ahora podemos hacer de Maybe una instancia de la clase de tipo Monad, simplemente proporcionando las definiciones apropiadas para return, bind, then y fail:


    import Control.Monad


    instance Monad Maybe where

        return           =   Just

        Nothing  >>= f = Nothing

        (Just x) >>= f = f x

        fail _           =   Nothing


Hay algunas funciones adicionales definidas en la clase de tipo MonadPlus:


    instance MonadPlus Maybe where

        mzero               = Nothing

        Nothing `mplus` x = x

        x `mplus` _         = x


Eso es todo, ¡ahora tenemos una mónada Maybe!

Veamos qué nos da esta mónada:

Un cálculo usando Maybe explícito

    foo :: [a] -> Maybe a

    foo xs =

      case myTail xs of

        Nothing -> Nothing

        Just a -> case myTail a of

                    Nothing -> Nothing

                    Just b -> myHead b

Para combinar cálculos que usan el tipo Maybe, necesitamos expresiones de caso explícitas para hacer coincidir el patrón con el tipo.

Escribamos este cálculo usando la mónada Maybe, primero usando el operador >> =:


    bar :: [a] -> Maybe a

    bar xs =

      myTail xs >>=

        (\a -> myTail a >>=

          (\b -> myHead b))


Ahora cambiemos un poco los saltos de línea y la sangría para que se vea mejor:


    bar2 :: [a] -> Maybe a

    bar2 xs =

      myTail xs >>= (\a ->

      myTail a >>=  (\b ->

      myHead b))


Gracias a la ley de asociatividad, también podemos eliminar los paréntesis innecesarios:


    bar3 :: [a] -> Maybe a

    bar3 xs =

      myTail xs >>= \a ->

      myTail a >>=  \b ->

      myHead b


Esto ya es mucho más limpio, pero finalmente podemos usar la notación do:


    bar3 :: [a] -> Maybe a

    bar3 xs = do

      a <- myTail xs

      b <- myTail a

      myHead b


Claramente, el código monádico final es mucho más legible que el código no monádico original.


Ejemplo: Reducción de barra [5,6]

        bar [5,6]

    -- > substitute [5,6] for xs in definition of bar

        myTail [5,6] >>=

         (\a -> myTail a >>=

          (\b -> myHead b))

    -- > def. myTail

        Just [6]  >>=

         (\a -> myTail a >>=

          (\b -> myHead b))

    -- >  def.2 of (>>=)

         (\a -> myTail a >>=

          (\b -> myHead b))

            [6]

    -- > beta reduction, substitute [6] for a

         myTail [6] >>= (\b -> myHead b)

    -- > reduce myTail

         Just [] >>=  (\b -> myHead b)

    -- >  def.2 of (>>=)   

        (\b -> myHead b) []

    -- > beta reduction, substitute [] for b

       myHead []

    -- > def.1 myHead

      Nothing


Ejemplo: Reducción de barra [5,6,7]

        bar [5,6,7]

    -> sustituir [5,6,7] por xs en la definición de bar

        bar [5,6,7]

    -- > substitute [5,6,7] for xs in definition of bar

        myTail [5,6,7] >>=

         (\a -> myTail a >>=

          (\b -> myHead b))

    -- > def. myTail

        Just [6,7]  >>=

         (\a -> myTail a >>=

          (\b -> myHead b))

    -- >  def.2 of (>>=)

         (\a -> myTail a >>=

          (\b -> myHead b))

            [6,7]

    -- > beta reduction, substitute [6,7] for a

         myTail [6,7] >>= (\b -> myHead b)

    -- > reduce myTail

         Just [7] >>=  (\b -> myHead b)

    -- >  def.2 of (>>=)   

        (\b -> myHead b) [7]

    -- > beta reduction, substitute [7] for b

        myHead [7]

    -- > def myHead

        Just 7

domingo, 8 de noviembre de 2020

¿Qué es una mónada?


Rápidamente nos podemos percatar de la importancia de los acentos! 

Una mónada es una estructura algebraica en la teoría de categorías, y en Haskell se usa para describir cálculos como secuencias de pasos y para manejar efectos secundarios como estado de entrada o salida.

Las mónadas son abstractas y tienen muchos ejemplos concretos útiles.

Las mónadas proporcionan una forma de estructurar un programa.

Se pueden usar (junto con tipos de datos abstractos) para permitir que las acciones (por ejemplo, variables mutables) se implementen de forma segura.

Una mónada tiene tres bloques de construcción:

  • Un constructor de tipos que produce el tipo de cálculo, dado el tipo de resultado de ese cálculo.
  • Una función que toma un valor y devuelve un cálculo que, cuando se ejecuta, producirá ese valor.
  • Una función que toma dos cálculos y los realiza uno tras otro, haciendo que el resultado del primer cálculo esté disponible para el segundo.

Una mónada consta de tres objetos, que deben satisfacer las leyes de la mónada. Veamos primero los objetos:

Un constructor de tipo M, tal que para cualquier tipo a, el tipo M a es el tipo de cálculo en la mónada M que produce un resultado de tipo a.

Una función return :: a → M a. Por lo tanto, si x :: a, return x es un cálculo en M que, cuando se ejecuta, producirá un valor de tipo a.

Una función (>> =) :: M a → (a → M b) → M b.

El primer argumento es un cálculo que produce un valor de tipo a.

El segundo argumento es una función que requiere un argumento de tipo a y devuelve un cálculo que produce un valor de tipo b.

Las leyes de las mónadas es un cálculo que producirá un valor de tipo b. Funciona ejecutando el primer cálculo y pasando su resultado a la función que devuelve el segundo cálculo, que luego se ejecuta.

Las mónadas son abstractas, generales y útiles.

En consecuencia, hay muchos casos de ellos.

Esto se captura mediante la definición de una clase de tipo para las mónadas, junto con muchas instancias estándar.

    class Monad m where

        return :: a -> m a

        (>>=) :: m a -> (a -> m b) -> m b

        (>>)   :: m a -> m b -> m b

        fail   :: String -> m a


La función de retorno toma un valor y devuelve un valor monádico, es decir, un valor envuelto en el constructor de tipo monada.

El operador >> = (pronunciado "bind") es una parte crucial de una mónada. Vincula un valor devuelto de un cálculo a otro cálculo.

El operador >> (pronunciado "then") es como >> =, pero simplemente ignora el valor devuelto por el cálculo:

    m >> n = m >> = \ _ -> n

El sistema utiliza la función de error para ayudar a producir mensajes de error cuando hay un patrón que no coincide; normalmente no lo usa directamente.

Cada mónada debe satisfacer las siguientes tres leyes. Entonces, si algo parece una mónada pero no satisface estas leyes, ¡no es una mónada! Las leyes expresan propiedades que deben satisfacerse para hacer componibles los cálculos monádicos.

La ley de unidad correcta:

    m >> = retorno = m

La ley de la unidad izquierda:

    devuelve x >> = f = f x

La ley de asociatividad:

    (m >> = f) >> = g = m >> = (\ x -> f x >> = g)

Hay muchas metáforas o intuiciones sobre lo que es una mónada.

Ejemplo: un "cálculo" o una "acción". Pero estos términos son vagos: pueden ayudarlo a comprender, pero a veces también pueden ser engañosos.

Una mónada es exactamente lo que dice la definición, ni más ni menos.

Escribir cálculos monádicos usando los operadores bind y then sigue siendo algo torpe. Haskell proporciona un azúcar sintáctico muy conveniente para cálculos monádicos llamado "notación do":

    baz :: [a] -> Maybe a

    baz xs =

      do  a <- myTail xs

          b <- myTail a

          c <- myHead b

          return c


Reglas de sintaxis para hacer

    do { x }  -- >  x

    do {x ; <xs> }  -- >  x >> do { <xs> }

    do { a <- x ; <xs> }  -- >  x >>= \a -> do { <xs> }

    do { let <declarations> ; xs }    -- >   let <declarations> in do { xs }

sábado, 7 de noviembre de 2020

En un lenguaje funcional, solo hay funciones

Aunque parezca que un lenguaje como Haskell tiene muchos objetos y construcciones diferentes, podemos expresarlos todos en términos de funciones. 

  let

      n = 10

      f x = x+1

    in

      f n


-- Una variable por let =>


    let

      n = 10

    in

      let  

        f x = x+1

      in

        f n


-- Reescribe f como lambda  =>

        

    let

      n = 10

    in

      let  

        f = \x -> x+1

      in

        f n


-- Reescribe el let interno como lambda =>


    let

      n = 10

    in

      (\f -> f n) (\x -> x+1)  


-- Reescribe el let externo como lambda =>


    ( \n -> ((\f -> f n) ( \x -> x+1 )) ) 10    


Entonces, las variables y las expresiones let son solo azúcar sintáctico para las expresiones lambda.

    tp = (1,"2",[3])

La notación de tupla es azúcar sintáctica para una aplicación de función:

    tp = mkTup 1 "2" [3]

La función de construcción de tuplas se puede definir de nuevo simplemente usando lambdas:

   mkTup = \x y z -> \t -> t x y z

Lo mismo ocurre con las funciones de acceso a la tupla:

    fst tp = tp (\x y z -> x)

    snd tp = tp (\x y z -> y)

Las listas se pueden definir en términos de listas vacías [] y la operación de contras (:).

    ls = [1,2,3]

Se puede escribir con : y [] =>

    ls = 1 : 2 : 3 : []

O usando cons =>

 ls = cons 1 (cons 2 (cons 3 []))

Podemos definir cons usando solo funciones lambda como

  cons = \x xs ->

   \c -> c x xs

Así

    ls = cons 1 (...)

       = \c -> c 1 (...)

También podemos definir head y tail usando solo lambdas:

    head ls = ls (\x y -> x)

    tail ls = ls (\x y -> y)

 

Podemos definir la lista vacía de la siguiente manera:

 [] = \f -> true

Las definiciones de verdadero y falso se dan a continuación bajo Booleanos.

Luego podemos verificar si una lista está vacía o no:

    isEmpty lst = lst (\x xs -> false)

Una lista no vacía siempre se define como: 

lst = x: xs

que con nuestra definición de (:) es

    lst = (\x xs -> \c -> c x xs) x xs

    = \c -> c x xs

Así que :

isEmpty lst
    = isEmpty (\c -> c x xs)
    =  (\c -> c x xs) (\x xs -> false)
    = false

    isEmpty []
    = isEmpty (\f -> true)
    = (\f->true) (\x xs -> false)
    = true

Ahora que podemos probar la lista vacía, podemos definir recursiones en listas como foldl, map, etc.

    foldl f acc lst =
      if isEmpty lst
        then acc
        else foldl f (f (head lst) acc) (tail lst)

y

    map f lst  =
      let
        map' f lst lst' = if isEmpty lst then (reverse lst') else map' f (tail lst) (head lst: lst')
      in
        map' f lst []

con

   reverse lst = (foldl (\acc elt -> (elt:acc)) [] lst

Las definiciones de foldl y map usan una expresión if-then-else que se define a posteriormente en condicionales.

 Concatenación de lista :   (++) lst1 lst2 = foldl (\acc elt -> (elt:acc)) lst2 (reverse lst1)

Para calcular la longitud de una lista necesitamos números enteros, se definen a continuación.

    length lst = foldl calc_length 0 lst
      where
        calc_length _ len = inc len

Hemos utilizado condicionales en las expresiones anteriores:

    if cond then if_true_exp else if_false_exp

Aquí cond es una expresión que devuelve verdadero o falso, que se definen a continuación.

Podemos escribir la cláusula if-then-else como una función pura:

    ifthenelse cond if_true_exp if_false_exp

Para evaluar la condición necesitamos definir booleanos:

    true = \x y -> x
    false = \x y -> y


Con esta definición, el if-then-else se convierte simplemente

    ifthenelse cond if_true_exp if_false_exp = cond if_true_exp if_false_exp

Usando ifthenelse podemos definir y, o y no:

    and x y = ifthenelse x (ifthenelse y true) false
    or x y = ifthenelse x true (ifthenelse y true false)
    not x = ifthenelse x false true

Observamos que para probar la igualdad de los booleanos podemos usar xnor y, por supuesto, podemos definir xor en términos de y, o y no:

    xor x y = (x or y) and (not x or not y)
    xnor x y = not (xor x y)

Enteros firmados
Definimos un entero como una lista de valores booleanos, en codificación de termómetro, y con las siguientes definiciones:

Definimos usigned 0 como una lista de 1 elemento que contiene false. Para obtener enteros con signo, simplemente definimos el primer bit de la lista como el bit de signo. Definimos versiones firmadas y sin firmar de 0:

    u0 = false:[]
    0 = +0 = true:u0
    -0 = false:u0

Por conveniencia definimos también:

    isPos n = head n
    isNeg n = not (head n)
    isZero n = not (head (tail n))
    sign n = head n

La definición de 0 facilita la igualdad de enteros (==):

    (==) n1 n2 = let
      s1 = head n1
      s2 = head n2
      b1 = head (tail n1)
      b2 = head (tail n2)
      if (xnor s1 s2) then
        if (and (not b1) (not b2))
          then true
          else
            if (and b1 b2)
              then  (==) (s1:(tail n1)) (s2:(tail n2))
              else false
        else false


También podemos definir fácilmente la negación:

    neg n = (not (head n)):(tail n)

Por conveniencia definimos también definimos operaciones de incremento y decremento:

    inc n = if isPos n then true:true:(tail n) else if isZero n then 1 else false:(tail (tail n))
    dec n = if isZero n then -1 else if isNeg n then false:true:(tail n) n else true:(tail (tail n))

La adición general es bastante fácil:

    add n1 n2 = foldl add_if_true n1 n2
      where
        add_if_true elt n1 = if elt then true:n1 else n1

Del mismo modo, la resta también es sencilla:

    sub n1 n2 = foldl sub_if_true n1 n2
      where
        sub_if_true elt n1 = of elt then (tail n1) else n1

Una forma sencilla de definir la multiplicación es definiendo las operaciones de replicación y suma:

    replicate n m =
      let
        repl n m lst = if n==0 then lst else repl (dec n) m (m:lst)
      in
        repl n m []

    sum lst = foldl add 0 lst

Entonces la multiplicación simplemente se convierte en

    mult n m = sum (replicate n m)

De manera similar, se pueden definir la división y el módulo de enteros.

Observamos que los flotantes y los caracteres utilizan una representación de números enteros, y las cadenas son simplemente listas de caracteres. Entonces ahora tenemos un lenguaje que puede manipular listas y tuplas de enteros, flotantes, caracteres y cadenas.

lunes, 2 de noviembre de 2020

Tipos con Clase parte 5



Seguimos con type class

Veamos algunas de type class definidas en las bibliotecas estándar.

Num: números, con muchas subclases para tipos específicos de números.

Read: tipos que se pueden "leer desde" una cadena.

Show: tipos que se pueden "mostrar a" una cadena.

Eq: tipos para los que se define el operador de igualdad ==.

Ord: tipos para los que puede hacer comparaciones como <,>, etc.

Enum: tipos donde los valores se pueden enumerar en secuencia; esto se usa, por ejemplo, en la notación [1..n] y ′ a ′ .. ′ z ′.

    *Main> [1..10]

    [1,2,3,4,5,6,7,8,9,10]

    *Main> ['a'..'z']

    "abcdefghijklmnopqrstuvwxyz"

Tipos con Clase parte 4


Seguimos con Type class

Hemos estado usando show para convertir un valor de datos en una cadena, que luego se puede escribir en la salida.

Algunos valores se pueden "mostrar", pero no todos.

Por ejemplo, en general es imposible mostrar una función.

Por lo tanto, debemos usar type class

    show::Show a → a→String

Definición de su propia instancia de Show

    data Foo = Bar | Baz

Podríamos querer nuestra propia representación de cadena :

    instance Show Foo where

      show Bar = "it is a bar"

      show Baz = "this is a baz"


Recordemos que cuando ingresa una expresión exp en ghci, imprime showexp. Entonces podemos probar nuestra extraña declaración de instancia:

    *Main> Bar

    it is a bar

    *Main> Baz

    this is a baz


deriving nos permite indicar que "implementa" Show o otro data type : 

    data Foo2 = Bar2 | Baz2

      deriving (Read, Show)

Haskell definirá automáticamente una instancia de show para Foo2, usando la definición obvia:

    *Main> Bar2

    Bar2

    *Main> Baz2

    Baz2


domingo, 1 de noviembre de 2020

Tipos con Clase parte 3

 


Seguimos con type class

Haskell proporciona varias type class estándar. Echemos un vistazo a Num.

Num es la clase de tipos numéricos.

Aquí está (en parte) su declaración de clase:

    class Num a where

      (+), (-), (*) :: a -> a -> a

Hay muchos tipos numéricos; dos de ellos son Int y Double.

Hay funciones monomórficas primitivas que realizan operaciones aritméticas en estos tipos (estos no son los nombres reales):

addInt, subInt, mulInt :: Int -> Int -> Int

addDbl, subDbl, mulDbl :: Double -> Double -> Double


    instance Num Int where

      (+) = addInt

      (-) = subInt

      (*) = mulInt


    instance Num Double where

      (+) = addDbl

      (-) = subDbl

      (*) = mulDbl


Hay algunas operaciones (suma) que son válidas para todos los tipos numéricos. Hay algunos otros (por ejemplo, funciones trigonométricas) que son válidos solo para algunos tipos numéricos.

Por lo tanto, existe una rica jerarquía de subclases, que incluyen :

Integral: clase de tipos numéricos que representan valores enteros, incluidos Int, Integer y más.

Fraccional: clase de tipos que pueden representar fracciones.

Floating: clase que contiene Float, Double, etc.

Bounded: clase de tipos numéricos que tienen un elemento mínimo y máximo.

Bits: clase de tipos donde puede acceder a la representación como una secuencia de bits, útil para la programación de sistemas y el diseño de circuitos digitales.

Si deseamos profundizar en clases y tipos numéricos, podemos consultar la documentación de Haskell.


Tipos con Clase parte 2


Seguimos con type class

Un Type Class es un conjunto de tipos para los que se definen algunas operaciones.

Haskell tiene algunas Type Classes estándar que se definen en el Preludio estándar.Pero también podemos definir el tuyo propio.

Supongamos que estamos computando con colores. Aquí hay un tipo y un par de funciones.

    data Bright = Blu | Red

      deriving (Read, Show)


    darkBright :: Bright -> Bool

    darkBright Blue = True

    darkBright Red  = False


    lightenBright :: Bright -> Bright

    lightenBright Blue = Red

    lightenBright Red = Red


Ahora, suponga que tenemos un tipo diferente que necesita funciones similares.


    data Pastel  = Turquoise  | Tan

      deriving (Read, Show)


    darkPastel :: Pastel -> Bool

    darkPastel Turquoise = True

    darkPastel Tan       = False


    lightenPastel :: Pastel -> Pastel

    lightenPastel Turquoise = Tan

    lightenPastel Tan       = Tan


Ambos tipos de colores tienen funciones para decidir si es oscuro o claro.

Podemos definir una clase Color y sus funciones correspondientes.

    class Color a where

      dark :: a -> Bool

      lighten :: a -> a


Esto dice :

  • El color es una clase de tipo
  • La variable de tipo a representa un tipo particular que está en la clase Color
  • Para cualquier tipo a en Color, hay dos funciones que puede usar: oscuro y claro, con los tipos especificados.

Una declaración de instancia dice que un tipo es miembro de una clase de tipo.

Cuando declaras una instancia, necesitas definir las funciones de clase.

A continuación se indica que el tipo Bright está en la clase Color y, en ese caso, la función oscura es en realidad darkBright.

    instance Color Bright where

      dark = darkBright

      lighten = lightenBright


De manera similar, podemos declarar que Pastel está en Color, pero tiene diferentes funciones para implementar las operaciones de la clase.

    instance Color Pastel where

      dark = darkPastel

      lighten = lightenPastel



Tipos con Clase


Type class son una forma de sobrecargar funciones u operadores al imponer restricciones al polimorfismo.

Por ejemplo:

(+) :: a -> a -> a

no está bien porque queremos restringir la suma de números.

Igualmente,

     (<) :: a -> a -> Bool

no está bien porque no está claro a priori cómo comparar con tipos arbitrarios.

Para abordar este problema, Haskell proporciona Type class. Estos restringen el polimorfismo. Por ejemplo:

     (+) :: Num a => a -> a -> a

dice que el tipo a debe ser numérico, y

     (<) :: Ord a => a -> a -> Bool

dice que debe ser ordenable.

Y eso es todo! listo, pero pero puedo crear mi propio type class? Lucho, por supuesto viejo... pero lo vamos a ver en el próximo post. 



domingo, 25 de octubre de 2020

Introducción al cálculo Lambda


El cálculo lambda fue desarrollado en la década de 1930 por Alonzo Church (1903-1995), uno de los principales desarrolladores de lógica matemática. El cálculo lambda fue un intento de formalizar funciones como medio de computación.

Un avance importante (realmente el mayor) en la teoría de la computabilidad fue la prueba de que el cálculo lambda y la máquina de Turing tienen exactamente el mismo poder computacional. Esto llevó a la tesis de Church: que el conjunto de funciones que son efectivamente computables es exactamente el conjunto computable por la máquina de Turing o el cálculo lambda.

La tesis se fortaleció cuando varios otros sistemas de computación matemática (Problema posterior a la correspondencia y otros) también demostraron ser equivalentes al cálculo lambda.

El punto es que el conjunto de funciones efectivamente computables parece ser una realidad fundamental, no solo una peculiaridad de cómo se definió la {máquina de Turing, cálculo lambda}.

El cálculo lambda ha resultado capturar dos aspectos de una función:

  • Un objeto matemático (conjunto de pares ordenados de dominio y rango), y
  • Una máquina de caja negra abstracta que toma una entrada y produce una salida.

El cálculo lambda es fundamental para la semántica denotacional, la teoría matemática de lo que significan los programas de computadora.

Los lenguajes de programación funcional se desarrollaron con el objetivo explícito de convertir el cálculo lambda en un lenguaje de programación práctico.

El compilador ghc Haskell opera (1) desechando el programa fuente, (2) transformando el programa en una versión del cálculo lambda llamado Sistema F, y (3) traduciendo el Sistema F al lenguaje de máquina usando reducción de grafos.

Trabajaremos con el cálculo lambda básico “enriquecido” con algunas constantes y funciones primitivas (estrictamente hablando, eso no es necesario).

El lenguaje tiene constantes, variables, aplicaciones y funciones.

    exp = const

      | var

      | exp exp

      | \ var -> exp


Cada aparición de una variable en una expresión está ligada o es libre.

En ∖x → x + 1, la ocurrencia de x en x + 1 está limitada por ∖x.

En y ∗ 3, la ocurrencia o y es libre. Debe definirse en otro lugar, quizás como una definición global.

En general, una aparición de una variable está vinculada si hay alguna expresión lambda adjunta que la vincula; si no hay enlace lambda, entonces la ocurrencia es libre.

Debemos tener cuidado: la primera aparición de a es libre pero la segunda aparición está vinculada.

       a + (\ a -> 2 ^ a) 3 -> a + 2 ^ 3

Ser libre o vinculada es una propiedad de la ocurrencia de una variable, ¡no de la variable en sí!

La computación en el cálculo lambda se realiza utilizando tres reglas de conversión.

Las reglas de conversión le permiten reemplazar una expresión por otra ("igual").

Algunas conversiones simplifican una expresión; estos se llaman reducciones.

Conversión alfa : La conversión alfa le permite cambiar el nombre de un parámetro de función de manera consistente. ¡Pero no puede cambiar las variables libres con la conversión alfa!

La definición detallada de conversión alfa es un poco complicada, porque debe tener cuidado de ser coherente y evitar la "captura de nombres". No nos preocuparemos por los detalles en este momento.

(\ x -> x + 1) 3

(\ y -> y + 1) 3

Conversión beta : La conversión beta es el "caballo de batalla" del cálculo lambda: define cómo funcionan las funciones.

Para aplicar una expresión lambda a un argumento, se toma el cuerpo de la función y se reemplaza cada aparición enlazada de la variable con el argumento.

    (\ x -> exp1) exp2

se evalúa como exp1 [exp2 / x]

Ejemplo:

    (\ x -> 2 * x + g x) 42

se evalúa como 2 ∗ 42 + g 42

Conversión ETA : Eta conversión dice que una función es equivalente a una expresión lambda que toma un argumento y aplica la función al argumento.

(\ x -> f x)

es equivalente a f

Ejemplo (recuerde que (∗ 3) es una función que multiplica su argumento por 3)

(\ x -> (* 3) x)

es equivalente a (∗ 3)

Intente aplicar ambos a 50:

(\ x -> (* 3) x) 50

es lo mismo que (∗ 3) 50

Existe un uso común de la conversión Eta. Supongamos que tenemos una definición como esta:

f x y = g y

Esto se puede reescribir de la siguiente manera:

f = \ x -> (\ y -> g y)

f = \ x -> g = f x = g

Por tanto, las siguientes dos definiciones son equivalentes:

    f x y = g y

    f x = g

En efecto, dado que el último argumento en ambos lados de la ecuación es el mismo (y), se puede “factorizar”.

Y listo, no quiero profundizar en detalles matemáticos, pero sin duda que esta teoría influyo mucho el mundo de los lenguajes y quiero compartir una imagen que encontré y describe como ha llegado esta teoría al mainstream de los lenguajes y gracias a quienes :



lunes, 19 de octubre de 2020

QuickCheck: prueba automática programas Haskell


QuickCheck es una biblioteca para pruebas aleatorias de propiedades de programas. 

El programador proporciona una especificación del programa, en forma de propiedades que las funciones deben satisfacer, y QuickCheck luego prueba que las propiedades se cumplen en una gran cantidad de casos generados aleatoriamente. 

Las especificaciones se expresan en Haskell, utilizando combinadores proporcionados por QuickCheck. 

QuickCheck proporciona combinadores para definir propiedades, observar la distribución de los datos de prueba y definir generadores de datos de prueba.

veamos un ejemplo, primero definamos una propiedad : 


prop_RevRev xs = reverse (reverse xs) == xs 

where types = xs::[Int]


y luego a probar la propiedad 


Main> quickCheck prop_RevRev

OK, passed 100 tests.


Y si fallará nos mostraría todas las veces que fallo : 


Main> quickCheck prop_RevId

Falsifiable, after 1 tests:

[-3,15]


Y listo, tenemos una comprobación rapida y fácil para nuestros programas. 

Dejo link: http://www.cse.chalmers.se/~rjmh/QuickCheck/


domingo, 18 de octubre de 2020

Currying en Haskell


Si tenemos esta firma de función :

    f :: X -> Y -> Z -> A

La flecha "->" es asociativa a la derecha, por lo que es lo mismo que:

    f :: X -> (Y -> (Z -> A))

Lo que esto significa es que podemos considerar f como una función con un solo argumento de tipo X que devuelve una función de tipo Y-> Z-> A.

La técnica de reescribir una función de múltiples argumentos en una secuencia de funciones con un solo argumento se llama currización. Podemos ilustrar esto mejor usando una función lambda:

    \ x y z -> ...

    \ x -> (\ y z -> ...)

    \ x -> (\ y -> (\ z -> ...))


El nombre "curry", es una referencia al lógico Haskell Curry. El concepto en realidad fue propuesto originalmente por otro lógico, Moses Schönfinkel, pero su nombre no era tan pegadizo.

La aplicación parcial significa que no necesitamos proporcionar todos los argumentos a una función, para aplicar la función.  Por ejemplo, dado

     sq x y = x*x+y*y

Observamos que la aplicación de la función se asocia a la izquierda, por lo que se cumple la siguiente equivalencia


    sq x y = (sq x) y

Por tanto, podemos crear una función especializada mediante la aplicación parcial de x:

    sq4 = sq 4 -- = \y -> 16+y*y

    sq4 3 -- = (sq 4) 3 = sq 4 3 = 25

Es por eso que puedes escribir cosas como:

    dobles = mapa (* 2) [1 ..]

sábado, 17 de octubre de 2020

Estructuras de datos infinitas


En el post anterior, hablamos listas infinitas. Podemos definir una lista infinita de enteros consecutivos de la siguiente manera:

[1 ..]

Podemos evaluar esta lista, pero no se imprimirá en su totalidad. 

Debemos utilizar las funciones de take y drop para trabajar con listas infinitas. Esto permite realizar una cantidad finita de procesamiento en una lista infinita, pero no recorrerla infinitamente.

La razón por la que Haskell puede procesar listas infinitas es porque evalúa las listas de manera perezosa, es decir, solo evalúa los elementos de la lista cuando son necesarios.

Ahora echemos un vistazo a dos listas de enteros conocidas. Estudiaremos sus definiciones recursivas.

Números de Fibonacci : El n-ésimo número de Fibonacci es la suma de los dos números de Fibonacci anteriores. Los dos primeros números son ambos 1. Luego el tercero es 2, seguido de 3, 5, etc.

1, 1, 2, 3, 5, 8, 13, 21, ...

Esto se puede expresar en Haskell usando la función zipWith, combinando pares de elementos con el operador de suma.

let fibs = 1: 1: (zipWith (+) fibs (tail fibs))

Podemos evaluar elementos individuales de esta lista usando el !! y el indice. O podríamos tomar los primeros n elementos de la lista de fibs.

Números primos: A continuación se muestra una serie de expresiones de filtro para calcular una lista infinita de números primos.


properfactors :: Int -> [Int]

properfactors x = filter (\y->(x `mod` y == 0)) [2..(x-1)]


numproperfactors :: Int -> Int

numproperfactors x = length (properfactors x)


primes :: [Int]

primes = filter (\x-> (numproperfactors x == 0)) [2..]


La función de factores propios toma un valor entero x y devuelve una lista de factores propios para x. Los factores son números que dividen x y no dejan resto. Los factores adecuados para un número entero x no incluyen 1 ni x.

La función numproperfactors simplemente cuenta cuántos factores propios hay para x, devolviendo la longitud de la lista x de factores propios.

Finalmente, la lista de primos usa la función de filtro para seleccionar enteros x que no tienen factores en el rango de 2 a (x-1) inclusive.


Operando con listas en Haskell


Podemos indexar una lista numerando los elementos, comenzando con 0. Por tanto, una forma canónica de una lista con n elementos es [x0, x1, .. xn − 1].

El operador !! toma una lista y un índice y devuelve el elemento correspondiente.

[5,3,8,7] !! 2 -> 8

[0 .. 100] !! 81 -> 81

['a' .. 'z'] !! 13 -> 'n'

Si el índice es negativo o demasiado grande, se devuelve undefined.

Para una programación robusta, debemos asegurarnos de que todas las expresiones estén bien definidas o de que todas las excepciones sean capturadas y manejadas.

Hay funciones de biblioteca estándar para obtener primer elemento (head) o todo el resto de la lista (tail).

El resultado de aplicar head o tail a la lista vacía es indefinido

head :: [a] -> a

head [4,5,6] -> 4

tail :: [a] -> [a]

tail [4,5,6] -> [5,6]

Como recomendación: debemos evitar usar (head) y (tail), para evitar valores indefinidos. Se puede utilizar pattern matching que es más robusto.

Las listas en haskell son perezosas, hemos mencionado antes que Haskell es "perezoso", lo que significa que solo evalúa expresiones cuando son requeridas para la evaluación de otra expresión. Este comportamiento se extiende a listas, por lo que podemos definir listas infinitas usando secuencias, por ejemplo [1 .. ] es la lista de todos los enteros positivos. Otro ejemplo es la función primes (del paquete Data.Numbers.Primes) que devuelve una lista infinita de números primos. Una consecuencia de la pereza en las listas es que puede definir listas que contengan expresiones muy complejas y que consuman mucho tiempo, y siempre que nunca acceda a ellas, no se evaluarán. Lo mismo es cierto para una expresión incorrecta, por ejemplo, definir xs = [1,2, xs !! 5,4] no generará un error siempre que no acceda al tercer elemento.

Las listas también son inmutables. Como resultado, si definimos xs2 = xs ++ xs e intenta acceder al tercer elemento xs2 !! 2 seguirá dando como resultado un error porque xs no se ha modificado.

Curiosamente, si cambiamos la definición de xs a xs = [1,2, xs2 !! 5,4], entonces ambas xs !! 2 y xs2 !! 2 devolverá 2:

xs = [1,2, xs2 !! 5,4]

xs2 = xs ++ xs

xs2 !! 2 -> 2

xs !! 2 -> 2

Esta es una consecuencia de la evaluación de expresiones de Haskell a través de la reducción: el orden de las expresiones no importa.

martes, 13 de octubre de 2020

Lista de comprensión en Haskell


Una lista de comprensión es una notación de alto nivel para especificar el cálculo de una lista.

El compilador transforma automáticamente las comprensiones de una lista en una expresión utilizando una familia de funciones básicas que operan en listas.

Las comprensiones de listas se inspiraron en la comprensión de conjuntos de notación matemática.

Ejemplos de comprensiones de conjuntos:

Un conjunto obtenido al multiplicar los elementos de otro conjunto por 3 es {3 × x | x ← {1,…, 10}}.

El conjunto de números pares es {2 × x | x ← N}.

El conjunto de números impares es

{2 × x + 1 | x ← N}.

El producto cruzado de dos conjuntos A y B es {(a, b) | a ← A, b ← B}.

Ejemplos de listas por comprensión

[3 * x | x <- [1..10]]

-> [3,6,9,12,15,18,21,24,27,30]

[2 * x | x <- [0..10]]

-> [0,2,4,6,8,10,12,14,16,18,20]

[2 * x + 1 | x <- [0..10]]

-> [1,3,5,7,9,11,13,15,17,19,21]

[[a, b] | a <- [10,11,12], b <- [20,21]]

-> [[10,20], [10,21], [11,20], [11,21], [12,20], [12,21]]

sábado, 10 de octubre de 2020

Secuencias en Haskell

 


A veces es útil tener una secuencia de números. En notación matemática estándar, puede escribir 0,1,…, n.

Haskell tiene una notación de secuencia para listas.

Escriba la secuencia entre corchetes, con el valor inicial, el operador .. y el valor final.

[0 .. 5] -> [0,1,2,3,4,5]

[100 .. 103] -> [100,101,102,103]

Los elementos se incrementan en 1 y las secuencias no se limitan a números

Hay muchos tipos enumerables en los que existe una forma natural de incrementar un valor.

Puede utilizar secuencias en cualquier tipo.

Los caracteres son enumerables y se pueden expresar listas de esta manerá.

Por ejemplo:

[’A’ .. ’z’]

-> ['a', 'b', 'c', 'd', 'e', ​​'f', 'g', 'h', 'i', 'j', 'k', 'l', ' m ',' n ',' o ',' p ',' q ',' r ',' s ',' t ',' u ',' v ',' w ',' x ',' y ' , 'z']

es una lista de caracteres;

[’0’ .. ’9’]

-> [’0’, ’1’, ’2’, ’3’, ’4’, ’5’, ’6’, ’7’, ’8 ',' 9’]

es una lista de caracteres (que resultan ser los dígitos);

[0 .. 9]

-> [0,1,2,3,4,5,6,7,8,9]

es una lista de números.