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.15) [details]
License MPL-2.0
Copyright 2019-2020 Veronika Romashkina
Author Veronika Romashkina
Category Data Structures, List
Home page
Bug tracker
Source repo head: git clone
Uploaded by vrom911 at 2020-04-18T18:19:01Z
Distributions NixOS:
Downloads 680 total (82 in the last 30 days)
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


data Slist a = Slist
    { sList :: [a]
    , sSize :: Size


data Size
    = Size Int
    | Infinity

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.



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 length of the list too frequently.
  • When you need to serialised lists.