[Haskell-cafe] Help wanted: Lazy multiway zipper with mismached
chrisk at MIT.EDU
Mon Sep 26 13:23:11 EDT 2005
Rene de Visser wrote:
> I need to zip together multiple lists.
> The lists are sorted by date, and each entry in the list represents data
> for a time interval.
> The time intervals between the lists may be missmatched from each other.
Does a single list have only disjoint intervals? If not, then this it
is more annoying to write. If they are disjoint then it is straightforward.
> This means that sometimes you don't need to move forward in list, while
> you move forward in other lists. It might also mean that you need to
> skip a number of entries foward.
> If the computation does not need part of the contents of one of the
> lists, then this list should be ignored until it is needed.
> As the lists are sorted you never need to go backwards.
> I found it fairly easy to write a zipper for two lists, where the items
> from both lists are needed (example binary operator on the payload of
> the list).
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.
> 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"? 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?
> I though about if there was a away of encapsulating this in a monad, but
> haven't thought of any way to do this.
> Another idea is to have a mutable cursor for each list and move these
> forward as required. But I guess this might be worth avoiding?
> I think it would be good if somehow I could encapsulate each list, so on
> a per list basis, and can say given me the current head, or move one
> forward. But I haven't figured out how to pass the state of the other
> threads invisibly through.
> I guess the ony way might be to use the state monad?
> I guess there can be no simple recursive solution?
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe