[Haskell-cafe] Optimization problem

[Magnus Jonsson]

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
>