[Haskell-cafe] Optimization problem
Magnus Jonsson
magnus at smartelectronix.com
Thu Sep 14 09:06:11 EDT 2006
On Thu, 14 Sep 2006, Ketil Malde wrote:
> Magnus Jonsson <magnus at smartelectronix.com> writes:
>
>> splitStreams::Ord a=>[(a,b)]->[(a,[b])]
>
>>> splitStreams [(3,x),(1,y),(3,z),(2,w)]
>> [(3,[x,z]),(1,[y]),(2,[w])]
>
> [...]
>
>> But is there any way to write it such that each element is touched
>> only once? Or at least an O(n*log(m)) algorithm?
>
> I guess it should be possible to use a quicksort-like algorithm,
> splitting the stream into three streams with keys less than, equal,
> and greater than the first element, and recurse on the less/equal
> streams?
>
> -k
>
That is probably the best we can do. I think in a hypothetical concurrent
Haskell with futures/promises, the split stream problem could be solved.
But if it can be solved in regular Haskell, I would be pleasantly
surprised.
/ Magnus
More information about the Haskell-Cafe
mailing list