Sat Feb 13 19:38:16 CET 2010
Memoizing original "merge" approach
The more I think about this, the more I like the previous incremental
approach. Maybe focussing on memoizing node-set membership (modulo
equivalences like commutation for + and *) is a better approach?
So what is a memo-term?
- Term: an expression tree
- [Term]: a list (set?) of all expression nodes (*)
- Term -> Maybe Term: a (fast) is-member function
If (*) is a list, the order should be one of the possible sequential
Problem: naive node membership is too expensive, as the (==) is
recursive, and recomputes equality of nodes multiple times.
termNodes = f where
f t@(Op _ ts) = t : (concat $ map f ts)
f t = [t]
firstWith p = f where
f  = Nothing
f (x:xs) | p x = Just x
f (_:xs) = f xs
-- Naive node membership;
nodeOf t0 = firstWith (t0 ==) . termNodes
So.. Memoization is usually based on the equality function, but what
if that's exactly the function to memoize?