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?