slist
Sized list
https://github.com/kowainik/slist
Version on this page: | 0.2.1.0 |
LTS Haskell 22.39: | 0.2.1.0@rev:1 |
Stackage Nightly 2024-11-02: | 0.2.1.0@rev:1 |
Latest on Hackage: | 0.2.1.0@rev:1 |
slist-0.2.1.0@sha256:112636a7190044f3dc1e09b2c69154ef37ff7f8595ddde1215ffa94a64858b13,3501
Module documentation for 0.2.1.0
slist
⚠️ Caution: this is a very opinionated library. There is no intention to replace the standard list data type. We are aware of every design decision we made for this package, and we are taking responsibility for that design. If you find it inappropriate, please, consider to use another library instead, that would fulfil your requirements.
This package introduces sized list data type — Slist
. The data type
has the following shape:
data Slist a = Slist
{ sList :: [a]
, sSize :: Size
}
As you can see that along with the familiar list, it contains Size
field that
represents the size of the structure. Slists can be finite or infinite, and this
is expressed with Size
.
data Size
= Size Int
| Infinity
⚠️ Caution:
Int
is used for the size by design. We had to make some trade-offs to provide the better (as we think) interface for users. For more details on the choice, see the Haddock documentation for theSize
data type.
This representation of the list gives some additional advantages. Getting the
length of the list is the “free” operation (runs in O(1)
). This property
helps to improve the performance for a bunch of functions like take
, drop
,
at
, etc. But also it doesn’t actually add any overhead on the existing
functions.
Also, this allows to write a number of safe functions like safeReverse
,
safeHead
, safeLast
, safeIsSuffixOf
, etc.
Comparison
Check out the comparison table between lists and slists performance.
Function | list (finite) | list (infinite) | Slist (finite) | Slist (infinite) |
---|---|---|---|---|
length |
O(n) |
<hangs> | O(1) |
O(1) |
safeLast |
O(n) |
<hangs> | O(n) |
O(1) |
init |
O(n) |
<works infinitely> | O(n) |
O(1) |
take |
O(min i n) |
O(i) |
0 < i < n : O(i) ; otherwise: O(1) |
O(i) |
at |
O(min i n) (run-time exception) |
O(i) (run-time exception) |
0 < i < n : O(i) ; otherwise: O(1) |
O(i) |
safeStripPrefix |
O(m) |
O(m) (can hang) |
O(m) |
O(m) |
Potential usage cases
- When you ask the size of the list too frequently.
- When you need to convert to data structures that require to know the list size in advance for allocating an array of the elements. Example: Vector data structure.
- When you need to serialise lists.
- When you need to control the behaviour depending on the finiteness of the list.
- When you need a more efficient or safe implementation of some functions.
Changes
Changelog
slist
uses PVP Versioning.
The changelog is available on GitHub.
0.2.1.0 – Nov 3, 2022
- #56: Support GHC-9.4.
0.2.0.1 – Oct 7, 2022
- #53: Support GHC-9.2.
- Upgrade
hedgehog
dependency.
0.2.0.0 — Mar 18, 2021
-
#45: Support GHC-9.0. Update older GHC’s bounds.
-
#36: Add strict functions:
append'
,concat'
andconcatMap'
. -
#30: Add
cons
andcons'
functions. -
#35: Add integration with the
containers
library:mapToKeys
,mapToVals
,mapToPairs
,setToSlist
.Add
ordNub
. -
#34: Add
partitionWith
andlistPartitionWith
. -
#29: Add
Slist.Maybe
module withmaybeToSlist
,slistToMaybe
,catMaybes
,mapMaybe
,slistWith
functions. -
#31: Add
sortWith
. -
#24: Add
chunksOf
forSlist
andlistChunksOf
for ordinary lists. -
Move the
Slist
data type into the separateSlist.Type
module.
0.1.1.0 — Apr 18, 2020
- Fix
mconcat
forSlist
Monoid
instance. - #25: Support GHC-8.10.
- Update to GHC-8.8.3 from GHC-8.8.1.
0.1.0.0
- #13: Support GHC-8.8.1.
- #16:
Use
DerivingStrategies
. - #9:
Implement
fromRange
function. (by @zfnmxt) - #6: Add generic function over the size and indices. (by @waynee95)
- Make
dropWhile
work better on infinite lists. (by @chshersh) - Support GHC-8.6.5 instead of GHC-8.6.3.
- #6: Build with Stack.
0.0.0
- Initially created.