[Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals

ChrisK chrisk at MIT.EDU
Mon Sep 26 15:30:22 EDT 2005

Rene de Visser wrote:
>> From: ChrisK <chrisk at MIT.EDU>
>> Rene de Visser wrote:
>> Does a single list have only disjoint intervals?
> Yes. The lists are strictly increasing

Could the interval for element x of List xList overlap with more than
one element of another list?  It does not matter too much, but is
something you did not clarify.  In general, how may the intervals for
all the lists overlap?  (The answer may be too complex, in which case
you can just ignore me).

Given all this complexity, you would be served by making an intermediate
list with time-ordered group events. (This is like the tuple of Maybe
type that was suggested, but more specialized to your problem.)

I would start by merging, perhaps in stages, into an intermediate list
with elements of its own "data FooIntermediate = A _ [_]| B  _ [(_,_)] |
C _ _ _ | ..." types.

This would name and catergorize your kinds of events into different A B
C constructors.  This clarity helped me create the intermediate stages
for one of my programs, and it helped separate the stages of processing.

Once you solve that merging (correctly), the rest of the functions
should be easier to write.  Debugging this merging is now independent of
 all the (recursive) processing functions, which hopefully only need a
"case...of" expression to decide what to do.

If you need to change the semantics of merging the streams then it may
help when you refactor that the types of events are now types of
constructors and the compiler is checking your code.

>> Doing this for two lists with a recursive function is easy. There being
>> an output element whenever the intervals of the two input lists overlap.
> Yes, I have done this.
>> > However the combination of merging multiple lists together, and
>> ignoring
>> > a list in the case it is not needed by the computation leads to very
>> > messy code.
>> >
>> Do mean multiple as in "at least three"?
> Yes
>>  If so, then what do have an
>> output element only if all three or more input elements overlap, or do
>> you have an output element when at least two input elements overlap?
> That can depend on the values (payloads) per entry. For example I might
> have a selector operator and one of the lists steers from which of the
> other lists I should take the value for that interval.
> I think a continuation per list would provide a nice solution.
> But I don't know how to do that, and it might be horribly ineffecient?
> Rene.

More information about the Haskell-Cafe mailing list