math - plataforma - haskell uso

Enfoques de dualidad en programación funcional

Question

Me gustaría saber qué tipo de problemas de la vida real se pueden abordar mediante "métodos de dualidad" en la programación funcional. Más precisamente, me gustaría saber si alguien realmente utilizó un método de dualidad como los que presento a continuación, o si hay otros ejemplos interesantes. Me interesarían particularmente las implementaciones existentes , probablemente en Haskell.

[Dado que la mayoría de las personas que estarán interesadas en esta pregunta probablemente conozcan a Haskell, permítanme agregar la etiqueta Haskell, incluso si la pregunta es bastante independiente del idioma]

Permítanme explicar qué quiero decir con dualidad (por falta de un nombre mejor) a través de algunos ejemplos. El primero son los números reales . Asuma la existencia de un Integer y un tipo Rational , y defina un número real como una función (disculpe mi Haskell, no soy un haskeller hardcore)

type Real = Integer -> Rational

de modo que siempre que x :: Real denota el número real x, xn arroja un número racional que está dentro de 2^(-n) de x.

Ahora uno puede hacer

(+) :: Real -> Real -> Real
(+) x y n = (x $ n + 1) + (y $ n + 1)

o lo mismo para otras operaciones aritméticas. Dada una función real continua f, también se puede calcular fx tan pronto como se pueda calcular un módulo de continuidad para f .

Esto tiene la ventaja de que uno puede escribir código de aspecto natural y, al final, obtener un resultado con el nivel de precisión deseado automáticamente. Sin embargo, ya no es posible comparar números reales para la igualdad. El único tipo de comparación posible entre y es x < y + eps .

Otro ejemplo de dualidad es esta pregunta sobre las medidas de probabilidad , que desencadenó la presente pregunta en mi cabeza. Escribanos

type Measure a = (a -> Double) -> Double

y definir medidas como procedimientos de integración contra funciones. En la pregunta vinculada, muestro cuán natural es en este marco expresar conceptos como convolución o empuje hacia adelante que son mucho más difíciles (computacionalmente, pero también teóricamente) para definir a nivel de densidades de probabilidad.

Le permite a uno componer bloques de construcción de la teoría de la probabilidad, y en principio le permite a uno construir procedimientos complejos de Monte Carlo, e incluso permite trabajar con densidades de probabilidad explícitas (a expensas de la integración numérica). Estaría especialmente interesado en cualquier intento de una biblioteca del mundo real sobre este tema.

Otro ejemplo que tengo en mente, pero que aún no se formalizó del todo, es la noción de campos vectoriales (de la geometría diferencial), que uno puede expresar como operadores de diferenciación . Para esto, uno necesita un tipo adecuado de "funciones lisas de valores reales", y luego un campo vectorial es así:

type VectorField = SmoothFunction -> SmoothFunction

tal que v (f * g) = f * (vg) + g * (vf) .

Por supuesto, describir una gavilla de funciones regulares en, digamos, Haskell no debería ser fácil. Pero al hacer eso, podríamos expresar todas las cosas desde la geometría diferencial en una forma independiente totalmente coordinada, y las coordenadas del conector al final.

Hay otros ejemplos, ej. Las series de Taylor se han discutido en el blog de Sigfpe (aunque no puedo encontrar esta publicación en particular), donde una función analítica es del siguiente tipo:

type AnalyticFunction = Double -> Integer -> [Double]

y donde fxn devuelve las n primeras sumas parciales de la expansión de Taylor de f alrededor de x . Esto nos permite escribir sin problemas todo tipo de operaciones aritméticas sobre funciones analíticas, incluyendo cosas como f / g donde f y g pueden desaparecer en un punto (junto con algunas de sus derivadas), o incluso f^(-1) (siempre que f'' no se desvanece). Al final, solo los términos necesarios de la serie intermedia se computan para obtener el valor de una expresión dada.

Answer 1

La característica común de su ejemplo es la representación de un objeto (matemático) por funciones . Esto es común en los lenguajes funcionales, pero no tan prácticos como en las matemáticas porque las funciones en los programas se usan de manera extensiva (no se pueden inspeccionar sus definiciones, solo se observan sus acciones en los argumentos) y solo con operaciones computables (solo se puede observar un número finito de argumentos).

En matemáticas, no te molestas con esas cosas, por ejemplo, muy a menudo dices "si f es analítico, entonces vamos a (a_n) sea su secuencia de coeficientes, y ...". En un lenguaje informático, si comienza con una función de tipo Double -> Integer -> [Double] , será doloroso convertirla en una representación en la que pueda recuperar fácilmente los coeficientes. En los lenguajes de programación, la función realmente son cuadros negros.

Por este motivo, los programadores a menudo intentan usar representaciones de datos explícitas en lugar de cuadros negros de funciones. Puede obtener fácilmente una función a partir de una representación de datos (es un tipo de evaluación o interpretación), mientras que a la inversa puede ser más difícil, menos eficiente, etc. Consulte "Todo es una función" en Haskell de Conal Elliott . .

Sin embargo, las funciones se siguen utilizando en los casos en los que realmente queremos objetos extensibles, que solo se pueden observar en lugar de inspeccionar. Para cada observación posible en el objeto que desea definir, se le asigna una función que realiza esta observación. En tu ejemplo, solo tienes una función porque solo tienes una observación. Esta es la idea central de la Programación Orientada a Objetos tal como la define William Cook en su documento Sobre la Abstracción de Datos, Revisitado .

Creo que la razón por la que relacionas esto con el término "dualidad" (un término que está, en la intelligentsia Haskell, más bien relacionado con conceptos de teorías de categorías) es que el cambio de un objeto a alguna forma particular de observación es a veces llamada dualidad en matemáticas, y tiene el efecto de agregar funciones en todas partes. Por ejemplo, existe el ejemplo clásico del dual de un espacio vectorial, y en particular la construcción bidual que es realmente una conversión de un vector a sus observaciones por funciones lineales: se cambia de V a (V -> K) -> K , para K el campo subyacente a su espacio vectorial.

(¿Pensaríamos en las continuaciones leyendo mi último ejemplo? Por supuesto que están relacionadas, ya que esta representación de las continuas es realmente una "observación" de contextos de evaluación concretos, representados por su acción sobre los valores).

La representación de las medidas de probabilidad se usa realmente para definir las mónadas de la medida de probabilidad en los lenguajes funcionales. Existen diferentes formas de definir las probabilidades de mónadas. Ver por ejemplo http://www.cs.tufts.edu/~nr/pubs/pmonad-abstract.html por Norman Ramsey y Avi Pfeffer. Sin embargo, la mayoría de las implementaciones del mundo real de DSL de probabilidad usan una representación más concreta, como una lista de pares [(prob,event)] (biblioteca de probability Haskell y OCaml okmij.org/ftp/kakuritu ).

Finalmente, para un ejemplo de representación de números reales como funciones, ver A Monadic de Russel O''Connor , Implementación funcional de números reales . Existen numerosas representaciones de números "computables" y tienen diferentes méritos, y la mayoría de ellos se basan en secuencias y, por lo tanto, pueden representarse como Integer -> ... funciones.