Como funciona o Data.MemoCombinators?

Question

Eu estive olhando a fonte por Data.MemoCombinadores mas não consigo realmente ver onde está o cerne disso.

Por favor, explique-me qual é a lógica por trás de todos esses combinadores e a mecânica de como eles realmente funcionam para acelerar seu programa na programação do mundo real.

Estou procurando detalhes para esse implementação e, opcionalmente, comparação/contraste com outras abordagens Haskell para memoização.Eu entendo o que é memoização e sou não procurando uma descrição de como funciona em geral.

Answer 1

Esta biblioteca é uma combinação direta da conhecida técnica de memorização.Vamos começar com o exemplo canônico:

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

Eu interpreto o que você disse como significando que você sabe como e por que isso funciona.Então vou me concentrar na combinatorização.

Estamos essencialmente tentando capturar e generalizar a ideia de (map f [0..] !!).O tipo desta função é (Int -> r) -> (Int -> r), o que faz sentido:leva uma função de Int -> r e retorna uma versão memorizada da mesma função.Qualquer função que seja semanticamente a identidade e tenha esse tipo é chamada de "memoizador para Int" (até id, que não memoriza).Generalizamos para esta abstração:

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

Então um Memo a, um memorizador para a, assume uma função de a para qualquer coisa e retorna uma função semanticamente idêntica que foi memorizada (ou não).

A ideia dos diferentes memoizers é encontrar uma maneira de enumerar o domínio com uma estrutura de dados, mapear a função sobre eles e então indexar a estrutura de dados. bool é um bom exemplo:

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

Funções de Bool são equivalentes a pares, exceto que um par avaliará cada componente apenas uma vez (como é o caso de cada valor que ocorre fora de um lambda).Então, apenas mapeamos para um par e voltamos.O ponto essencial é que estamos elevando a avaliação da função acima do lambda para o argumento (aqui o último argumento de table) enumerando o domínio.

Memoizando Maybe a é uma história semelhante, só que agora precisamos saber como memorizar a para o Just caso.Então o memoizer para Maybe leva um 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

O resto da biblioteca são apenas variações deste tema.

A maneira como ele memoriza tipos integrais usa uma estrutura mais apropriada do que [0..].É um pouco complicado, mas basicamente cria apenas uma árvore infinita (representando os números em binário para elucidar a estrutura):

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

Portanto, procurar um número na árvore tem tempo de execução proporcional ao número de bits em sua representação.

Como sclv aponta, a biblioteca MemoTrie de Conal usa a mesma técnica subjacente, mas usa uma apresentação de classe de tipo em vez de uma apresentação de combinador.Lançamos nossas bibliotecas de forma independente ao mesmo tempo (na verdade, em algumas horas!).O Conal é mais fácil de usar em casos simples (há apenas uma função, memo, e determinará a estrutura do memorando a ser usada com base no tipo), enquanto a minha é mais flexível, pois você pode fazer coisas como esta:

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

Que memoriza apenas valores inferiores a um determinado limite, necessários para a implementação de um dos problemas de Euler do projeto.

Existem outras abordagens, por exemplo, expor uma função de ponto fixo aberta sobre uma mônada:

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

O que permite ainda mais flexibilidade, por exemplo.limpar caches, LRU, etc.Mas é um saco de usar e também impõe restrições de rigor à função a ser memorizada (por exemplo,sem recursão infinita à esquerda).Não acredito que existam bibliotecas que implementem essa técnica.

Isso respondeu ao que você estava curioso?Se não, talvez deixe explícitos os pontos sobre os quais você está confuso?

Answer 2

O coração é o bits função:

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

É a única função (exceto a trivial unit :: Memo ()) o que pode lhe dar uma Memo a valor.Ele usa a mesma ideia deste página sobre memoização de Haskell.A seção 2 mostra a estratégia de memorização mais simples usando uma lista e a seção 3 faz o mesmo usando uma árvore binária de naturais semelhante à IntTree usado em memocombinadores.

A idéia básica é usar uma construção como (map fib [0 ..] !!) ou no caso de memocombinadores - IntTrie.apply (fmap f IntTrie.identity).O que se deve notar aqui é a correspondência entre IntTie.apply e !! e também entre IntTrie.identity e [0..].

O próximo passo é memorizar funções com outros tipos de argumentos.Isto é feito com o wrap função que usa um isomorfismo entre tipos a e b para construir um Memo b a partir de um Memo a.Por exemplo:

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

O restante do código-fonte trata de tipos como List, Maybe, Both e memorização de vários argumentos.

Answer 3

Parte do trabalho é feito pela IntTrie: http://hackage.haskell.org/package/data-inttrie-0.0.4

A biblioteca de Luke é uma variação da biblioteca MemoTrie de Conal, que ele descreveu aqui: http://conal.net/blog/posts/elegant-memoization-with-funcional-memo-tries/

Alguma expansão adicional - a noção geral por trás da memoização funcional é pegar uma função de a -> b e mapeá-lo em uma estrutura de dados indexada por tudo possível valores de a e contendo valores de b.Tal estrutura de dados deve ser preguiçosa de duas maneiras – primeiro, deve ser preguiçosa nos valores que contém.Em segundo lugar, ele próprio deveria ser produzido preguiçosamente.O primeiro está, por padrão, em uma linguagem não estrita.O último é realizado usando tentativas generalizadas.

As várias abordagens de memocombinadores, memotrie, etc. são apenas maneiras de criar composições de pedaços de tentativas sobre tipos individuais de estruturas de dados para permitir a construção simples de tentativas para estruturas cada vez mais complexas.

Answer 4

@luqui Uma coisa que não está clara para mim:isso tem o mesmo comportamento operacional que o seguinte:

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

O texto acima deve memorizar mentiras no nível superior e, portanto, se você definir duas funções:

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

Se então calcularmos f5, obtemos que mentira 5 não é recalculado ao calcular mentira 6.Não está claro para mim se os combinadores de memorização têm o mesmo comportamento (ou seja,memoização de nível superior em vez de apenas proibir a recomputação "dentro" do cálculo da mentira) e, em caso afirmativo, por que exatamente?