[Haskell-cafe] Optimization problem

[Bruno Oliveira]

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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20060914/a7142e74/attachment-0001.htm