slist: Sized list

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

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


[Skip to Readme]

Properties

Versions 0.0.0, 0.1.0.0, 0.1.0.0, 0.1.1.0, 0.2.0.0, 0.2.0.1, 0.2.1.0
Change log CHANGELOG.md
Dependencies base (>=4.10.1.0 && <4.14) [details]
License MPL-2.0
Copyright 2019 Veronika Romashkina
Author Veronika Romashkina
Maintainer vrom911@gmail.com
Category Data Structures, List
Home page https://github.com/vrom911/slist
Bug tracker https://github.com/vrom911/slist/issues
Source repo head: git clone https://github.com/vrom911/slist.git
Uploaded by vrom911 at 2019-11-08T08:26:44Z

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for slist-0.1.0.0

[back to package description]

slist

Build status Hackage Stackage LTS Stackage Nightly MPL-2.0 license

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

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