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.