¿Cómo de Datos.MemoCombinators trabajo?

Question

He estado mirando el código fuente para De datos.MemoCombinators pero realmente no veo donde está el corazón de lo que es.

Por favor, que me explique cuál es la lógica que está detrás de todos estos combinadores y la mecánica de la forma en que realmente trabajan para acelerar su programa en el mundo real de la programación.

Estoy buscando detalles para este aplicación, y, opcionalmente, comparación y contraste con otros Haskell enfoques memoization.Entiendo lo que memoization es y estoy no buscando una descripción de cómo funciona en general.

Answer 1

Esta biblioteca es un sencillo combinatorization de la conocida técnica de memoization.Vamos a empezar con el ejemplo canónico:

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

Debo interpretar lo que se dice que significa que usted sabe cómo y por qué funciona esto.Así que me centraré en la combinatorization.

Estamos essentiallly tratando de capturar y generalizar la idea de (map f [0..] !!).El tipo de esta función es (Int -> r) -> (Int -> r), lo cual tiene sentido:se necesita una función de Int -> r y devuelve un memoized versión de la misma función.Cualquier función que es semánticamente la identidad y tiene este tipo se llama un "memoizer para Int"(incluso id, que no memoize).Podemos generalizar 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 nada, y devuelve un semánticamente idénticas función que ha sido memoized (o no).

La idea de las diferentes memoizers es encontrar una manera de enumerar el dominio con una estructura de datos, mapa de la función por encima de ellos, y, a continuación, el índice de 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

Funciones de Bool son equivalentes a los pares, a excepción de un par solamente evaluar cada componente de una vez (como es el caso para cada valor que se produce fuera de un lambda).Así que acaba de asignar a un par y la espalda.El punto esencial es que estamos levantando la evaluación de la función por encima de la lambda para el argumento (aquí el último argumento de table) mediante la enumeración de dominio.

Memorización Maybe a es una historia similar, excepto que ahora necesitamos saber cómo memoize a para el Just caso.Así que el memoizer para Maybe toma un memoizer para a 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 sólo variaciones sobre este tema.

La forma en que se memoizes integral de los tipos de usos más adecuados de la estructura de [0..].Es un poco implicado, pero, básicamente, sólo crea un árbol infinito (en representación de los números en binario para dilucidar la estructura):

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

Así que buscando un número en el árbol tiene tiempo de ejecución es proporcional al número de bits en la representación.

Como sclv señala, Conal del MemoTrie biblioteca usa la misma técnica, pero utiliza un typeclass presentación en lugar de un combinador de presentación.Damos a conocer nuestras bibliotecas de forma independiente al mismo tiempo (de hecho, dentro de un par de horas!).Conal es más fácil de usar en casos sencillos (sólo hay una función, memo, y eso va a determinar el memo de la estructura a utilizar según el 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 sólo memoizes valores de menos de un determinado obligado, necesario para la aplicación de uno de los proyecto de euler problemas.

Hay otros enfoques, por ejemplo, la exposición de un abierto de punto fijo de la función a través de una mónada:

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

Lo que permite aún más flexibilidad, por ejemplo.purgar caché, la LRU, etc.Pero es un dolor en el culo a usar, y también se pone el rigor restricciones en la función a ser memoized (por ejemplo,no infinito izquierda recursividad).No creo que hay alguna de las bibliotecas que implementan esta técnica.

Hizo que conteste lo que tenía curiosidad acerca de?Si no, tal vez hacer explícitos los puntos que usted está confundido acerca de?

Answer 2

El corazón es el bits función:

-- | 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 el trivial unit :: Memo ()) que le puede dar una Memo a valor.Se utiliza la misma idea que en este página sobre Haskell memoization.La sección 2 muestra la más simple memoization estrategia de uso de una lista y en la sección 3 hace lo mismo mediante un árbol binario de productos naturales similares a la IntTree se utiliza en memocombinators.

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

El siguiente paso es la memorización de las funciones con otros tipos de argumentos.Esto se hace con el wrap función que utiliza un isomorfismo entre los tipos de a y b para la construcción de un Memo b a partir de una 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 de la fuente de código se refiere a los tipos de la Lista, tal vez, ninguno de los dos y memorización de varios argumentos.

Answer 3

Algunos de los trabajos se realizan por inttrie: http://hackage.haskell .org / Paquete / 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 memoización funcional es realizar una función de a -> b y mapearlo a través de un Dataestructure indexado por los valores todos los valores posible de a y que contienen valores de b. Dicha arcutos de datos deben ser perezosos de dos maneras: primero debe ser perezoso en los valores que sostiene. En segundo lugar, se debe producir perezosamente. El primero está por defecto en un lenguaje no estricto. Este último se logra mediante el uso de intentos generalizados.

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

Answer 4

@luqui Una cosa que no está clara para mí: ¿Tiene esto el mismo comportamiento operativo que los siguientes:

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 la FIB en el nivel superior y, por lo tanto, si define dos funciones:

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

Si nos calculamos F 5 , obtenemos que FIB 5 no se recomienda al computarlo FIB 6 .No está claro si los combinadores de memoización tienen el mismo comportamiento (es decir, la memoización a nivel superior en lugar de prohibir solo la recomputación "dentro" de la cálculo de la fib), y de ser así, ¿por qué exactamente?