TRADUCIR LAS MATEMÁTICAS EN CÓDIGO CON EJEMPLOS EN JAVA, LA RAQUETA, HASKELL Y PYTHON

Las estructuras matemáticas discretas son la base de la informática.

Estas estructuras son tan universales que la mayoría de los trabajos de investigación en la teoría de la computación, lenguajes de programación y los métodos formales de presentar los conceptos en términos de la matemática discreta en lugar de código.

El supuesto subyacente es que el lector sabe cómo traducir estas estructuras en un fiel cumplimiento de un programa de trabajo.

La falta de material que explica esta traducción frustra los forasteros.

Lo que profundiza la frustración es que cada modelo de lenguaje codifica estructuras discretas de una maneradistinta.

Muchas de las codificaciones son tan inmutables, estructuras de datos puramente funcional (incluso en los lenguajes imperativos), un tema que por desgracia omite muchos currículos de informática. Muchas bibliotecasestándar proporcionan sólo mutable versiones de estas estructuras de datos, lo que lleva inmediatamente a las trampas.

Okasaki clásico de estructuras de datos puramente funcional es una referencia esencial:

ATENCIÓN: MATEMÁTICAS NO TIENE EFECTOS SECUNDARIOS

Los recién llegados error fatal que al traducir las matemáticas en código es mutable utilizando estructuras de datos en la que sólo una estructura inmutable, estaba en lo cierto.

Las matemáticas no tiene efectos secundarios.

Las matemáticas no puede modificar el valor de una variable - ya sea global o local. No se puede mutar un elemento de una matriz. Y, una función matemática devuelve siempre el mismo valor para la misma entrada.

La traducción literal de las matemáticas en el código no puede contener los efectos secundarios.

Las matemáticas son un lenguaje puramente funcional.

Por supuesto, una vez que las limitaciones de una aplicación se entienden, por lo general es posible cambiar las estructuras de datos inmutables mutable de los lugares clave para lograr ahorros de rendimiento.

Sin embargo, a los efectos de creación de prototipos, que siempre es mejor comenzar con una aplicación directa, puramente funcional.

CONJUNTOS Y CONJUNTOS DE PODER

La prestación de un conjunto como el código suele ser un tipo, una colección de respaldo de un árbol de equilibrado o un mapa hash, o un predicado.

En matemáticas, un conjunto es una colección desordenada de elementos.

El conjunto vacío - ∅ - es un conjunto especial que no contiene elementos.

La sintaxis de los juegos de llaves es literal: {}. Por ejemplo, el conjunto {1,2,3} es el conjunto que contiene 1, 2 y 3.

La relación x ∈ S declara que el valor de x es un miembro del conjunto S.

Establece como tipos

Conjuntos infinitos suelen ser codificados como tipos.

(Por supuesto, algunos conjuntos finitos se codifican como tipo también.)

En algunos casos, un conjunto X se define como un subconjunto de otro conjunto Y:

  X ⊂ Y.
Esta relación subconjunto puede ser representada como sucesiones en un lenguaje como Java o Python, si estos juegos están destinados a ser los tipos:

la clase X se extiende Y {... }
Cuando un conjunto X se define como el conjunto potencia de otro conjunto Y:

X = P (Y) = 2Y,
entonces X e Y serán los tipos, y los miembros de X será colecciones.

CONJUNTOS COMO COLECCIONES

Cuando el contenido de un conjunto se calcula en tiempo de ejecución, a continuación, a menudo será una colección ordenada respaldado por una estructura como un árbol rojo-negro.

No es difícil de implementar un árbol de búsqueda puramente funcional, ordenado (pero no balanceada) en Java:

interface Ordered <T> {
  public boolean isLessThan(T that) ;
}

abstract class SortedSet<T extends Ordered<T>> {
  public abstract boolean isEmpty() ;
  public abstract boolean contains(T element) ;
  public abstract SortedSet<T> add(T element) ;

  public static final <E extends Ordered<E>> SortedSet<E> empty() {
    return new EmptySet<E>();
  }
}

final class EmptySet<T extends Ordered<T>> extends SortedSet<T> {
  public boolean isEmpty() {
    return true ;
  }

  public boolean contains(T element) {
    return false ;
  }

  public SortedSet<T> add(T element) {
    return new Node<T>(this,element,this) ;
  }

  public EmptySet() {
  }
}

final class Node<T extends Ordered<T>> extends SortedSet<T> {

  private final SortedSet<T> left ;
  private final T element ;
  private final SortedSet<T> right ;

  public boolean isEmpty() {
    return false ;
  }

  public Node(SortedSet<T> left, T element, SortedSet<T> right) {
    this.left = left ;
    this.right = right ;
    this.element = element ;
  }

  public boolean contains(T needle) {
    if (needle.isLessThan(this.element)) {
      return this.left.contains(needle) ;
    } else if (this.element.isLessThan(needle)) {
      return this.right.contains(needle) ;
    } else {
      return true ;
    }
  }

  public SortedSet<T> add(T newGuy) {
    if (newGuy.isLessThan(this.element)) {
      return new Node<T>(left.add(newGuy),this.element,right) ;
    } else if (this.element.isLessThan(newGuy)) {
      return new Node<T>(left,this.element,right.add(newGuy)) ;
    } else {
      return this ; // Already in set.
    }
  }
}