Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Finding the lowest element greater or equal than (martin)
2. Re: Finding the lowest element greater or equal than
(Konstantine Rybnikov)
3. Re: Finding the lowest element greater or equal than
(Bob Ippolito)
----------------------------------------------------------------------
Message: 1
Date: Wed, 18 Mar 2015 22:49:50 +0100
From: martin <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Finding the lowest element greater or
equal than
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Hello all,
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.
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.
------------------------------
Message: 2
Date: Thu, 19 Mar 2015 00:07:27 +0200
From: Konstantine Rybnikov <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Finding the lowest element greater or
equal than
Message-ID:
<caabahfsxpzaa2uxawt00oph2fsy6kppb+3duhhxy6xjv31a...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Martin,
What you want depends on more details. If you just have a list of items,
you can access its first item which is less than some "n" by doing:
headMay (filter (< n) xs)
Would this solution satisfy you? If not -- what condition would not be met?
You mentioned something regarding that with ordered list you'd have to
traverse half of the list on average. What did you mean by that? (I mean,
if you have ordered list, then either its first element is what you need,
or none of them are)
On Wed, Mar 18, 2015 at 11:49 PM, martin <[email protected]> wrote:
> Hello all,
>
> 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.
>
> 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.
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150319/960841de/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 18 Mar 2015 15:42:09 -0700
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Finding the lowest element greater or
equal than
Message-ID:
<cacwmpm_j69eyqws_a-_oxv7o2ct2fw6n8ajqqqtkcqcjq24...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Wed, Mar 18, 2015 at 2:49 PM, martin <[email protected]> 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-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 81, Issue 50
*****************************************
