Hello Magnus, You are right. Silly me. I was thinking of Rel as a kind of Hashtable. In this case, I think it should be possible to have O(n), since "cons" would only need constant time. Cheers, Bruno On Thu, 14 Sep 2006 13:11:05 -0400 (EDT), Magnus Jonsson wrote:
Thanks Bruno.
However I think this is still O(n*m). As far as I understand your code it is a longwinded way to say "[b | (a,b) <- input, b == myChannelOfInterest]". This is fine if you are only interested in one channel, and for that case I agree it's O(n), but if you are interested in many different channels, it will take O(n*m). Here's why I think your code is equivalent to using a filter/list-comprehension:
cons :: Eq a => (a,b) -> Rel a b -> Rel a b cons (x,y) l z | x == z = y : l x | otherwise = l z
z is the channel that the user is interested in. x is the channel of the current message in the list. y is the message content. l is a function for searching the rest of the list.
For each element of the list you create a function that compares the requested channel to a (in (a,b)). If it's the same, you return that element followed by a continued search down the list. If you don't find it, you forward the request to the next function down the list. That's exactly the same as what the filter function does.
It is possible I made a mistake somewhere and if I did, let me know.
/ Magnus
On Thu, 14 Sep 2006, Bruno Oliveira wrote:
Hello,
I think it is possible to do it in O(n) (if you change the representation of the output stream).
Note that the solution is quite similar toTwan van Laarhoven, and it should be trivial use "Map" instead of "Rel".
Here is my take on it:
The type of the output stream:
type Rel a b = a -> [b]
Here are cons and nil:
nil :: Rel a b nil _ = []
and a lookUp function:
lookUp :: Rel a b -> a -> [b] lookUp = id
Finally the splitStreams algorithm:
splitStreams :: Eq a => [(a,b)] -> Rel a b splitStreams = foldr cons nil
Here is a test with finite lists:
fin = splitStreams [(3,'x'),(1,'y'),(3,'z'),(2,'w')]
and here are the console tests:
*General7> lookUp fin 1 "y" *General7> lookUp fin 2 "w" *General7> lookUp fin 3 "xz"
Now with infinite lists:
inf = splitStreams (map (\x -> (0, x)) [1..])
and here a case where it terminates with infinite lists:
*General7> take 10 (lookUp inf 0) [1,2,3,4,5,6,7,8,9,10]
Cheers,
Bruno Oliveira
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe