slist: Sized list

[ data-structures, library, list, mpl ] [ Propose Tags ]

This package implements Slist data structure that stores the size of the list along with the list itself.

[Skip to Readme]
Versions [faq] 0.0.0,,,
Change log
Dependencies base (>= && <4.16), containers (>=0.5 && <=0.7) [details]
License MPL-2.0
Copyright 2019-2020 Veronika Romashkina 2020-2021 Kowainik
Author Veronika Romashkina
Maintainer Kowainik <>
Category Data Structures, List
Home page
Bug tracker
Source repo head: git clone
Uploaded by vrom911 at 2021-03-18T13:23:08Z
Distributions NixOS:, Stackage:
Downloads 1184 total (30 in the last 30 days)
Rating 2.25 (votes: 2) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs uploaded by user
Build status unknown [no reports yet]


[Index] [Quick Jump]


Maintainer's Corner

For package maintainers and hackage trustees

Readme for slist-

[back to package description]


GitHub CI Build status Hackage Stackage LTS Stackage Nightly MPL-2.0 license

⚠️ 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 the Size 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.


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.