[Haskell-cafe] Optimization problem
Bruno Oliveira
bruno.oliveira at comlab.ox.ac.uk
Thu Sep 14 12:47:00 EDT 2006
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:
> cons :: Eq a => (a,b) -> Rel a b -> Rel a b
> cons (x,y) l z
> | x == z = y : l x
> | otherwise = l z
> 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
More information about the Haskell-Cafe
mailing list