Tristan Ravitch | 29 Aug 18:46 2012
Picon

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:

(Continue reading)

Alberto G. Corona | 29 Aug 19:13 2012
Picon

Re: 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 <travitch <at> cs.wisc.edu>
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 <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Johan Tibell | 29 Aug 19:16 2012
Picon

Re: ANNOUNCE: persistent-vector-0.1.0.1

On Wed, Aug 29, 2012 at 10:13 AM, Alberto G. Corona <agocorona <at> gmail.com> 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
Tristan Ravitch | 29 Aug 19:17 2012
Picon

Re: 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 <travitch <at> cs.wisc.edu>
>
> > 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 <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane