[<<][meta][>>][..]
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
of components.

    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.
  


Today's conclusions:

  * 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
    names.

  * 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
    state.





[Reply][About]
[<<][meta][>>][..]