[Haskell-cafe] Optimization problem
bruno.oliveira at comlab.ox.ac.uk
Thu Sep 14 14:03:24 EDT 2006
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
On Thu, 14 Sep 2006 13:11:05 -0400 (EDT), Magnus Jonsson wrote:
>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.
>On Thu, 14 Sep 2006, Bruno Oliveira wrote:
>> 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
>> *General7> lookUp fin 2
>> *General7> lookUp fin 3
>> 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)
>> Bruno Oliveira
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe