Large data structures

newer
Type problem with simple takusen...

Alex Queiroz

11 Dec 2006 11 Dec '06

8:27 p.m.

Hi all, I'm considering the use of Haskell to manipulate large data structures for Computer Graphics (large geometric datasets). I'm wondering what's the best way to do it. As "objects" (not in the OO sense) in Haskell are immutable, how can I add a vertex to a large mesh without using obscene amounts of memory? Making an analogy:

...

enlarge :: a -> [a] -> [a] enlarge c cs = c : cs

enlarge 15 [1..100000]

Will this copy the whole list to make a new one with an element more? Cheers, -- -alex http://www.ventonegro.org/

Show replies by date

Stefan O'Rear

11 Dec 11 Dec

8:33 p.m.

On Mon, Dec 11, 2006 at 10:27:44PM -0300, Alex Queiroz wrote:

...

Hi all,

I'm considering the use of Haskell to manipulate large data structures for Computer Graphics (large geometric datasets). I'm wondering what's the best way to do it. As "objects" (not in the OO sense) in Haskell are immutable, how can I add a vertex to a large mesh without using obscene amounts of memory? Making an analogy:

...
enlarge :: a -> [a] -> [a] enlarge c cs = c : cs

enlarge 15 [1..100000]

Will this copy the whole list to make a new one with an element more?

No. Haskell's lists are linked lists, enlarge creates a single new link without modifying (and copying) the original.

Alex Queiroz

8:35 p.m.

Hallo, On 12/11/06, Stefan O'Rear wrote:

...

No. Haskell's lists are linked lists, enlarge creates a single new link without modifying (and copying) the original. _______________________________________________

Thanks. Is there a way to mimic this behaviour with my own code? Cheers, -- -alex http://www.ventonegro.org/

Matthew Brecknell

8:53 p.m.

...

...
No. Haskell's lists are linked lists, enlarge creates a single new link without modifying (and copying) the original.

Thanks. Is there a way to mimic this behaviour with my own code?

Yes. Take a look at Data.Map. This data structure provides various operations which create a new map from an old one in O(log n) time, by splicing bits of the old map into the new one. Importantly, performing any of these operations does not destroy the old map if your code still references it. On the other hand, if your code drops references to the old map, then the garbage collector can reclaim any branches of the old map not used in the new one. You may also be interested in this paper: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Alex Queiroz

12 Dec 12 Dec

7:21 a.m.

Hallo, On 12/11/06, Matthew Brecknell wrote:

...

Yes. Take a look at Data.Map. This data structure provides various operations which create a new map from an old one in O(log n) time, by splicing bits of the old map into the new one. Importantly, performing any of these operations does not destroy the old map if your code still references it. On the other hand, if your code drops references to the old map, then the garbage collector can reclaim any branches of the old map not used in the new one. You may also be interested in this paper:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Thanks for the info and the link, looks interesting. Cheers, -- -alex http://www.ventonegro.org/

Benjamin Franksen

11 Dec 11 Dec

9:07 p.m.

Alex Queiroz wrote:

...

On 12/11/06, Stefan O'Rear wrote:

...
No. Haskell's lists are linked lists, enlarge creates a single new link without modifying (and copying) the original. Thanks. Is there a way to mimic this behaviour with my own code?

It is the default for any data structure you define. Data is by default represented internally as a pointer to the actual value. Otherwise recursive structures (see below for an example) would not be easily possible. And since no part of the data structure is 'mutable', different instances can share (memory-wise) as much of their structure as the implementation is able to find. BTW apart from the special syntax (like [a,b,c]) there is nothing special about lists. E.g. with this data type definition data List a = Nil | Cons a (List a) (List a) is completely equivalent to [a]. HTH Ben PS: Please try to include exactly the relevant context in replies, no more, no less. Your original question (stripped down to the body of the text) would have been relevant, here, but neither 'Hello', nor 'Cheers' are worth quoting.

Alex Queiroz

12 Dec 12 Dec

7:25 a.m.

Hallo, On 12/12/06, Benjamin Franksen wrote:

...

Alex Queiroz wrote:

...
On 12/11/06, Stefan O'Rear wrote:

...
No. Haskell's lists are linked lists, enlarge creates a single new link without modifying (and copying) the original. Thanks. Is there a way to mimic this behaviour with my own code?

It is the default for any data structure you define. Data is by default represented internally as a pointer to the actual value. Otherwise recursive structures (see below for an example) would not be easily possible. And since no part of the data structure is 'mutable', different instances can share (memory-wise) as much of their structure as the implementation is able to find.

Ok, I think I got it now. :-)

...

PS: Please try to include exactly the relevant context in replies, no more, no less. Your original question (stripped down to the body of the text) would have been relevant, here, but neither 'Hello', nor 'Cheers' are worth quoting.

Sorry, but I did not quote "hello" or "cheers". -- -alex http://www.ventonegro.org/

Benjamin Franksen,15.8.202,6392-4982,

13 Dec 13 Dec

9:21 a.m.

Alex Queiroz wrote:

...

On 12/12/06, Benjamin Franksen wrote:

...
PS: Please try to include exactly the relevant context in replies, no more, no less. Your original question (stripped down to the body of the text) would have been relevant, here, but neither 'Hello', nor 'Cheers' are worth quoting.

Sorry, but I did not quote "hello" or "cheers".

Oops. My turn to say 'sorry'. No offense meant... Cheers Ben

6735

Age (days ago)

6736

Last active (days ago)

List overview

Download

7 comments

5 participants

participants (5)

Alex Queiroz
Benjamin Franksen
Benjamin Franksen,15.8.202,6392-4982,
Matthew Brecknell
Stefan O'Rear