haskell / vector

An efficient implementation of Int-indexed arrays (both mutable and immutable), with a powerful loop optimisation framework .
Other
360 stars 141 forks source link

Add strict vector #488

Closed Shimuuar closed 5 months ago

Shimuuar commented 6 months ago

Fixes #483 and #380

Implementation follows discussion in issues above and virtually identical to one in strict-containers. Only difference fromArray and unsafeFromArraySlice now force all elements of returned vector to WHNF. It changes complexity to O(n) so to compensate lazyFromArray and unsafeLazyFromArraySlice are added, they retain O(1) complexity but user has to deal with strictness.

This is draft since there's still some work to do with documentation.

  1. We need to decide to prefix to use in examples. V. is used by lazy vector, VS by storable. One option
  2. I think it would be better to switch examples in generic vector to strict vector. It's better default data structure
  3. It's worth making a new release soon after this PR is merged, so I think I should just slap @since 0.13.2.0 on each function in Strict modules

Also

Shimuuar commented 6 months ago

At this point PR is pretty much ready

Bodigrim commented 6 months ago

@infinity0 could you possibly review?

Shimuuar commented 6 months ago

Basically it's same as version from strict-containers. Only differences are strict fromArray & fromMutableArray, added lazyFromArray and haddocks.

I also switched examples in D.V.Generic to strict vectors but that's purely documentation change

Shimuuar commented 6 months ago

@Bodigrim switching to a newtype worked out quite well and allowed to drop a lot of duplicated code. It doesn't work all that well for instances since DerivingStrategies are only available since 8.2. So it's not possible to instruct GHC to derive say Ord.

I also added function for conversion between strict and lazy vectors.

Shimuuar commented 6 months ago

I removed function that don't enforce strictness: lazyFromLazy, etc.

Shimuuar commented 5 months ago

I'm going to merge this PR on next weekend if there are no objections