Sat May 8 15:07:24 EDT 2010
The core operation is:
- Check if a node is already present in the dictionary. If not,
allocate a new intermediate tag and update the dictionary.
- Replace node with tag.
So there are two state components that need to be threaded: currently
visited nodes + node naming.
type Scan n v = State ([v], Dict n v) v
Hmm... too many loose ends. One thing at a time.
Key elements seem to be:
1. Convert tree into a list of nodes (abstract recursive decent)
2. Write dictExtend as n -> State ...
3. fmap (n -> State ..) over nodes to get [State ...]
4. sequence the [State ..] into State
6. flatten the dictionary elements.
Ok, got full flattening + sharing without memo in Flatten.hs
The remarkable thing is that the output is completely ignored.
Meaning this is just a fold and the State monad isn't necessary.
However, it might be easier to stick to the monad such that it can be
combined with the IO monad for stable names.
dictExtend is now factored into a foldable function, with the State
monad version derived from it.