A fast immutable list/sequence data structure with a functional API. A general purpose replacement for native arrays.
npm install list
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.
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.
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.
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.
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.
The API is organized into three parts.
listCreates 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
emptyReturns an empty list.
Complexity: O(1)
Example
const emptyList = empty(); //=> list()
pairTakes two arguments and returns a list that contains them.
Complexity: O(1)
Example
pair("foo", "bar"); //=> list("foo", "bar")
fromArrayConverts an array into a list.
Complexity: O(n)
Example
fromArray([0, 1, 2, 3, 4]); //=> list(0, 1, 2, 3, 4)
rangeReturns 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)
repeatReturns 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")
concatConcatenates two lists.
Complexity: O(logn)
Example
concat(list(0, 1, 2), list(3, 4)); //=> list(0, 1, 2, 3, 4)
flattenFlattens 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)
prependPrepends 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)
appendAppends 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)
mapApplies 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)
pluckExtracts 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)
updateReturns 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")
adjustReturns 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)
sliceReturns 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)
takeTakes 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)
takeWhileTakes 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)
takeLastTakes 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)
splitAtSplits 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)]
removeTakes 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)
dropReturns 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)
dropWhileRemoves 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)
dropLastReturns 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)
tailReturns a new list with the first element removed.
Complexity: O(1)
Example
tail(list(0, 1, 2, 3)); //=> list(1, 2, 3)
popReturns a new list with the last element removed.
Aliases: init
Complexity: O(1)
Example
pop(list(0, 1, 2, 3)); //=> list(0, 1, 2)
filterReturns 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)
rejectReturns 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)
equalsReturns 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
toArrayConverts a list into an array.
Complexity: O(n)
Example
toArray(list(0, 1, 2, 3, 4)); //=> [0, 1, 2, 3, 4]
nthGets the nth element of the list.
Complexity: O(logn), practically constant
Example
const l = list(0, 1, 2, 3, 4);
nth(2, l); //=> 2
lengthReturns 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
firstReturns 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
lastReturns 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
foldlFolds 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
foldrFolds 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
everyReturns 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
someReturns 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
indexOfReturns 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
findReturns 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
findIndexReturns 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
noneReturns 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
includesReturns 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
joinConcats the strings in a list separated by a specified separator.
Complexity: O(n)
Example
join(", ", list("one", "two", "three")); //=> "one, two, three"
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.
FAQs
Fast purely functional immutable lists.
The npm package list receives a total of 11,006 weekly downloads. As such, list popularity was classified as popular.
We found that list demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 2 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
GitHub removed 27 malicious pull requests attempting to inject harmful code across multiple open source repositories, in another round of low-effort attacks.
Security News
RubyGems.org has added a new "maintainer" role that allows for publishing new versions of gems. This new permission type is aimed at improving security for gem owners and the service overall.
Security News
Node.js will be enforcing stricter semver-major PR policies a month before major releases to enhance stability and ensure reliable release candidates.