[Haskell-beginners] Finding the lowest element greater or equal than

[Bob Ippolito]

On Wed, Mar 18, 2015 at 2:49 PM, martin <martin.drautzburg at web.de> wrote:

>
> I want to find the lowest element in a collection of items which is
> greatet or equal to a given element. There can be
> more than one such element in which case I wouldn't care which one I get.
> I still want to be able to iterate over the
> elements following the found element. In a way I want the equivalent of
>
> select ...
> from table
> where table.x > n
>
>
> How would I do this efficiently?
>
> I tried using an ordered list, but I would still have to traverse half the
> list on average.
>

You could do it in log time (using a binary search algorithm) with an
ordered Vector or Array. Lists are not an appropriate data structure for
random access.


> I suppose I can do this with some sort of tree, but i don't want to write
> all the code myself. But I couldn't find
> anything off the shelf.
>

Data.Map supports that operation in log time with splitLookup. You can use
the values of the map to count the occurrences of a given element. If all
of the elements are unique you can save a bit of space and use Data.Set
instead, which has a splitMember function.

-bob
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150318/d58b342b/attachment.html>