`[<<][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][>>][..]`