@funkia/list

List

A fast immutable list/sequence data structure with a functional API. A general purpose replacement for native arrays.

Features

• API centered around functions with arguments ordered for currying/partial application.
• Seamless Ramda integration—if you know Ramda you already know how to use List.
• Very good performance.
• Written in TypeScript and comes with accurate types that cover the entire library.
• Fantasy Land support.
• Ships with tree-shaking compatible ES modules. You only pay in size for the functions that you actually use.

Install

npm install @funkia/list

What & why?

List is a purely functional alternative to arrays. It is an implementation of a fast sequential data structure. Compared to JavaScript arrays List has two major benefits.

• Arrays have an API for mutating them. List don't. This means that if you want to do purely functional programming List is better suited and it won't tempt you with an imperative API.
• Since List doesn't allow mutations it can be heavily optimized for pure operations. This makes List much faster for functional programming than arrays.

Since List is immutable it provides increased safety compared to arrays. It is impossible to accidentally mutate a list because it offers no API for mutating it. If you're doing functional programming with arrays their impure API is nothing but a source of bugs.

Due to the way List is implemented it can be many times faster than arrays for functional programming. If, for instance, you concatenate two arrays both arrays will have to be copied into a new array. This is because potential mutations to the old arrays must not affect the new concatenated array. List, on the other hand, is immutable and the concatenated list can share the majority of its structure with the old lists. This reduces copying, reduces memory allocations, and results in much better performance.

Seamless Ramda integration

List is designed to work seamlessly together with Ramda. Ramda offers a large number of useful functions for working with arrays. List implements the same methods on its immutable data structure. This means that Ramda users can keep using the API they're familiar with.

Additionally, List offers an entry point where all functions are curried using Ramda's R.curry and where all equality comparisons are done using R.equals.

import * as L from "@funkia/list/ramda";
const indexOfFoo1 = indexOf({ foo: 1 });
indexOfFoo1({ foo: 0 }, { foo: 1 }, { foo: 2 }); //=> 1

In the example above indexOf is curried and it uses R.equals to find an element equivalent to {foo: 1}.

Since List implements Ramda's array API it is very easy to convert code from using arrays to using immutable lists. As an example, consider the code below.

import * as R from "ramda";

R.pipe(R.filter(n => n % 2 === 0), R.map(R.multiply(3)), R.reduce(R.add, 0))(
  array
);

It can be converted to code using List as follows.

import * as R from "ramda";
import * as L from "@funkia/list";

R.pipe(L.filter(n => n % 2 === 0), L.map(R.multiply(3)), L.reduce(R.add, 0))(
  list
);

For each function operating on arrays, the R is simply changed to an L. This works because List exports functions that have the same name and behavior as Ramdas functions.

Implemented Ramda functions

The goal is to implement the entirety of Ramda's array functions for List. The list below keeps track of how many of Ramda functions that are missing and of how many that are already implemented. Currently 36 out of 115 functions have been implemented.

Implemented: adjust, all, any, append, concat, contains, drop, dropLast, dropWhile, filter, find, findIndex, head, flatten, indexOf, init, last, length, join, map, none, nth, pair, pluck, prepend, range, reduce, reduceRight, reject, repeat, slice, splitAt, take, takeWhile, tail, takeLast, update.

Not implemented: aperture, chain, dropLastWhile, dropRepeats, dropRepeatsWith, endsWith, findLast, findLastIndex, fromPairs, groupBy, groupWith, indexBy, insert, insertAll, intersperse, lastIndexOf, mapAccum, mapAccumRight, mergeAll, partition, reduceBy, reduceWhile, remove, reverse, scan, sequence, sort, splitEvery, splitWhen, startsWith, takeLastWhile, times, transpose, traverse, unfold, uniq, uniqBy, uniqWith, unnest without, xprod, zip, zipObj, zipWith.

Fantasy Land

List currently implements the following Fantasy Land specifications: Setoid, semigroup, monoid, foldable, functor.

The following specifications are planned but have not implemented yet: Apply, applicative, traversable, chain, monad.

API

The API is organized into three parts.

1. Functions that create lists.
2. Functions that transform lits. That is, functions that take one or more lists as arguments and returns a new list.
3. Function extracts values from lists. They take one or more lists as arguments and returns something that is not a list.

Creating lists

list

Creates a list based on the arguments given.

Complexity: O(n)

Example

const l = list(1, 2, 3, 4); // creates a list of four elements
const l2 = list("foo"); // creates a singleton

empty

Returns an empty list.

Complexity: O(1)

Example

const emptyList = empty(); //=> list()

pair

Takes two arguments and returns a list that contains them.

Complexity: O(1)

Example

pair("foo", "bar"); //=> list("foo", "bar")

fromArray

Converts an array into a list.

Complexity: O(n)

Example

fromArray([0, 1, 2, 3, 4]); //=> list(0, 1, 2, 3, 4)

range

Returns a list of numbers between an inclusive lower bound and an exclusive upper bound.

Complexity: O(n)

Example

range(3, 8); //=> list(3, 4, 5, 6, 7)

repeat

Returns a list of a given length that contains the specified value in all positions.

Complexity: O(n)

Example

repeat(1, 7); //=> list(1, 1, 1, 1, 1, 1, 1)
repeat("foo", 3); //=> list("foo", "foo", "foo")

Updating lists

concat

Concatenates two lists.

Complexity: O(logn)

Example

concat(list(0, 1, 2), list(3, 4)); //=> list(0, 1, 2, 3, 4)

flatten

Flattens a list of lists into a list. Note that this function does not flatten recursively. It removes one level of nesting only.

Complexity: O(n * log(m)) where n is the length of the outer list and m the length of the inner lists.

Example

const nested = list(list(0, 1, 2, 3), list(4), empty(), list(5, 6));
flatten(nested); //=> list(0, 1, 2, 3, 4, 5, 6)

prepend

Prepends an element to the front of a list and returns the new list.

Complexity: O(logn), practically constant

Example

const newList = prepend(0, list(1, 2, 3)); //=> list(0, 1, 2, 3)

append

Appends an element to the end of a list and returns the new list.

Complexity: O(logn), practically constant

Example

const newList = append(3, list(0, 1, 2)); //=> list(0, 1, 2, 3)

map

Applies a function to each element in the given list and returns a new list of the values that the function return.

Complexity: O(n)

Example

map(n => n * n, list(0, 1, 2, 3, 4)); //=> list(0, 1, 4, 9, 12)

pluck

Extracts the specified property from each object in the list.

Example

const l = list(
  { foo: 0, bar: "a" },
  { foo: 1, bar: "b" },
  { foo: 2, bar: "c" }
);
pluck("foo", l); //=> list(0, 1, 2)

update

Returns a list that has the entry specified by the index replaced with the given value.

Complexity: O(logn)

Example

update(2, "X", list("a", "b", "c", "d", "e")); //=> list("a", "b", "X", "d", "e")

adjust

Returns a list that has the entry specified by the index replaced with the value returned by applying the function to the value.

Complexity: O(logn)

Example

adjust(2, inc, list(0, 1, 2, 3, 4, 5)); //=> list(0, 1, 3, 3, 4, 5)

slice

Returns a slice of a list. Elements are removed from the beginning and end. Both the indices can be negative in which case they will count from the right end of the list.

Complexity: O(log(n))

Example

const l = list(0, 1, 2, 3, 4, 5);
slice(1, 4, l); //=> list(1, 2, 3)
slice(2, -2, l); //=> list(2, 3)

take

Takes the first n elements from a list and returns them in a new list.

Complexity: O(log(n))

Example

take(3, list(0, 1, 2, 3, 4, 5)); //=> list(0, 1, 2)

takeWhile

Takes the first elements in the list for which the predicate returns true.

Complexity: O(k + log(n)) where k is the number of elements satisfying the predicate.

Example

takeWhile(n => n < 4, list(0, 1, 2, 3, 4, 5, 6)); //=> list(0, 1, 2, 3)

takeLast

Takes the last n elements from a list and returns them in a new list.

Complexity: O(log(n))

Example

takeLast(3, list(0, 1, 2, 3, 4, 5)); //=> list(3, 4, 5)

splitAt

Splits a list at the given index and return the two sides in a pair. The left side will contain all elements before but not including the element at the given index. The right side contains the element at the index and all elements after it.

Complexity: O(log(n))

Example

const l = list(0, 1, 2, 3, 4, 5, 6, 7, 8);
splitAt(4, l); //=> [list(0, 1, 2, 3), list(4, 5, 6, 7, 8)]

remove

Takes an index, a number of elements to remove and a list. Returns a new list with the given amount of elements removed from the specified index.

Complexity: O(log(n))

Example

const l = list(0, 1, 2, 3, 4, 5, 6, 7, 8);
remove(4, 3, l); //=> list(0, 1, 2, 3, 7, 8)
remove(2, 5, l); //=> list(0, 1, 7, 8)

drop

Returns a new list without the first n elements.

Complexity: O(log(n))

Example

drop(2, list(0, 1, 2, 3, 4, 5)); //=> list(2, 3, 4, 5)

dropWhile

Removes the first elements in the list for which the predicate returns true.

Complexity: O(k + log(n)) where k is the number of elements satisfying the predicate.

Example

dropWhile(n => n < 4, list(0, 1, 2, 3, 4, 5, 6)); //=> list(4, 5, 6)

dropLast

Returns a new list without the first n elements.

Complexity: O(log(n))

Example

dropLast(2, list(0, 1, 2, 3, 4, 5)); //=> list(0, 1, 2, 3)

tail

Returns a new list with the first element removed.

Complexity: O(1)

Example

tail(list(0, 1, 2, 3)); //=> list(1, 2, 3)

pop

Returns a new list with the last element removed.

Aliases: init

Complexity: O(1)

Example

pop(list(0, 1, 2, 3)); //=> list(0, 1, 2)

filter

Returns a new list that only contains the elements of the original list for which the predicate returns true.

Complexity: O(n)

Example

filter(isEven, list(0, 1, 2, 3, 4, 5, 6)); //=> list(0, 2, 4, 6)

reject

Returns a new list that only contains the elements of the original list for which the predicate returns false.

Complexity: O(n)

Example

filter(isEven, list(0, 1, 2, 3, 4, 5, 6)); //=> list(1, 3, 5)

Folds

equals

Returns true if the two lists are equivalent.

Complexity: O(n)

Example

equals(list(0, 1, 2, 3), list(0, 1, 2, 3)); //=> true
equals(list("a", "b", "c"), list("a", "z", "c")); //=> false

toArray

Converts a list into an array.

Complexity: O(n)

Example

toArray(list(0, 1, 2, 3, 4)); //=> [0, 1, 2, 3, 4]

nth

Gets the nth element of the list.

Complexity: O(logn), practically constant

Example

const l = list(0, 1, 2, 3, 4);
nth(2, l); //=> 2

length

Returns the length of a list. I.e. the number of elements that it contains.

Complexity: O(1)

Example

length(list(0, 1, 2, 3)); //=> 4

first

Returns the first element of the list. If the list is empty the function returns undefined.

Aliases: head

Complexity: O(1)

Example

first(list(0, 1, 2, 3)); //=> 0
first(list()); //=> undefined

last

Returns the last element of the list. If the list is empty the function returns undefined.

Complexity: O(1)

Example

last(list(0, 1, 2, 3)); //=> 3
last(list()); //=> undefined

foldl

Folds a function over a list. Left-associative.

Aliases: reduce

Complexity: O(n)

Example

foldl((n, m) => n - m, 1, list(2, 3, 4, 5));
1 - 2 - 3 - 4 - 5; //=> -13

foldr

Folds a function over a list. Right-associative.

Aliases: reduceRight Aliases: reduceRight

Complexity: O(n)

Example

foldr((n, m) => n - m, 5, list(1, 2, 3, 4));
1 - (2 - (3 - (4 - 5))); //=> 3

every

Returns true if and only if the predicate function returns true for all elements in the given list.

Aliases: all

Complexity: O(n)

Example

const isEven = n => n % 2 === 0;
every(isEven, empty()); //=> true
every(isEven, list(2, 4, 6, 8)); //=> true
every(isEven, list(2, 3, 4, 6, 7, 8)); //=> false
every(isEven, list(1, 3, 5, 7)); //=> false

some

Returns true if and only if there exists an element in the list for which the predicate returns true.

Aliases: any

Complexity: O(n)

Example

const isEven = n => n % 2 === 0;
some(isEven, empty()); //=> false
some(isEven, list(2, 4, 6, 8)); //=> true
some(isEven, list(2, 3, 4, 6, 7, 8)); //=> true
some(isEven, list(1, 3, 5, 7)); //=> false

indexOf

Returns the index of the first element in the list that is equal to the given element. If no such element is found the function returns -1.

Complexity: O(n)

Example

const l = list(12, 4, 2, 89, 6, 18, 7);
indexOf(12, l); //=> 0
indexOf(89, l); //=> 3
indexOf(10, l); //=> -1

find

Returns the first element for which the predicate returns true. If no such element is found the function returns undefined.

Complexity: O(n)

Example

find(isEven, list(1, 3, 5, 6, 7, 9, 10)); //=> 6
find(isEven, list(1, 3, 5, 7, 9)); //=> undefined

findIndex

Returns the index of the first element for which the predicate returns true. If no such element is found the function returns -1.

Complexity: O(n)

Example

findIndex(isEven, list(1, 3, 5, 6, 7, 9, 10)); //=> 3
findIndex(isEven, list(1, 3, 5, 7, 9)); //=> -1

none

Returns true if and only if the predicate function returns false for all elements in the given list.

Complexity: O(n)

Example

const isEven = n => n % 2 === 0;
none(isEven, empty()); //=> true
none(isEven, list(2, 4, 6, 8)); //=> false
none(isEven, list(2, 3, 4, 6, 7, 8)); //=> false
none(isEven, list(1, 3, 5, 7)); //=> true

includes

Returns true if the list contains the specified element. Otherwise it returns false.

Aliases: contains

Complexity: O(n)

Example

includes(3, list(0, 1, 2, 3, 4, 5)); //=> true
includes(3, list(0, 1, 2, 4, 5)); //=> false

join

Concats the strings in a list separated by a specified separator.

Complexity: O(n)

Example

join(", ", list("one", "two", "three")); //=> "one, two, three"

Benchmarks

The benchmarks are located in the bench directory.

Run the benchmarks like this (starting with CWD in the root).

npm install
npm run build
cd bench
npm install
./prepare-benchmarks.sh
npm run bench

Note that in the output List corresponds to @funkia/list.