Help wanted: Lazy multiway zipper with mismached intervals

Rene de Visser

26 Sep 2005 26 Sep '05

4:14 p.m.

Hello, 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. 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). 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. 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? Rene.

Show replies by date

ChrisK

26 Sep 26 Sep

5:23 p.m.

Rene de Visser wrote:

...

Hello,

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?

Rene.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Rene de Visser

6:17 p.m.

...

From: ChrisK Rene de Visser wrote: Does a single list have only disjoint intervals? Yes. The lists are strictly increasing 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.

ChrisK

7:30 p.m.

Rene de Visser wrote:

...

...
From: ChrisK 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.

Rene de Visser

27 Sep 27 Sep

2:42 p.m.

Many thanks to all for the replies

...

From: ChrisK

...

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).

Yes, unlimited overlap is possible. e.g. Infinite interval in one list, and infinitely many small intervals in another list.

...

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

Yes, I'll probably use this suggestion, maybe with records to make partial update easier.

...

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. Originally I had thought that I could treat the merge symetrically, but I now think this is not the case. Still I am not sure if I will use different types for different types of merge.

Rene.

Marcin Tustin

26 Sep 26 Sep

7:53 p.m.

Perhaps I am being obtuse, but why would you need to pass a continuation for each list, rather than just passing the list? If the head does not encapsultate all relevant infromation about the list, could you not wrap the list with another datastructure, which you update (pass a derived version of) at each iteration? On Mon, Sep 26, 2005 at 08:17:10PM +0200, Rene de Visser wrote:

...

...
From: ChrisK Rene de Visser wrote: Does a single list have only disjoint intervals? Yes. The lists are strictly increasing 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.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Robin Green

6:28 p.m.

On Monday 26 September 2005 17:14, Rene de Visser wrote:

...

Hello,

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.

Is this the sort of thing you want? module Main where data Event = Event { time :: Int, what :: String } deriving (Eq, Show) zipToMaybes :: [Event] -> [Event] -> [(Maybe Event, Maybe Event)] zipToMaybes [] [] = [] zipToMaybes [] (h:t) = ((Nothing, Just h):(zipToMaybes [] t)) zipToMaybes (h:t) [] = ((Just h, Nothing):(zipToMaybes t [])) zipToMaybes (ha:ta) (hb:tb) | (time ha) == (time hb) = ((Just ha, Just hb):(zipToMaybes ta tb)) | (time ha) < (time hb) = ((Just ha, Nothing):(zipToMaybes ta (hb:tb))) | otherwise = ((Nothing, Just hb):(zipToMaybes (ha:ta) tb)) main = interact $ const $ show $ zipToMaybes [Event 0 "Got up", Event 1 "Had breakfast", Event 3 "Went to work"] [Event 0 "Got up", Event 2 "Went to work"]

John Meacham

6:41 p.m.

Why not have a merging function which takes all lists and merges them into a single ordered list marked with which list the events came from and their timestamps. Then you can just traverse this single, merged list. if I am understanding the problem properly... John -- John Meacham - ⑆repetae.net⑆john⑈

John Meacham

6:42 p.m.

Doh! ignore me. apparently I understand the problem, but offer nothing in the way of solution. :) John -- John Meacham - ⑆repetae.net⑆john⑈

Henning Thielemann

27 Sep 27 Sep

10:25 a.m.

On Mon, 26 Sep 2005, Rene de Visser wrote:

...

Hello,

I need to zip together multiple lists.

I would write a function 'merge' which merges two lists. Multiple list can be merged with 'foldl merge []'.

...

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.

This sounds like the merge step performed in Haskore which merges two sequences of time-ordered (music) notes. With absolute time stamps: (search for 'merge') http://cvs.haskell.org/darcs/haskore/src/Haskore/General/Utility.lhs With relative time stamps: http://cvs.haskell.org/darcs/haskore/src/Haskore/Performance.lhs

7222

Age (days ago)

7223

Last active (days ago)

List overview

Download

9 comments

6 participants

participants (6)

ChrisK
Henning Thielemann
John Meacham
Marcin Tustin
Rene de Visser
Robin Green