Here's an infinite structure with logarithmic access time with natural
numbers for keys.
It's not particularily efficient for a sparse map, but if the maximum
used key is linear in the size of your problem, it gives log(n) access
time.
However, an infinite fold of insert is still _|_; you have
On Wed, Oct 22, 2008 at 3:14 AM, Ryan Ingram [EMAIL PROTECTED] wrote:
Here's an infinite structure with logarithmic access time with natural
numbers for keys.
It's not particularily efficient for a sparse map, but if the maximum
used key is linear in the size of your problem, it gives log(n)
Ideas for how to make such tries
composable would encourage me to release a hackage module :-)
Have a look at code.haskell.org/gmap/api - a library for composable
maps. It currently requires huge instances in the name of efficiency
but I hope to improve that over the next couple of months. The
Hi, I need a rather strange data structure, and I can't find any
existing implementations or think of a way to implement it. It's a
multiqueue, basically a map of queues. The trick is that it should
be lazy in its spine and still support efficient access. For example,
the following should hold:
On Tue, Oct 21, 2008 at 11:43 AM, Luke Palmer [EMAIL PROTECTED] wrote:
Hi, I need a rather strange data structure, and I can't find any
existing implementations or think of a way to implement it. It's a
multiqueue, basically a map of queues. The trick is that it should
be lazy in its spine
On Tue, Oct 21, 2008 at 3:02 PM, Justin Bailey [EMAIL PROTECTED] wrote:
On Tue, Oct 21, 2008 at 11:43 AM, Luke Palmer [EMAIL PROTECTED] wrote:
Hi, I need a rather strange data structure, and I can't find any
existing implementations or think of a way to implement it. It's a
multiqueue,
On 10/21/08, Luke Palmer [EMAIL PROTECTED] wrote:
Well, first, my question was highly malformed. I actually just want a
spine lazy map of lists; queues were not what I wanted.
[...]
The best I've come up with so far is a binary search tree where the
most recently inserted thing is at the
On Wed, 22 Oct 2008 11:54:50 Luke Palmer wrote:
On Tue, Oct 21, 2008 at 3:02 PM, Justin Bailey [EMAIL PROTECTED] wrote:
On Tue, Oct 21, 2008 at 11:43 AM, Luke Palmer [EMAIL PROTECTED] wrote:
Hi, I need a rather strange data structure, and I can't find any
existing implementations or think