[<<][meta][>>][..]

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
program orders.

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?

[Reply][About]

[<<][meta][>>][..]