[Haskell-cafe] ANNOUNCE: persistent-vector-0.1.0.1
I uploaded a package implementing persistent vectors using array mapped tries (based on the implementation in clojure). Version 0.1.0.0 was broken, so I am starting off with 0.1.0.1. http://hackage.haskell.org/package/persistent-vector Persistent vectors are a sequence container offering efficient and purely functional append (snoc), indexing, and updates. This is similar to Data.Sequence from containers. The array mapped trie is closely related to the data structure used in the unordered-containers package. Comparison to Sequence: * Faster indexing and append * Slightly slower updates to existing elements * O(1) slicing * Sequence offers efficient prepend and concatenate (persistent-vector does not implement prepend, while concatenate is O(n)). I tried to model the API after Sequence as much as was reasonable, but a few functions are still missing. Some are reasonable to implement and some would be difficult to make efficient. The results from criterion (mostly comparing against Sequence and IntMap) are posted here: http://pages.cs.wisc.edu/~travitch/pvec.html The *Vec* runs are the vectors from this package and IM and Seq are IntMap and Sequence from containers. Hopefully someone will find this useful. Comments and suggestions are definitely welcome for anything: API, implementation, test suite, or benchmarks. pgpGGufATcanJ.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: persistent-vector-0.1.0.1
Where the "persistent" part of the name comes from?. It can be serialized/deserialized from a persistent storage automatically or on demand? 2012/8/29 Tristan Ravitch > I uploaded a package implementing persistent vectors using array > mapped tries (based on the implementation in clojure). Version > 0.1.0.0 was broken, so I am starting off with 0.1.0.1. > > http://hackage.haskell.org/package/persistent-vector > > Persistent vectors are a sequence container offering efficient and > purely functional append (snoc), indexing, and updates. This is > similar to Data.Sequence from containers. The array mapped trie > is closely related to the data structure used in the > unordered-containers package. > > Comparison to Sequence: > > * Faster indexing and append > > * Slightly slower updates to existing elements > > * O(1) slicing > > * Sequence offers efficient prepend and concatenate >(persistent-vector does not implement prepend, while concatenate is >O(n)). > > I tried to model the API after Sequence as much as was reasonable, but > a few functions are still missing. Some are reasonable to implement > and some would be difficult to make efficient. The results from > criterion (mostly comparing against Sequence and IntMap) are posted > here: > > http://pages.cs.wisc.edu/~travitch/pvec.html > > The *Vec* runs are the vectors from this package and IM and Seq are > IntMap and Sequence from containers. > > > Hopefully someone will find this useful. Comments and suggestions are > definitely welcome for anything: API, implementation, test suite, or > benchmarks. > > ___ > 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] ANNOUNCE: persistent-vector-0.1.0.1
On Wed, Aug 29, 2012 at 10:13 AM, Alberto G. Corona wrote: > Where the "persistent" part of the name comes from?. It can be > serialized/deserialized from a persistent storage automatically or on > demand? Persistent have two meanings unfortunately. In functional programming it's used to mean that every operation on a data structure preserves the old version as well. -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: persistent-vector-0.1.0.1
Sorry, persistent as in purely functional. Updates to one vector don't affect others. I guess the distinction isn't as useful in Haskell as it is in other languages since it is the default. On Wed, Aug 29, 2012 at 07:13:38PM +0200, Alberto G. Corona wrote: > Where the "persistent" part of the name comes from?. It can be > serialized/deserialized from a persistent storage automatically or on > demand? > > 2012/8/29 Tristan Ravitch > > > I uploaded a package implementing persistent vectors using array > > mapped tries (based on the implementation in clojure). Version > > 0.1.0.0 was broken, so I am starting off with 0.1.0.1. > > > > http://hackage.haskell.org/package/persistent-vector > > > > Persistent vectors are a sequence container offering efficient and > > purely functional append (snoc), indexing, and updates. This is > > similar to Data.Sequence from containers. The array mapped trie > > is closely related to the data structure used in the > > unordered-containers package. > > > > Comparison to Sequence: > > > > * Faster indexing and append > > > > * Slightly slower updates to existing elements > > > > * O(1) slicing > > > > * Sequence offers efficient prepend and concatenate > >(persistent-vector does not implement prepend, while concatenate is > >O(n)). > > > > I tried to model the API after Sequence as much as was reasonable, but > > a few functions are still missing. Some are reasonable to implement > > and some would be difficult to make efficient. The results from > > criterion (mostly comparing against Sequence and IntMap) are posted > > here: > > > > http://pages.cs.wisc.edu/~travitch/pvec.html > > > > The *Vec* runs are the vectors from this package and IM and Seq are > > IntMap and Sequence from containers. > > > > > > Hopefully someone will find this useful. Comments and suggestions are > > definitely welcome for anything: API, implementation, test suite, or > > benchmarks. > > > > ___ > > Haskell-Cafe mailing list > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > pgpyRTf9uZFKs.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
