Re: [Haskell-cafe] Destructive updates to plain ADTs
Hi, is there any way to perform a destructive update on a plain ADT? Hi Milan, perhaps this is a dumb question, but given that you're using a lazy functional language: why do you want to do destructive updates at all? Perhaps you'd be better off using an imperative/object-oriented language? I am one of the maintainers of the containers package, so I definitely want to stick to Haskell :) The reason for me wanting to do destructive updates is speed -- if I could perform destructive updates during the construction of persistent structure (e.g., inside Data.Map.fromList), the performance would improve. ... I would like just to run some benchmarks and see the results. Running benchmarks for destructive updates in Haskell seems a waste of time(?) Johan successfully improved unordered-containers by using destructive updates during construction, but he is using Array# where destructive updates are possible. I was wondering if I could do similar thing in containers... Cheers, Milan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Destructive updates to plain ADTs
Hi all, is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree. I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type. At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results. Cheers, Milan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Destructive updates to plain ADTs
On Sun, Sep 9, 2012 at 1:46 AM, Milan Straka f...@ucw.cz wrote: Hi all, is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree. I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type. At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results. Cheers, Milan You can do it if you refer to the children using Array#s. That's what I do in unordered-containers to implement a more efficient fromList. For arbitrary field types I don't think there's a way (although it would be useful when birthing persistent data structures). -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Destructive updates to plain ADTs
Why modify it instead of creating the new one and let the previous tree get garbage collected? On Sep 9, 2012, at 12:46 PM, Milan Straka f...@ucw.cz wrote: Hi all, is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree. I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type. At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results. Cheers, Milan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Destructive updates to plain ADTs
On Sun, Sep 9, 2012 at 2:19 AM, MigMit miguelim...@yandex.ru wrote: Why modify it instead of creating the new one and let the previous tree get garbage collected? You can avoid a bunch of copying and allocation by modifying the nodes in-place. See http://blog.johantibell.com/2012/03/improvements-to-hashmap-and-hashset.html for some numbers. -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Destructive updates to plain ADTs
is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree. I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type. At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results. Cheers, Milan You can do it if you refer to the children using Array#s. That's what I do in unordered-containers to implement a more efficient fromList. But the Array# adds another level of indirection, which seem wasteful if it has 2 elements. Also creating and cloning array is calling method in runtime, which is another source of (minor) slowdown. For arbitrary field types I don't think there's a way (although it would be useful when birthing persistent data structures). That is my reason for asking this. I was hoping for some Addr# trick or something like that. If I understand the GHC runtime correctly, rewriting a pointer in an ADT should not break any garbage collecting and similar. Cheers, Milan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Destructive updates to plain ADTs
On 09/09/2012 11:03, Milan Straka wrote: I was hoping for some Addr# trick or something like that. If I understand the GHC runtime correctly, rewriting a pointer in an ADT should not break any garbage collecting and similar. Don't you need to worry about having something in the old generation suddenly pointing to something in a younger generation? Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Destructive updates to plain ADTs
Milan Straka fox at ucw.cz writes: is there any way to perform a destructive update on a plain ADT? Hi Milan, perhaps this is a dumb question, but given that you're using a lazy functional language: why do you want to do destructive updates at all? Perhaps you'd be better off using an imperative/object-oriented language? If you're trying to create a static data structure, perhaps the credit card transform is the approach to use? ... I would like just to run some benchmarks and see the results. Running benchmarks for destructive updates in Haskell seems a waste of time(?) AntC ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
