Sat May 8 13:06:29 EDT 2010
Just flattening + node allocation + input collection.
Let's properly solve the problem of node flattening and input/output
gathering first using a specialized data type that has the minimal set
data Graph n v = Leaf v | Node n [Graph n v]
Where the n type identifies nodes (i.e. it could be an opcode) and the
v type identifies node names in a unique way. This should then be
massaged into a non-recursive data type:
data Binding n v = Binding v n [v]
data Dict n v = Dict [v] [v] [v] [Binding n v]
The flatten function takes a temp node generator and a list of variable
to output term bindings to build a dictionary structure.
flatten :: [v] -> [(v, Graph n v)] -> Dict n v
This consists of two steps:
* fold over tree
* fold over list
Just like before, the Fold is the most important part. What is the
accumulator for the fold? The dictionary, but in a form that can
represent pointer equality.
( I'm cursing now at the absence of side effects... Accumulations
like these are trivial in Scheme. I've been able to avoid these in
Haskell up to now.. )
So, what about writing Flatten.hs without memoization first, then try
to memoize it? Even then, writing down the recursion pattern:
dict -> tree -> (dict, tree)
is problematic. In SSH.hs `envFold' I've written it out explicitly.
Looks like it's time to go to basics again.
* Making "flatten" explicit is probably a good idea. It's a decent
interface and it makes it possible to concentrate on the essence :
remove recursion from (any?) datatype by introducing variable
* I'm struggling with two basic abstractions: dealing with object
equality (which can currently be ignored by using non-memoized ==
and later try to memoize it), and dealing with map + threaded