# slist

Sized list

https://github.com/vrom911/slist

 LTS Haskell 16.24: 0.1.1.0 Stackage Nightly 2020-12-04: 0.1.1.0 Latest on Hackage: 0.1.1.0

See all snapshots slist appears in

Maintained by
This version can be pinned in stack with:slist-0.1.1.0@sha256:4896d54f16493697facb4b2a23395d95de5eefe2a0e9acdb62d8bb034846070d,2537

#### Module documentation for 0.1.1.0

Depends on 1 package(full list with versions):

# slist

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

• When you ask the length 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 serialised 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.

# Changelog

slist uses PVP Versioning. The changelog is available on GitHub.

## 0.1.1.0 — Apr 18, 2020

• Fix mconcat for Slist 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.