haskell - ¿Cómo funciona Data.MemoCombinators?

memoization

Question

He estado buscando en la fuente de Data.MemoCombinators pero realmente no puedo ver dónde está el corazón.

Explíqueme cuál es la lógica detrás de todos estos combinadores y la mecánica de cómo funcionan realmente para acelerar su programa en la programación del mundo real.

Estoy buscando detalles para esta implementación y, opcionalmente, comparación / contraste con otros enfoques de Haskell para la memorización. Entiendo qué es la memorización y no estoy buscando una descripción de cómo funciona en general.

Answer 1

@luqui Una cosa que no me queda clara: ¿tiene esto el mismo comportamiento operativo que el siguiente?

fib :: [Int]
fib = map fib'' [0..]
where fib'' 0 = 0
fib'' 1 = 1
fib'' n = fib!!(n-1) + fib!!(n-2)

Lo anterior debe memorizar Fib en el nivel superior, y por lo tanto si define dos funciones:

f n = fib!!n + fib!!(n+1)

Si calculamos f 5 , obtenemos que fib 5 no se vuelve a calcular al calcular fib 6 . No está claro para mí si los combinadores de memo- rización tienen el mismo comportamiento (es decir, memorización de alto nivel en lugar de solo prohibir el recálculo "dentro" del cálculo de fib), y si es así, ¿por qué exactamente?

Answer 2

El corazón es la función de los bits :

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

Es la única función (excepto la unit :: Memo () trivial unit :: Memo () ) que puede darle Memo a valor Memo a . Utiliza la misma idea que en esta page sobre la memoria de Haskell. La sección 2 muestra la estrategia de memorización más simple usando una lista y la sección 3 hace lo mismo usando un árbol binario de elementos naturales similar al IntTree utilizado en los memocombinators.

La idea básica es usar una construcción como (map fib [0 ..] !!) o en el caso de IntTrie.apply (fmap f IntTrie.identity) - IntTrie.apply (fmap f IntTrie.identity) . Lo que hay que notar aquí es la correspondencia entre IntTie.apply y !! y también entre IntTrie.identity y [0..] .

El siguiente paso es memorizar funciones con otros tipos de argumentos. Esto se hace con la función de wrap que usa un isomorfismo entre los tipos a y b para construir un Memo b partir de un Memo a . Por ejemplo:

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

El resto del código fuente trata con tipos como Lista, Tal vez, Cualquiera y memorando múltiples argumentos.

Answer 3

Esta biblioteca es una combinación directa de la conocida técnica de memorización. Comencemos con el ejemplo canónico:

fib = (map fib'' [0..] !!)
where
fib'' 0 = 0
fib'' 1 = 1
fib'' n = fib (n-1) + fib (n-2)

Interpreto que lo que dijiste significa que sabes cómo y por qué funciona esto. Así que me centraré en la combinatización.

Estamos intentando esencialmente capturar y generalizar la idea de (map f [0..] !!) . El tipo de esta función es (Int -> r) -> (Int -> r) , lo que tiene sentido: toma una función de Int -> r y devuelve una versión memorizada de la misma función. Cualquier función que es semánticamente la identidad y tiene este tipo se llama "memoizer for Int " (incluso id , que no se memoriza). Generalizamos a esta abstracción:

type Memo a = forall r. (a -> r) -> (a -> r)

Así que un Memo a , un memoizer para a , toma una función de a para cualquier cosa, y devuelve una función semánticamente idéntica que ha sido memorada (o no).

La idea de los diferentes memoizers es encontrar una manera de enumerar el dominio con una estructura de datos, mapear la función sobre ellos y luego indexar la estructura de datos. bool es un buen ejemplo:

bool :: Memo Bool
bool f = table (f True, f False)
where
table (t,f) True = t
table (t,f) False = f

Las funciones de Bool son equivalentes a pares, excepto que un par solo evaluará cada componente una vez (como es el caso para cada valor que ocurre fuera de una lambda). Así que solo asignamos un par y regresamos. El punto esencial es que estamos levantando la evaluación de la función por encima del lambda para el argumento (aquí el último argumento de la table ) al enumerar el dominio.

Memoying Maybe a es una historia similar, excepto que ahora necesitamos saber cómo memorizar a para el caso Just . Entonces el memorando de Maybe toma un memorando como argumento:

maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
where
table (n,j) Nothing = n
table (n,j) (Just x) = j x

El resto de la biblioteca es solo variaciones sobre este tema.

La forma en que memoriza los tipos integrales usa una estructura más apropiada que [0..] . Es un poco complicado, pero básicamente solo crea un árbol infinito (representa los números en binario para elucidar la estructura):

1
10
100
1000
1001
101
1010
1011
11
110
1100
1101
111
1110
1111

De modo que buscar un número en el árbol tiene un tiempo de ejecución proporcional al número de bits en su representación.

Como señala sclv, la biblioteca MemoTrie de Conal utiliza la misma técnica subyacente, pero utiliza una presentación de clase de tipo en lugar de una presentación combinatoria. Lanzamos nuestras bibliotecas de forma independiente al mismo tiempo (¡de hecho, en un par de horas!). Conal''s es más fácil de usar en casos simples (solo hay una función, memo , y determinará la estructura de memo para usar en función del tipo), mientras que la mía es más flexible, ya que puede hacer cosas como esta:

boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = /z -> if z < bound then memof z else f z
where
memof = integral f

Que solo memoriza valores inferiores a un límite determinado, necesarios para la implementación de uno de los problemas de euler del proyecto.

Hay otros enfoques, por ejemplo, la exposición de una función de punto fijo abierto sobre una mónada:

memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)

Lo cual permite aún más flexibilidad, ej. purgando cachés, LRU, etc. Pero es un fastidio utilizarlo, y también pone restricciones de rigor en la función que se va a memorizar (p. ej., no hay recursividad infinita a la izquierda). No creo que haya bibliotecas que implementen esta técnica.

¿Respondió eso por lo que sentías curiosidad? Si no, ¿tal vez explíqueles los puntos con los que está confundido?

Answer 4

Parte del trabajo lo realiza IntTrie: http://hackage.haskell.org/package/data-inttrie-0.0.4

La biblioteca de Luke es una variación de la biblioteca MemoTrie de Conal, que describió aquí: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

Alguna expansión adicional: la noción general detrás de la memorización funcional es tomar una función de a -> b y mapearla a través de una estructura de datos indexada por todos los valores posibles de b contienen valores de b . Dicha estructura de datos debe ser floja de dos maneras: primero, debe ser floja en los valores que posee. En segundo lugar, debería producirse perezosamente. El primero es por defecto en un lenguaje no estricto. Esto último se logra mediante el uso de intentos generalizados.

Los diversos enfoques de memocombinators, memotrie, etc. son solo formas de crear composiciones de piezas de prueba sobre tipos individuales de estructuras de datos para permitir la construcción simple de intentos para estructuras cada vez más complejas.