On Thursday, 24 May 2012 at 13:15:30 UTC, Craig Dillabaugh wrote:
I am not sure if I entirely understand your problem, but would a
persistent search tree work? See:
http://www.sciencedirect.com/science/article/pii/002289900342
I have a small write up on them from a course I took years ago:
On Wednesday, 23 May 2012 at 22:39:33 UTC, Roman D. Boiko wrote:
On Wednesday, 23 May 2012 at 22:25:35 UTC, Steven Schveighoffer
wrote:
I looked up how it could be done, the one thing I was not sure
of was the parent node. If you can have multiple references
to the same subtree, how do you kee
On Wednesday, 23 May 2012 at 21:12:04 UTC, Jonathan M Davis wrote:
On Wednesday, May 23, 2012 20:51:31 Roman D. Boiko wrote:
On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon
wrote:
> On 23/05/2012 16:05, Roman D. Boiko wrote:
>
>
>> I need some immutable collections for my D Compiler
On Thursday, 24 May 2012 at 01:00:52 UTC, Jonathan M Davis wrote:
As part of my thesis work, I wrote a program which was counting
possible
tokens in code (as part of an AI attempting to learn about a
programming
language), which required a map of tokens to the number of
times that they'd
been s
On Wednesday, May 23, 2012 23:58:42 Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 21:12:04 UTC, Jonathan M Davis wrote:
> > In my personal experience, that's not true at all. I've seen
> > _huge_
> > performance problems in Haskell when using a map. There may be
> > cases where an
> > immuta
On Wednesday, 23 May 2012 at 23:51:45 UTC, bearophile wrote:
Roman D. Boiko:
The end goal is to have something as easy to work with as
collections of Scala or F# (I don't know Haskell), and, of
course, efficient.
If you plan in creating a start of purely functional
collections library then
Andrei Alexandrescu:
Yah, FP doesn't like arrays and immutable containers
essentially eschew arrays altogether.
In the Chapel/X10 worlds I have read about various strategies to
use mutable arrays too in parallel/concurrent situations.
Probably some of those ideas will be quite useful in D to
Roman D. Boiko:
The end goal is to have something as easy to work with as
collections of Scala or F# (I don't know Haskell), and, of
course, efficient.
If you plan in creating a start of purely functional collections
library then I suggest you to also take a look at Clojure and
various Hask
On Wednesday, 23 May 2012 at 22:25:35 UTC, Steven Schveighoffer
wrote:
I looked up how it could be done, the one thing I was not sure
of was the parent node. If you can have multiple references to
the same subtree, how do you keep track of the parents. But if
you only are concerned about the
On Wed, 23 May 2012 17:54:42 -0400, Roman D. Boiko wrote:
On Wednesday, 23 May 2012 at 19:51:02 UTC, Steven Schveighoffer wrote:
If you need a sorted tree structure that supports sharing immutable
state, you likely have to find a different algorithm than redblack,
since adding nodes can mod
On 5/23/12 1:54 PM, David Nadlinger wrote:
On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
When the tree is immutable, only lookup speed is of any real
relevance, so you might as well create a perfectly balanced binary
tree. Or even better, an array.
An array does not facilita
On Wednesday, 23 May 2012 at 21:12:04 UTC, Jonathan M Davis wrote:
In my personal experience, that's not true at all. I've seen
_huge_
performance problems in Haskell when using a map. There may be
cases where an
immutable container may not pose large performance problems,
but I would be
_very_
On Wednesday, 23 May 2012 at 19:51:02 UTC, Steven Schveighoffer
wrote:
If you need a sorted tree structure that supports sharing
immutable state, you likely have to find a different algorithm
than redblack, since adding nodes can modify the tree structure
via rotates.
-Steve
I don't need to
On Wednesday, 23 May 2012 at 21:13:48 UTC, Andrei Alexandrescu
wrote:
Okasaki put together the ultimate work on immutable data
structures. I have plans to add immutable collections to D
containers once I sort out the allocators matter.
Unfortunately, I find myself gasping for time so the news t
On 5/23/12 1:53 PM, Roman D. Boiko wrote:
On Wednesday, 23 May 2012 at 18:51:32 UTC, Roman D. Boiko wrote:
Immutable collections in most cases have the same performance
characteristics as mutable ones. Space consumption may be higher, but
not necessarily.
Instead of mutating a collection, a new
On Wednesday, May 23, 2012 20:51:31 Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
> > On 23/05/2012 16:05, Roman D. Boiko wrote:
> >
> >
> >> I need some immutable collections for my D Compiler Tools
> >> project, namely linked list,
> >> red-black tree,
On Wed, 23 May 2012 14:32:57 -0400, Roman D. Boiko wrote:
On Wednesday, 23 May 2012 at 18:24:28 UTC, simendsjo wrote:
On Wed, 23 May 2012 20:18:54 +0200, simendsjo
wrote:
On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko
wrote:
I need some immutable collections for my D Compiler Tool
On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
When the tree is immutable, only lookup speed is of any real
relevance, so you might as well create a perfectly balanced
binary tree. Or even better, an array.
An array does not facilitate sharing common subsets between
contain
On Wednesday, 23 May 2012 at 18:51:32 UTC, Roman D. Boiko wrote:
Immutable collections in most cases have the same performance
characteristics as mutable ones. Space consumption may be
higher, but not necessarily.
Instead of mutating a collection, a new one is returned each
time you add or re
On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
On 23/05/2012 16:05, Roman D. Boiko wrote:
I need some immutable collections for my D Compiler Tools
project, namely linked list,
red-black tree, and possibly some others.
What's the point of an immutable red-black tree?
The
On 23/05/2012 16:05, Roman D. Boiko wrote:
I need some immutable collections for my D Compiler Tools project, namely
linked list,
red-black tree, and possibly some others.
What's the point of an immutable red-black tree?
The whole point of a red-black tree is to facilitate fast dynamic addi
On Wednesday, 23 May 2012 at 18:24:28 UTC, simendsjo wrote:
On Wed, 23 May 2012 20:18:54 +0200, simendsjo
wrote:
On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko
wrote:
I need some immutable collections for my D Compiler Tools
project, namely linked list, red-black tree, and possibly
s
On Wednesday, 23 May 2012 at 18:18:55 UTC, simendsjo wrote:
On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko
wrote:
I need some immutable collections for my D Compiler Tools
project, namely linked list, red-black tree, and possibly some
others.
So I'm going to create them for my use, and l
On Wed, 23 May 2012 20:18:54 +0200, simendsjo wrote:
On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko
wrote:
I need some immutable collections for my D Compiler Tools project,
namely linked list, red-black tree, and possibly some others.
So I'm going to create them for my use, and late
On 23.05.2012 22:18, simendsjo wrote:
On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko wrote:
I need some immutable collections for my D Compiler Tools project,
namely linked list, red-black tree, and possibly some others.
So I'm going to create them for my use, and later generalize. I've
cr
On Wed, 23 May 2012 17:05:21 +0200, Roman D. Boiko wrote:
I need some immutable collections for my D Compiler Tools project,
namely linked list, red-black tree, and possibly some others.
So I'm going to create them for my use, and later generalize. I've
created a project on GitHub, but didn
On Wednesday, 23 May 2012 at 14:35:31 UTC, bearophile wrote:
Chris Dew:
Does D have "structural sharing" of its immutable collections?
i.e. Can I make a copy of an immutable Map or List collection
with an extra (or mutated) member, and will the returned (new)
collection share most of it's st
Thanks for your answer,
Chris.
On Wednesday, 23 May 2012 at 14:35:31 UTC, bearophile wrote:
Chris Dew:
Does D have "structural sharing" of its immutable collections?
i.e. Can I make a copy of an immutable Map or List collection
with an extra (or mutated) member, and will the returned (new)
Chris Dew:
Does D have "structural sharing" of its immutable collections?
i.e. Can I make a copy of an immutable Map or List collection
with an extra (or mutated) member, and will the returned (new)
collection share most of it's structure with the earlier
collection.
Currently Phobos doesn
Just some beginner questions...
Does D have "structural sharing" of its immutable collections?
i.e. Can I make a copy of an immutable Map or List collection
with an extra (or mutated) member, and will the returned (new)
collection share most of it's structure with the earlier
collection.
Th
30 matches
Mail list logo