Re: [Haskell-cafe] Proposal: Partitionable goes somewhere + containers instances
Hi Ryan, > -Original message- > From: Ryan Newton > Sent: 29 Sep 2013, 04:21 > > > > *class Partitionable t where* > * partition :: t -> Maybe (t,t)* > > > > So what I really want is for the *containers package to please get some > kind of Partitionable instances! * Johan & others, I would be happy to > provide a patch if the class can be agreed on. This is important because > currently the balanced tree structure of Data.Set/Map is an *amazing and > beneficial property* that is *not* exposed at all through the API. Some comments: 1) containers are a boot package (http://ghc.haskell.org/trac/ghc/wiki/Commentary/Libraries) therefore its dependencies have to be boot packages too. If Partitionable gets into base or some other boot package, fine :) 2) IntMap/IntSet have different partitioning operation than Map/Set: partition :: IntMap a -> Either IntMap (IntMap a, IntMap) partition :: Map k v -> Either Map (Map, k, v, Map) Nevertheless, IntMap/IntSet are not well balanced, so maybe it would be fine to have partition working for Map/Set. 3) Partition somehow exposes internal structure, which forces us to only some implementations. Nevertheless, I doubt the representation of containers will change wildly (although I am planning to add data constructor to Map/Set shortly, so you never know). It seems that the best course of action would be to ignore the Partitionable class and instead provide methods in the containers to allow splitting. The question is how should the API look like. Currently IntMap and IntSet are deliberately as close to Map and Set as possible. Introducing this splitting operation would enlarge the difference between them. But as noted, we could provide split only for Map and Set, as IntMap/IntSet are not well balanced anyway. 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
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
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
[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] A paper relating to Data.Set and Data.Map
Hi Kazu and all,
> Hello libraries and cafe,
>
> We (Hirai and I) would like to tell you our paper relating to
> Data.Set and Data.Map. "Balancing Weight-Balanced Trees" is now
> accepted and will appear in Journal of Functional Programming.
> The camera-ready version of the paper is available from:
>
> http://www.mew.org/~kazu/proj/weight-balanced-tree/
>
> Please recall that Taylor Campbell reported a bug of Data.Map in last
> Summer. In some cases, the balance of Data.Map is broken after delete
> operations. This triggered our research.
>
> http://article.gmane.org/gmane.comp.lang.haskell.libraries/13444
>
> Though Data.Set/Data.Map are based of a variant Weight-Balanced tree
> by Adams, we target the original Weight-Balanced tree by Nievergelt
> and Reingold. They are parameterized algorithms and the difference of
> two algorithms is quite small. But the original has smaller conditions
> which are gentle for proof.
>
> We identified the valid area of two parameters of the original
> Weight-Balanced tree and showed <3,2> is only one integer solution.
> Soundness is proved in Coq and completeness is verified with four
> algorithms to generate counterexamples for the outside of the valid
> area.
>
> "wttree.scm" of MIT/GNU Scheme and slib have already incorporated our
> fixes. When I offered our fixes to MIT/GNU Scheme, Taylor Campbell
> appeared again. I understand that he is an MIT/GNU Scheme guy and
> found the bug of Data.Map when re-implementing "wttree.scm" consulting
> Data.Map. :-)
>
> We think it's Haskell community turn now. Data.Set/Data.Map are still
> based on the variant whose soundness is not proved yet. If interested,
> let's discuss whether or not we should replace the variant with the
> original in Data.Set/Data.Map.
>
> We guess that Milan Straka, a big contributer of the container
> package, has his opinion. We welcome opinions from other people, two.
I wrote a paper containing the proof of correctness of Adams' trees and
therefore of Data.{Set,Map}. The paper got accepted to the TFP 2011. The
draft is available at http://fox.ucw.cz/papers/bbtree/ . That should
settle the question of soundness of the current implementation.
The analysis and the benchmark included in the paper suggest to use
different representation and parameters for best performance -- I will
submit patches soon.
One nice side-effect is that just by reordering the constructors of
Data.IntSet and Data.IntMap, I got 10% and 9% speedup (measured with
the containers-benchmark package). These changes will be part of the
patches I am going to make. (See the pages 13 and 14 of the paper
for some discussion about this phenomenon.)
Cheers,
Milan Straka
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
