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