multiplicar - multiplos en haskell

¿Cómo se implementan los algoritmos de programación dinámica en Haskell idiomático?

Question

Haskell y otros lenguajes de programación funcionales se basan en la premisa de no mantener el estado. Todavía soy nuevo en cuanto a cómo funciona la programación funcional y los conceptos en ella, así que me preguntaba si es posible implementar algoritmos DP de una manera FP.

¿Qué construcciones de programación funcional se pueden usar para hacer eso?

Answer 1

Algoritmos de Rabhi y Lapalme : un enfoque de programación funcional tiene un buen capítulo sobre esto que ilustra algunos conceptos de FP que se ponen en uso, a saber , funciones de orden superior y evaluación perezosa . Supongo que está bien para mí reproducir una versión simplificada de su función de orden superior.

Se simplifica porque solo funciona en funciones que toman Int como entrada y producen Int como salida. Debido a que estamos usando Int de dos formas diferentes, crearé sinónimos para ellos "Clave" y "Valor". Pero no olvide que, debido a que son sinónimas, es perfectamente posible utilizar claves y valores, y viceversa. Solo se usan para leer.

type Key = Int
type Value = Int
dynamic :: (Table Value Key -> Key -> Value) -> Key -> Table Value Key
dynamic compute bnd = t
where t = newTable (map (/coord -> (coord, compute t coord)) [0..bnd])

Analicemos esta función un poco.

Primero, ¿qué hace esta función? Desde la firma tipo, podemos ver que de alguna manera manipula las tablas. De hecho, el primer argumento "calcular" es una función (por lo tanto, dinámica es una función de "orden superior") que produce algún tipo de valor de una tabla, y el segundo argumento es solo una especie de límite superior, diciéndonos dónde parar. Y como salida, la función "dinámica" nos da algún tipo de tabla. Si queremos obtener la respuesta a algún problema amigable con DP, ejecutamos "dinámico" y luego buscamos la respuesta de nuestra Tabla.

Para usar esta función para calcular fibonacci, la ejecutaremos un poco como esta

fib = findTable (dynamic helper n) n
where
helper t i =
if i <= 1
then i
else findTable t (i-1) + findTable t (i-2)

No se preocupe demasiado por entender esta función fib por ahora. Se aclarará un poco al explorar "dinámico".

En segundo lugar, ¿qué clase de prerrequisitos necesitamos conocer para comprender esta función? Asumiré que está más o menos familiarizado con la sintaxis, el [0..x] para indicar una lista de 0 a x, el -> en firmas de tipo como Int -> Tabla -> ... versus el - > en funciones anónimas como / coord -> ... Si no te sientes cómodo con esto, es posible que se interponga en el camino.

Otro requisito previo para abordar es esta tabla de búsqueda. No queremos preocuparnos por cómo funciona, pero supongamos que podemos crearlos a partir de listas de pares clave-valor y también buscar entradas en ellos:

newTable :: [(k,v)] -> Table v k
findTable :: Table v k -> k -> v

Tres cosas a tener en cuenta aquí:

• Para simplificar, no estamos usando el equivalente de la biblioteca estándar de Haskell
• findTable se bloqueará si le pide que busque un valor inexistente de la tabla. Podemos usar una versión más elegante para evitar esto si es necesario, pero ese es un tema para una publicación diferente
• Por extraño que parezca, no mencioné ningún tipo de función de "agregar un valor a la mesa", a pesar de que el libro y las bibliotecas estándar de Haskell proporcionan uno. Por qué no?

Finalmente, ¿cómo funciona realmente esta función? ¿Que está pasando aqui? Podemos acercar un poco la carne de la función,

t = newTable (map (/coord -> (coord, compute t coord)) [0..bnd])

y romperlo metódicamente. Yendo de afuera hacia adentro, tenemos t = newTable (...), lo que parece decirnos que estamos construyendo una tabla a partir de algún tipo de lista. Aburrido. ¿Qué hay de la lista?

map (/coord -> (coord, compute t coord)) [0..bnd]

Aquí tenemos la función de mapa de orden superior caminando por una lista de 0 a bnd y produciendo una nueva lista como resultado. Para calcular la nueva lista, está usando una función / coord -> (coord, compute t coord). Tenga en cuenta el contexto: estamos tratando de construir una tabla a partir de pares de valores clave, por lo que si estudia la tupla, la primera parte coord debe ser la clave y la segunda parte calcular t coordenadas debe ser el valor. Esa segunda parte es donde las cosas se ponen emocionantes. Vamos a acercar un poco más

compute t coord

Estamos construyendo una tabla a partir de pares clave-valor y el valor que estamos conectando a estas tablas proviene de ejecutar "calcular coordenadas". Algo que no mencioné antes es que el cálculo toma una tabla y una clave como entrada y nos dice qué valor debemos incluir en la tabla, en otras palabras, qué valor debemos asociar con esa clave. La idea, entonces, de llevar esto a la programación dinámica, es que la función de cálculo usa los valores previos de la tabla para calcular ese nuevo valor que debemos conectar.

¡Y eso es todo! Para hacer una programación dinámica en Haskell podemos construir algún tipo de tabla al conectar sucesivamente los valores en las celdas usando una función que busca valores previos de la tabla. Fácil, ¿verdad? ... ¿o no?

Quizás tengas una experiencia similar a la que tuve yo. Así que quiero compartir mi progreso actual lidiando con esta función. La primera vez que leí esta función, pareció tener una especie de sentido intuitivo y no pensé mucho más en ello. Luego lo leí más cerca e hice una especie de doble toma, ¿qué espera? ¿Cómo puede esto funcionar? Eche un segundo vistazo a este fragmento de código aquí.

compute t coord

Para calcular el valor en una celda dada y así llenar la tabla, pasamos t, la misma tabla que intentamos crear en primer lugar. Si la programación funcional se trata de inmutabilidad como usted señala, ¿cómo puede funcionar este negocio de usar valores que aún no hemos calculado? Si tiene un poco de FP en su haber, podría preguntarse a sí mismo como lo hice, "¿es eso un error?", ¿No debería ser un "pliegue" en lugar de un "mapa"?

La clave aquí es la evaluación perezosa. La pequeña magia que hace posible crear un valor inmutable a partir de partes de sí mismo se reduce a la pereza. Siendo una especie de Haskeller de cinturón amarillo a largo plazo, todavía encuentro la noción de pereza un poco desconcertante. Así que tendré que dejar que alguien más se haga cargo aquí.

Mientras tanto, simplemente me digo a mí mismo que esto está bien. Me contento con visualizar la Mesa como una especie de punto con muchas flechas sobresaliendo de ella. Tomando fib como ejemplo:

o
|
|--0--> 1
|
|--1--> 1
|
|--2--> 2
|
|--3--> 2
.
.
.

Los bits de la tabla que aún no hemos visto son territorio desconocido. Cuando caminamos por la lista, todo está por descubrir

o
.
.
.

Cuando queremos calcular el primer valor, no necesitamos saber nada más sobre la tabla porque i <= 1.

 helper t i =
if i <= 1
then i
else findTable t (i-1) + findTable t (i-2)
o
|
|--0--> 1
.
.
.

Cuando queremos calcular valores sucesivos, siempre estamos mirando hacia atrás en las partes ya descubiertas de la tabla (programación dinámica, hey-hey!). La clave para recordar es que estamos trabajando al 100% con valores inmutables aquí, sin trucos de fantasía además de la pereza. "t" realmente significa la tabla, y no "la tabla en su estado actual en la iteración 42". Es solo que solo descubrimos los bits de la tabla que nos dicen cuál es el valor que corresponde a 42 cuando realmente lo solicitamos.

Afortunadamente, con otros en , irás más lejos que yo y no te dejarán murmurar vagamente "uhm sí, pereza, algo así como otro" Realmente no es un gran problema :-)

Answer 2

La forma más común de hacerlo es a través de la memorización perezosa. En cierto sentido, la función recursiva de Fibonacci se puede considerar una programación dinámica, ya que calcula los resultados a partir de superposiciones de subproblemas. Me doy cuenta de que este es un ejemplo cansado, pero este es un gusto. Utiliza la biblioteca data-memocombinators para la memorización perezosa.

import qualified Data.MemoCombinators as Memo
fib = Memo.integral fib''
where
fib'' 0 = 0
fib'' 1 = 1
fib'' n = fib (n-1) + fib (n-2)

Fib es la versión memorable, y fib'' simplemente'' fuerza bruta ''el problema, pero calcula sus subproblemas utilizando el FIM memorado. Otros algoritmos de DP están escritos en este mismo estilo, utilizando diferentes estructuras de notas, pero con la misma idea de simplemente calcular el resultado de una manera funcional directa y memorizar.

Editar : finalmente cedí y decidí proporcionar una tipografía memorable. Eso significa que la memorización es más fácil ahora:

import Data.MemoCombinators.Class (memoize)
fib = memoize fib''
where
fib'' :: Integer -> Integer -- but type sig now required
...

Instaead de la necesidad de seguir el tipo, simplemente puede memoize cualquier cosa. Todavía puedes usar el viejo modo si te gusta.

Answer 3

La programación dinámica en haskell se puede expresar elegantemente gracias a la pereza, vea el primer ejemplo en esta página

Answer 4

Los algoritmos de programación dinámica usualmente explotan la idea de reducir un problema a problemas más simples. Sus problemas pueden formularse como un hecho básico (por ejemplo, el camino más corto desde una celda cuadrada a sí mismo tiene longitud 0) más un conjunto de reglas recurrentes que muestran exactamente cómo reducir el problema "encontrar el camino más corto desde la celda (i,j) hasta (0,0) " al problema " encuentre las rutas más cortas desde las celdas (i-1,j) , (i,j-1) a (0,0) ; seleccione la mejor " . AFAIK esto se puede expresar fácilmente en un programa de estilo funcional; ningún estado involucrado.

Answer 5

Si desea usar DP con 2 o 3 parámetros (por ejemplo, cuando procesa cadenas) puede usar una matriz inmutable:

import Data.Array.IArray
answer :: String -> Int
answer s = table ! (1, l)
where
l = length s
--signatyres are needed, because GHC doesn''t know what kind of Array we need
--string is stored in Array because we need quick access to individual chars
a :: Array Int Char
a = listArray (1, l) s
table :: Array (Int, Int) Int
table = listArray ((1, 1), (l, l)) [f i j | i <- [1..l], j <- [1..l]]
f i j | i > j = 0
| i == j = 1
| (a ! i) == (a ! j) = 2 + table ! (i+1, j-1)
| otherwise = maximum [table ! (i+1, j), table ! (i, j-1)]

Este código resuelve la siguiente tarea: dada una cadena S, encuentre la subsecuencia de S de longitud máxima, que sería un síndrome (la subsecuencia no necesita ser continua).

Básicamente, ''f'' es la función resursiva, y la matriz ''tabla'' es una matriz de todos sus valores posibles. Como Haskell es flojo, solo se necesitan los valores de respuesta de ''f''. En otras palabras, esto es recursión con memoialización. Entonces usa Data.Memocombinators, que es lo mismo, pero ya escrito por otra persona :)