fold/unfold and friends
Henry Cejtin
henry@sourcelight.com
Thu, 27 Sep 2001 16:54:36 -0500
Here is my recollection: Some times you are consuming container elements
(fold) and some times you are producing them (unfold). We have both now. An
orthogonal choice is who owns the stack. Who ever owns the stack has to be
the procedure that does the looping. In the consumer case, fold owns the
stack. The other choice here would be like C++ iterators where there would
be a routine I could call which would give me the next element (of the list
or what ever). The notion is that just like fold passes around a state to
make up for the fact that the folder doesn't have the stack, here the person
calling the procedure which returns the next element would maintain its
state.
The result is that you have an iterator whose type is like the StringCvt
reader type. I.e., the iterator take a state as input and returns an
(element * state) option
as a result.
The analogue of unfold (produce a container with the code which is providing
the elements owning the stack) I need a function to call with different
elements to insert in the container.
Your notion was for the unfold case, and you would call a procedure no-stack-
unfold which would take a function as an argument. It would call the
function (ONLY ONCE) passing it the initial state and the function it can
call for inserting elements. Now when that function returns, the no-stack-
unfold would assume (checking of course) that all elements were in place, do
what ever clean up was needed and return the container.
I remember you said that you didn't think that HM types were going to be
general enough to make things polymorphic in this way, so that the structure
which exported the no-stack-unfold procedure would also export the type which
is maintaining the iterator state.
The great thing about this that you can now do parallel traversals of more
than one list for instance (by doing a fold with each call of the folder
doing one call of the no-stack-fold iterator.
Again, it is VERY VERY important that who ever has the stack threads a state
through for who ever does NOT have the stack.
Sorry, I just read the do-not-read-before-CVS now.