Re: [Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
Many thanks to all for the replies From: ChrisK [EMAIL PROTECTED] 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
From: ChrisK [EMAIL PROTECTED] 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
Re: [Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
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]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
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⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help wanted: Lazy multiway zipper with mismached intervals
Doh! ignore me. apparently I understand the problem, but offer nothing in the way of solution. :) John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
