[haskell-br] Diagramas de Decisão Binária Ordenada e Reduzida

[Daniel Yokomizo]

Eric, uma opção legal é usar o Data.MemoCombinators (
http://hackage.haskell.org/packages/archive/data-memocombinators/0.3/doc/html/Data-MemoCombinators.html)
ele inclui uns combinadores bem práticos que ajudam nesses casos.


2013/8/16 Eric Kinoshita <eric.void at gmail.com>

> Talvez as funções de síntese (operação entre BDDs) ficariam mais claras
> usando mônadas.
>
> As figuras desse artigo lembram bastante as figuras que fiz no meu :P
> Depois vou dar uma olhada com mais calma.
>
>
> Para vocês não terem que ler o meu código, segue uma ilustração do que
> fiz, usando fibonacci:
>
>
> import Data.Map as M
>
> -- 'wrapper' para inicializar o mapa de memoização
> fibonacci n = fst $ fib n M.empty
>
> type Memo = M.Map Int Int
>
> fib :: Int -> Memo -> (Int, Memo)
> fib 0 memo = (0, memo) -- caso base
> fib 1 memo = (1, memo) -- caso base
> fib n memo = fib' n (M.lookup n memo) memo -- confere o mapa de memoização
>
>
> fib' :: Int -> Maybe Int -> Memo -> (Int, Memo)
> fib' _ (Just x) memo = (x, memo) -- usa o resultado memoizado
> fib' n _ memo = (n1 + n2, memo'') -- definição recursiva
>   where (n1, memo') = fib'' (n - 1) memo
>         (n2, memo'') = fib'' (n - 2) memo'
>
> -- faz a recursão e memoíza
> fib'' n memo = (r, M.insert n r memo')
>     where (r, memo') = fib n memo
>
>
> Assim, eu uso memoização e o algoritmo fica bem eficiente, em
> contrapartida o código é sujo e confuso.
>
> Tem como manter a recursão dupla, mas não ter que ficar passando o mapa de
> Memoização por todo lado? Ou ao menos da memoização não ficar tão explícita?
>
> Abraços,
>
>  Eric
>
>   Eric
>
>
> 2013/8/16 Rodrigo Ribeiro <rodrigogribeiro at gmail.com>
>
>> Oi Eric, tudo bom?
>>
>> Dei uma olhada rápida no seu código e uma possível maneira de evitar a
>> passagem de parâmetros adicionais em funções é usar uma mônada (State ou
>> Reader). Caso o uso de mônadas não seja vantajoso, esse artigo trata de um
>> problema similar:
>>
>>
>> http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/09-ChristiansenHuch-APurelyFunctionalImplementationOfROBDDs.pdf
>>
>> [ ]s
>>
>>
>> Rodrigo
>>
>>
>> 2013/8/15 Eric Kinoshita <eric.void at gmail.com>
>>
>>> Oi pessoal,
>>>
>>> Fiz a tradução do meu TCC pra haskell. Vide link abaixo.
>>>
>>> https://bitbucket.org/ericvoid/robdd
>>>
>>> Gostaria que vcs dessem uma olhada, para ver se tem como melhorar.
>>>
>>> Des do ultimo dojo consegui dar um upgrade no código. Dei uma boa
>>> organizada e troquei as listas por Maps. Isso deu um ganho de eficiência
>>> gigante. Mas o arquivo de síntese é o que deve estar mais bagunçado.
>>>
>>> Será que tem alguma forma de memoizar uma função sem ter que ficar
>>> passando a estrutura de dados para todo lado?
>>>
>>> Obrigado,
>>>
>>>   Eric
>>>
>>> _______________________________________________
>>> haskell-br mailing list
>>> haskell-br at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-br
>>>
>>>
>>
>
> _______________________________________________
> haskell-br mailing list
> haskell-br at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-br
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-br/attachments/20130816/8417ad03/attachment.htm>