1 | <h3 align="center">
|
2 | <img align="center" src="assets/listopard.png" alt="List logo" width=400 />
|
3 | </h3>
|
4 |
|
5 | <p align="center">
|
6 | A fast immutable list with a functional API.
|
7 | </p>
|
8 |
|
9 | <p align="center">
|
10 | <a href="https://gitter.im/funkia/General"><img src="https://img.shields.io/gitter/room/funkia/General.svg" alt="Gitter" height="20"></a>
|
11 | <a href="https://travis-ci.org/funkia/list"><img src="https://travis-ci.org/funkia/list.svg?branch=master" alt="Build Status" height="20"></a>
|
12 | <a href="https://codecov.io/gh/funkia/list"><img src="https://codecov.io/gh/funkia/list/branch/master/graph/badge.svg" alt="codecov" height="20"></a>
|
13 | <a href="https://badge.fury.io/js/list"><img src="https://badge.fury.io/js/list.svg" alt="npm version" height="20"></a>
|
14 | <a href="https://david-dm.org/funkia/list"><img src="https://david-dm.org/funkia/list/status.svg" alt="npm version" height="20"></a>
|
15 | <a href="https://david-dm.org/funkia/list?type=dev"><img src="https://david-dm.org/funkia/list/dev-status.svg" alt="npm version" height="20"></a>
|
16 | <a href="https://greenkeeper.io/"><img src="https://badges.greenkeeper.io/funkia/list.svg" alt="Greenkeeper badge"></a>
|
17 | </p>
|
18 |
|
19 | # List
|
20 |
|
21 | List is a purely functional alternative to arrays. It is an
|
22 | implementation of a fast persistent sequence data structure. Compared
|
23 | to JavaScript's `Array` List has three major benefits.
|
24 |
|
25 | * **Safety**. List is immutable. This makes it safer and better suited
|
26 | for functional programming. It doesn't tempt you with an imperative API and
|
27 | accidental mutations won't be a source of bugs.
|
28 | * **Performance**. Since List doesn't allow mutations it can be
|
29 | heavily optimized for pure operations. This makes List much faster for
|
30 | functional programming than arrays. [See the
|
31 | benchmarks](https://funkia.github.io/list/benchmarks/).
|
32 | * **API**: List has a large API of useful functions and offers both chainable
|
33 | methods and curried functions to suit every taste.
|
34 |
|
35 | ## Features
|
36 |
|
37 | * **Familiar functional API**. List follows the naming conventions
|
38 | common in functional programming and has arguments ordered for
|
39 | currying/partial application.
|
40 | * **Extensive API**. List has all the functions known from `Array`
|
41 | and a lot of additional functions that'll save the day once you need them.
|
42 | * **Extremely fast**. List is a carefully optimized implementation of
|
43 | the highly efficient data-structure _relaxed radix balanced trees_. We have
|
44 | an [extensive benchmark suite](https://funkia.github.io/list/benchmarks/) to
|
45 | ensure optimal performance.
|
46 | * **Several API styles**. In addition to the base API List offers [additional
|
47 | API styles](#api-styles). Import `list/methods` to get chainable methods or
|
48 | alterntively import `list/curried` to get a version of the API where every
|
49 | function is curried. Both variants are 100% TypeScript compatible.
|
50 | * **Does one thing well**. Instead of offering a wealth of data
|
51 | structures List has a tight focus on being the best immutable list possible.
|
52 | It doesn't do everything but is designed to work well with the libraries
|
53 | you're already using.
|
54 | * **Seamless Ramda integration**. If you know Ramda you already know
|
55 | how to use List. List was designed to integrate [seamlessly with
|
56 | Ramda](#seamless-ramda-integration).
|
57 | * **Type safe**. List is implemented in TypeScript. It makes full use of
|
58 | TypeScript features to provide accurate types that covers the entire library.
|
59 | * **Fully compatible with tree-shaking**. List ships with tree-shaking
|
60 | compatible ECMAScript modules. `import * as L from "list"` in itself adds
|
61 | zero bytes to your bundle when using Webpack. Using a function adds only that
|
62 | function and the very small (<1KB) core of the library. You only pay in size
|
63 | for the functions that you actually use.
|
64 | * **Iterable**. Implements the JavaScript iterable protocol. This
|
65 | means that lists can be use in `for..of` loops, works with destructuring, and
|
66 | can be passed to any function expecting an iterable. [See more](#iterable).
|
67 | * **Fantasy Land support**. List
|
68 | [implements](#fantasy-land-static-land) both the Fantasy Land and the Static
|
69 | Land specification.
|
70 |
|
71 | ## Getting started
|
72 |
|
73 | This section explains how to get started using List. First you'll have
|
74 | to install the library.
|
75 |
|
76 | ```
|
77 | npm install list
|
78 | ```
|
79 |
|
80 | Then you can import it.
|
81 |
|
82 | ```js
|
83 | // As an ES module
|
84 | import * as L from "list";
|
85 | // Or with require
|
86 | const L = require("list");
|
87 | ```
|
88 |
|
89 | Then you can begin using List instead of arrays and enjoy immutability
|
90 | the performance benefits.
|
91 |
|
92 | As a replacement for array literals List offers the function `list`
|
93 | for constructing lists:
|
94 |
|
95 | ```js
|
96 | // An array literal
|
97 | const myArray = [0, 1, 2, 3];
|
98 | // A list "literal"
|
99 | const myList = L.list(0, 1, 2, 3);
|
100 | ```
|
101 |
|
102 | List has all the common functions that you know from native arrays and
|
103 | other libraries.
|
104 |
|
105 | ```js
|
106 | const myList = L.list(0, 1, 2, 3, 4, 5);
|
107 | myList.length; //=> 6
|
108 | L.filter(isEven, myList); //=> list(0, 2, 4)
|
109 | L.map(n => n * n, myList); //=> list(0, 1, 4, 9, 16, 25)
|
110 | L.reduce((sum, n) => sum + n, 0, myList); //=> 15
|
111 | L.slice(2, 5, myList); //=> list(2, 3, 4)
|
112 | L.concat(myList, L.list(6, 7, 8)); //=> list(0, 1, 2, 3, 4, 5, 6, 7, 8);
|
113 | ```
|
114 |
|
115 | You'll probably also end up needing to convert between arrays and
|
116 | List. You can do that with the functions `fromArray` and `toArray`.
|
117 |
|
118 | ```js
|
119 | L.toArray(L.list("foo", "bar")); //=> ["foo", "bar"];
|
120 | L.fromArray(["foo", "bar"]); //=> L.list("foo", "bar");
|
121 | ```
|
122 |
|
123 | List offers a wealth of other useful and high-performing functions.
|
124 | You can see them all in the [API documentation](#api-documentation)
|
125 |
|
126 | ## API styles
|
127 |
|
128 | List offers several API styles. By default the library exports "plain"
|
129 | functions. Additioanlly curried functions can be imported from `list/curried`
|
130 | and an API with chainable methods can be imported from `list/methods`. The
|
131 | differences are illustrated below.
|
132 |
|
133 | The default export offers normal plain function.
|
134 |
|
135 | ```ts
|
136 | import * as L from "list";
|
137 |
|
138 | const l = take(5, sortBy(p => p.name, filter(p => p.age > 22, people)));
|
139 | ```
|
140 |
|
141 | In `list/methods` all functions are available as chainable methods.
|
142 |
|
143 | ```ts
|
144 | import * as L from "list/methods";
|
145 |
|
146 | const l = people
|
147 | .filter(p => p.age > 22)
|
148 | .sortBy(p => p.name)
|
149 | .take(5);
|
150 | ```
|
151 |
|
152 | In `list/curried` all functions are curried. In the example below the partially
|
153 | applied functions are composed together using Ramda's
|
154 | [`pipe`](http://ramdajs.com/docs/#pipe). Alternatively one could have used
|
155 | Lodash's [`flowRight`](https://lodash.com/docs/#flow).
|
156 |
|
157 | ```ts
|
158 | import * as R from "ramda";
|
159 | import * as L from "list/curried";
|
160 |
|
161 | const l = R.pipe(L.filter(p => p.age > 22), L.sortBy(p => p.name), L.take(5))(
|
162 | people
|
163 | );
|
164 | ```
|
165 |
|
166 | ## Iterable
|
167 |
|
168 | List implements the JavaScript iterable protocol. This means that
|
169 | lists can be used with array destructuring just like normal arrays.
|
170 |
|
171 | ```js
|
172 | const myList = L.list("first", "second", "third", "fourth");
|
173 | const [first, second] = myList;
|
174 | first; //=> "first"
|
175 | second; //=> "second"
|
176 | ```
|
177 |
|
178 | Lists can also be used in `for..of` loops.
|
179 |
|
180 | ```js
|
181 | for (const element of myList) {
|
182 | console.log(element);
|
183 | }
|
184 | // logs: first, second, third, fourth
|
185 | ```
|
186 |
|
187 | And they can be passed to any function that takes an iterable as its
|
188 | argument. As an example a list can be converted into a native
|
189 | [`Set`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set).
|
190 |
|
191 | ```js
|
192 | const mySet = new Set(myList);
|
193 | mySet.has("third"); //=> true
|
194 | ```
|
195 |
|
196 | This works because the `Set` constructor accepts any iterable as
|
197 | argument.
|
198 |
|
199 | Lists also work with [spread syntax](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_syntax). For instannce, you can call a function like this.
|
200 |
|
201 | ```js
|
202 | console.log(...list("hello", "there", "i'm", "logging", "elements"));
|
203 | ```
|
204 |
|
205 | And each element of the list will be passed as an argument to `console.log`.
|
206 |
|
207 | The iterable protocol allows for some very convenient patterns and
|
208 | means that lists can integrate nicely with JavaScript syntax. But,
|
209 | here are two anti-patterns that you should be aware of.
|
210 |
|
211 | 1. Don't overuse `for..of` loops. Functions like [`map`](#map) and
|
212 | [`foldl`](#foldl) are often a better choice. If you want to perform
|
213 | a side-effect for each element in a list you should probably use
|
214 | [`forEach`](#forEach).
|
215 | 2. Don't use the spread syntax in destructuring
|
216 | ```js
|
217 | const [a, b, ...cs] = myList; // Don't do this
|
218 | ```
|
219 | The syntax converts the rest of the iterable (in this case a list)
|
220 | into an array by iterating through the entire iterable. This is
|
221 | slow and it turns our list into an array. This alternative avoids
|
222 | both problems.
|
223 | ```js
|
224 | const [[a, b], cs] = splitAt(2, myList); // Do this
|
225 | ```
|
226 | This uses the [`splitAt`](#splitAt) function which splits and
|
227 | creates the list `cs` very efficiently in `O(log(n))` time.
|
228 |
|
229 | ## Seamless Ramda integration
|
230 |
|
231 | List is designed to work seamlessly together with Ramda. Ramda offers a large
|
232 | number of useful functions for working with arrays. List implements the same
|
233 | functions on its immutable data structure. This means that Ramda users can keep
|
234 | using the API they're familiar with. Additionally, List offers an entry point
|
235 | where all functions are curried.
|
236 |
|
237 | Since List implements Ramda's array API it is very easy to convert code from
|
238 | using arrays to using immutable lists. As an example, consider the code below.
|
239 |
|
240 | ```js
|
241 | import * as R from "ramda";
|
242 |
|
243 | R.pipe(R.filter(n => n % 2 === 0), R.map(R.multiply(3)), R.reduce(R.add, 0))(
|
244 | array
|
245 | );
|
246 | ```
|
247 |
|
248 | The example can be converted to code using List as follows.
|
249 |
|
250 | ```js
|
251 | import * as R from "ramda";
|
252 | import * as L from "list/curried";
|
253 |
|
254 | R.pipe(L.filter(n => n % 2 === 0), L.map(R.multiply(3)), L.reduce(R.add, 0))(
|
255 | list
|
256 | );
|
257 | ```
|
258 |
|
259 | For each function operating on arrays, the `R` is simply changed to an `L`.
|
260 | This works because List exports functions that have the same names and behavior
|
261 | as Ramdas functions.
|
262 |
|
263 | ### Implemented Ramda functions
|
264 |
|
265 | The goal is to implement the entirety of Ramda's array functions for List. The
|
266 | list below keeps track of how many of Ramda functions that are missing and of
|
267 | how many that are already implemented. Currently 46 out of 75 functions have
|
268 | been implemented.
|
269 |
|
270 | Implemented: `adjust`, `all`, `any`, `append`, `chain`, `concat`, `contains`,
|
271 | `drop`, `dropLast`, `dropWhile`, `filter`, `find`, `findIndex`, `head`,
|
272 | `flatten`, `indexOf`, `init`, `insert`, `insertAll`, `last`, `length`, `join`,
|
273 | `map`, `none`, `nth`, `pair`, `partition`, `pluck`, `prepend`, `range`,
|
274 | `reduce`, `reduceRight`, `reject`, `remove`, `reverse`, `repeat`, `slice`,
|
275 | `sort`, `splitAt`, `take`, `takeWhile`, `tail`, `takeLast`, `times`, `update`,
|
276 | `zip`, `zipWith`.
|
277 |
|
278 | Not implemented: `aperture`, `dropLastWhile`, `dropRepeats`, `dropRepeatsWith`,
|
279 | `endsWith`, `findLast`, `findLastIndex`, `groupWith`, `indexBy`, `intersperse`,
|
280 | `lastIndexOf`, `mapAccum`, `mapAccumRight`, `reduceWhile`, `scan`, `sequence`,
|
281 | `splitEvery`, `splitWhen`, `startsWith`, `takeLastWhile`, `transpose`,
|
282 | `traverse`, `unfold`, `uniq`, `uniqBy`, `uniqWith`, `unnest` `without`,
|
283 | `xprod`.
|
284 |
|
285 | ## Fantasy Land & Static Land
|
286 |
|
287 | <img align="right" width="82" height="82" alt="Fantasy Land" src="https://raw.github.com/fantasyland/fantasy-land/master/logo.png">
|
288 | <img align="right" width="131" height="82" src="https://raw.githubusercontent.com/rpominov/static-land/master/logo/logo.png" />
|
289 |
|
290 | List currently implements the following Fantasy Land and Static Land
|
291 | specifications: Setoid, semigroup, monoid, foldable, functor, apply,
|
292 | applicative, chain, monad.
|
293 |
|
294 | The following specifications have not been implemented yet:
|
295 | Traversable, Ord.
|
296 |
|
297 | Since methods hinder tree-shaking the Fantasy Land methods are not
|
298 | included by default. In order to get them you must import it likes
|
299 | this:
|
300 |
|
301 | ```js
|
302 | import "list/fantasy-land";
|
303 | ```
|
304 |
|
305 | ## API documentation
|
306 |
|
307 | The API is organized into three parts.
|
308 |
|
309 | 1. [Creating lists](#creating-lists) — Functions that _create_ lists.
|
310 | 2. [Updating lists](#updating-lists) — Functions that _transform_ lists.
|
311 | That is, functions that take one or more lists as arguments and
|
312 | returns a new list.
|
313 | 3. [Folds](#folds) — Functions that _extracts_ values based on lists.
|
314 | They take one or more lists as arguments and returns something that
|
315 | is not a list.
|
316 |
|
317 | ### Creating lists
|
318 |
|
319 | ### `list`
|
320 |
|
321 | Creates a list based on the arguments given.
|
322 |
|
323 | **Complexity**: `O(n)`
|
324 |
|
325 | **Example**
|
326 |
|
327 | ```js
|
328 | const l = list(1, 2, 3, 4); // creates a list of four elements
|
329 | const l2 = list("foo"); // creates a singleton
|
330 | ```
|
331 |
|
332 | ### `empty`
|
333 |
|
334 | Returns an empty list.
|
335 |
|
336 | **Complexity**: `O(1)`
|
337 |
|
338 | **Example**
|
339 |
|
340 | ```js
|
341 | const emptyList = empty(); //=> list()
|
342 | ```
|
343 |
|
344 | ### `of`
|
345 |
|
346 | Takes a single arguments and returns a singleton list that contains it.
|
347 |
|
348 | **Complexity**: `O(1)`
|
349 |
|
350 | **Example**
|
351 |
|
352 | ```js
|
353 | of("foo"); //=> list("foo")
|
354 | ```
|
355 |
|
356 | ### `pair`
|
357 |
|
358 | Takes two arguments and returns a list that contains them.
|
359 |
|
360 | **Complexity**: `O(1)`
|
361 |
|
362 | **Example**
|
363 |
|
364 | ```js
|
365 | pair("foo", "bar"); //=> list("foo", "bar")
|
366 | ```
|
367 |
|
368 | ### `fromArray`
|
369 |
|
370 | Converts an array into a list.
|
371 |
|
372 | **Complexity**: `O(n)`
|
373 |
|
374 | **Example**
|
375 |
|
376 | ```js
|
377 | fromArray([0, 1, 2, 3, 4]); //=> list(0, 1, 2, 3, 4)
|
378 | ```
|
379 |
|
380 | ### `range`
|
381 |
|
382 | Returns a list of numbers between an inclusive lower bound and an
|
383 | exclusive upper bound.
|
384 |
|
385 | **Complexity**: `O(n)`
|
386 |
|
387 | **Example**
|
388 |
|
389 | ```js
|
390 | range(3, 8); //=> list(3, 4, 5, 6, 7)
|
391 | ```
|
392 |
|
393 | ### `repeat`
|
394 |
|
395 | Returns a list of a given length that contains the specified value in
|
396 | all positions.
|
397 |
|
398 | **Complexity**: `O(n)`
|
399 |
|
400 | **Example**
|
401 |
|
402 | ```js
|
403 | repeat(1, 7); //=> list(1, 1, 1, 1, 1, 1, 1)
|
404 | repeat("foo", 3); //=> list("foo", "foo", "foo")
|
405 | ```
|
406 |
|
407 | ### `times`
|
408 |
|
409 | Returns a list of given length that contains the value of the given function called with current index.
|
410 |
|
411 | **Complexity**: `O(n)`
|
412 |
|
413 | **Example**
|
414 |
|
415 | ```js
|
416 | const twoFirsOdds = times(i => i * 2 + 1, 2);
|
417 | const dots = times(() => {
|
418 | const x = Math.random() * width;
|
419 | const y = Math.random() * height;
|
420 | return { x, y };
|
421 | }, 50);
|
422 | ```
|
423 |
|
424 | ### Updating lists
|
425 |
|
426 | ### `concat`
|
427 |
|
428 | Concatenates two lists.
|
429 |
|
430 | **Complexity**: `O(log(n))`
|
431 |
|
432 | **Example**
|
433 |
|
434 | ```js
|
435 | concat(list(0, 1, 2), list(3, 4)); //=> list(0, 1, 2, 3, 4)
|
436 | ```
|
437 |
|
438 | ### `flatten`
|
439 |
|
440 | Flattens a list of lists into a list. Note that this function does
|
441 | _not_ flatten recursively. It removes one level of nesting only.
|
442 |
|
443 | **Complexity**: `O(n * log(m))` where `n` is the length of the outer
|
444 | list and `m` the length of the inner lists.
|
445 |
|
446 | **Example**
|
447 |
|
448 | ```js
|
449 | const nested = list(list(0, 1, 2, 3), list(4), empty(), list(5, 6));
|
450 | flatten(nested); //=> list(0, 1, 2, 3, 4, 5, 6)
|
451 | ```
|
452 |
|
453 | ### `prepend`
|
454 |
|
455 | Prepends an element to the front of a list and returns the new list.
|
456 |
|
457 | **Complexity**: `O(log(n))`, practically constant
|
458 |
|
459 | **Example**
|
460 |
|
461 | ```js
|
462 | const newList = prepend(0, list(1, 2, 3)); //=> list(0, 1, 2, 3)
|
463 | ```
|
464 |
|
465 | ### `append`
|
466 |
|
467 | Appends an element to the end of a list and returns the new list.
|
468 |
|
469 | **Complexity**: `O(log(n))`, practically constant
|
470 |
|
471 | **Example**
|
472 |
|
473 | ```js
|
474 | const newList = append(3, list(0, 1, 2)); //=> list(0, 1, 2, 3)
|
475 | ```
|
476 |
|
477 | ### `map`
|
478 |
|
479 | Applies a function to each element in the given list and returns a new
|
480 | list of the values that the function return.
|
481 |
|
482 | **Complexity**: `O(n)`
|
483 |
|
484 | **Example**
|
485 |
|
486 | ```js
|
487 | map(n => n * n, list(0, 1, 2, 3, 4)); //=> list(0, 1, 4, 9, 16)
|
488 | ```
|
489 |
|
490 | ### `pluck`
|
491 |
|
492 | Extracts the specified property from each object in the list.
|
493 |
|
494 | **Example**
|
495 |
|
496 | ```js
|
497 | const l = list(
|
498 | { foo: 0, bar: "a" },
|
499 | { foo: 1, bar: "b" },
|
500 | { foo: 2, bar: "c" }
|
501 | );
|
502 | pluck("foo", l); //=> list(0, 1, 2)
|
503 | ```
|
504 |
|
505 | ### `update`
|
506 |
|
507 | Returns a list that has the entry specified by the index replaced with
|
508 | the given value.
|
509 |
|
510 | If the index is out of bounds the given list is
|
511 | returned unchanged.
|
512 |
|
513 | **Complexity**: `O(log(n))`
|
514 |
|
515 | **Example**
|
516 |
|
517 | ```js
|
518 | update(2, "X", list("a", "b", "c", "d", "e")); //=> list("a", "b", "X", "d", "e")
|
519 | ```
|
520 |
|
521 | ### `adjust`
|
522 |
|
523 | Returns a list that has the entry specified by the index replaced with
|
524 | the value returned by applying the function to the value.
|
525 |
|
526 | If the index is out of bounds the given list is
|
527 | returned unchanged.
|
528 |
|
529 | **Complexity**: `O(log(n))`
|
530 |
|
531 | **Example**
|
532 |
|
533 | ```js
|
534 | adjust(2, inc, list(0, 1, 2, 3, 4, 5)); //=> list(0, 1, 3, 3, 4, 5)
|
535 | ```
|
536 |
|
537 | ### `slice`
|
538 |
|
539 | Returns a slice of a list. Elements are removed from the beginning and
|
540 | end. Both the indices can be negative in which case they will count
|
541 | from the right end of the list.
|
542 |
|
543 | **Complexity**: `O(log(n))`
|
544 |
|
545 | **Example**
|
546 |
|
547 | ```js
|
548 | const l = list(0, 1, 2, 3, 4, 5);
|
549 | slice(1, 4, l); //=> list(1, 2, 3)
|
550 | slice(2, -2, l); //=> list(2, 3)
|
551 | ```
|
552 |
|
553 | ### `take`
|
554 |
|
555 | Takes the first `n` elements from a list and returns them in a new list.
|
556 |
|
557 | **Complexity**: `O(log(n))`
|
558 |
|
559 | **Example**
|
560 |
|
561 | ```js
|
562 | take(3, list(0, 1, 2, 3, 4, 5)); //=> list(0, 1, 2)
|
563 | ```
|
564 |
|
565 | ### `takeWhile`
|
566 |
|
567 | Takes the first elements in the list for which the predicate returns
|
568 | `true`.
|
569 |
|
570 | **Complexity**: `O(k + log(n))` where `k` is the number of elements
|
571 | satisfying the predicate.
|
572 |
|
573 | **Example**
|
574 |
|
575 | ```js
|
576 | takeWhile(n => n < 4, list(0, 1, 2, 3, 4, 5, 6)); //=> list(0, 1, 2, 3)
|
577 | ```
|
578 |
|
579 | ### `takeLast`
|
580 |
|
581 | Takes the last `n` elements from a list and returns them in a new
|
582 | list.
|
583 |
|
584 | **Complexity**: `O(log(n))`
|
585 |
|
586 | **Example**
|
587 |
|
588 | ```js
|
589 | takeLast(3, list(0, 1, 2, 3, 4, 5)); //=> list(3, 4, 5)
|
590 | ```
|
591 |
|
592 | ### `splitAt`
|
593 |
|
594 | Splits a list at the given index and return the two sides in a pair.
|
595 | The left side will contain all elements before but not including the
|
596 | element at the given index. The right side contains the element at the
|
597 | index and all elements after it.
|
598 |
|
599 | **Complexity**: `O(log(n))`
|
600 |
|
601 | **Example**
|
602 |
|
603 | ```js
|
604 | const l = list(0, 1, 2, 3, 4, 5, 6, 7, 8);
|
605 | splitAt(4, l); //=> [list(0, 1, 2, 3), list(4, 5, 6, 7, 8)]
|
606 | ```
|
607 |
|
608 | ### `remove`
|
609 |
|
610 | Takes an index, a number of elements to remove and a list. Returns a
|
611 | new list with the given amount of elements removed from the specified
|
612 | index.
|
613 |
|
614 | **Complexity**: `O(log(n))`
|
615 |
|
616 | **Example**
|
617 |
|
618 | ```js
|
619 | const l = list(0, 1, 2, 3, 4, 5, 6, 7, 8);
|
620 | remove(4, 3, l); //=> list(0, 1, 2, 3, 7, 8)
|
621 | remove(2, 5, l); //=> list(0, 1, 7, 8)
|
622 | ```
|
623 |
|
624 | ### `drop`
|
625 |
|
626 | Returns a new list without the first `n` elements.
|
627 |
|
628 | **Complexity**: `O(log(n))`
|
629 |
|
630 | **Example**
|
631 |
|
632 | ```js
|
633 | drop(2, list(0, 1, 2, 3, 4, 5)); //=> list(2, 3, 4, 5)
|
634 | ```
|
635 |
|
636 | ### `dropWhile`
|
637 |
|
638 | Removes the first elements in the list for which the predicate returns
|
639 | `true`.
|
640 |
|
641 | **Complexity**: `O(k + log(n))` where `k` is the number of elements
|
642 | satisfying the predicate.
|
643 |
|
644 | **Example**
|
645 |
|
646 | ```js
|
647 | dropWhile(n => n < 4, list(0, 1, 2, 3, 4, 5, 6)); //=> list(4, 5, 6)
|
648 | ```
|
649 |
|
650 | ### `dropLast`
|
651 |
|
652 | Returns a new list without the last `n` elements.
|
653 |
|
654 | **Complexity**: `O(log(n))`
|
655 |
|
656 | **Example**
|
657 |
|
658 | ```js
|
659 | dropLast(2, list(0, 1, 2, 3, 4, 5)); //=> list(0, 1, 2, 3)
|
660 | ```
|
661 |
|
662 | ### `tail`
|
663 |
|
664 | Returns a new list with the first element removed.
|
665 |
|
666 | **Complexity**: `O(1)`
|
667 |
|
668 | **Example**
|
669 |
|
670 | ```js
|
671 | tail(list(0, 1, 2, 3)); //=> list(1, 2, 3)
|
672 | ```
|
673 |
|
674 | ### `pop`
|
675 |
|
676 | Returns a new list with the last element removed.
|
677 |
|
678 | **Aliases**: `init`
|
679 |
|
680 | **Complexity**: `O(1)`
|
681 |
|
682 | **Example**
|
683 |
|
684 | ```js
|
685 | pop(list(0, 1, 2, 3)); //=> list(0, 1, 2)
|
686 | ```
|
687 |
|
688 | ### `filter`
|
689 |
|
690 | Returns a new list that only contains the elements of the original
|
691 | list for which the predicate returns `true`.
|
692 |
|
693 | **Complexity**: `O(n)`
|
694 |
|
695 | **Example**
|
696 |
|
697 | ```js
|
698 | filter(isEven, list(0, 1, 2, 3, 4, 5, 6)); //=> list(0, 2, 4, 6)
|
699 | ```
|
700 |
|
701 | ### `reject`
|
702 |
|
703 | Returns a new list that only contains the elements of the original
|
704 | list for which the predicate returns `false`.
|
705 |
|
706 | **Complexity**: `O(n)`
|
707 |
|
708 | **Example**
|
709 |
|
710 | ```js
|
711 | reject(isEven, list(0, 1, 2, 3, 4, 5, 6)); //=> list(1, 3, 5)
|
712 | ```
|
713 |
|
714 | ### `reverse`
|
715 |
|
716 | Reverses a list.
|
717 |
|
718 | **Complexity**: `O(n)`
|
719 |
|
720 | **Example**
|
721 |
|
722 | ```js
|
723 | reverse(list(0, 1, 2, 3, 4, 5)); //=> list(5, 4, 3, 2, 1, 0)
|
724 | ```
|
725 |
|
726 | ### `ap`
|
727 |
|
728 | Applies a list of functions to a list of values.
|
729 |
|
730 | **Example**
|
731 |
|
732 | ```js
|
733 | ap(list((n: number) => n + 2, n => 2 * n, n => n * n), list(1, 2, 3)); //=> list(3, 4, 5, 2, 4, 6, 1, 4, 9)
|
734 | ```
|
735 |
|
736 | ### `chain`
|
737 |
|
738 | Maps a function over a list and concatenates all the resulting lists
|
739 | together.
|
740 |
|
741 | Also known as `flatMap`.
|
742 |
|
743 | **Example**
|
744 |
|
745 | ```js
|
746 | chain(n => list(n, 2 * n, n * n), list(1, 2, 3)); //=> list(1, 2, 1, 2, 4, 4, 3, 6, 9)
|
747 | ```
|
748 |
|
749 | ### `partition`
|
750 |
|
751 | Splits the list into two lists. One list that contains all the values
|
752 | for which the predicate returns `true` and one containing the values for
|
753 | which it returns `false`.
|
754 |
|
755 | **Complexity**: `O(n)`
|
756 |
|
757 | **Example**
|
758 |
|
759 | ```js
|
760 | partition(isEven, list(0, 1, 2, 3, 4, 5)); //=> list(list(0, 2, 4), list(1, 3, 5))
|
761 | ```
|
762 |
|
763 | ### `insert`
|
764 |
|
765 | Inserts the given element at the given index in the list.
|
766 |
|
767 | **Complexity**: `O(log(n))`
|
768 |
|
769 | **Example**
|
770 |
|
771 | ```js
|
772 | insert(2, "c", list("a", "b", "d", "e")); //=> list("a", "b", "c", "d", "e")
|
773 | ```
|
774 |
|
775 | ### `insertAll`
|
776 |
|
777 | Inserts the given list of elements at the given index in the list.
|
778 |
|
779 | **Complexity**: `O(log(n))`
|
780 |
|
781 | **Example**
|
782 |
|
783 | ```js
|
784 | insertAll(2, list("c", "d"), list("a", "b", "e", "f")); //=> list("a", "b", "c", "d", "e", "f")
|
785 | ```
|
786 |
|
787 | ### `zipWith`
|
788 |
|
789 | This is like mapping over two lists at the same time. The two lists are
|
790 | iterated over in parallel and each pair of elements is passed to the function.
|
791 | The returned values are assembled into a new list.
|
792 |
|
793 | The shortest list determine the size of the result.
|
794 |
|
795 | **Complexity**: `O(log(n))` where `n` is the length of the smallest list.
|
796 |
|
797 | **Example**
|
798 |
|
799 | ```js
|
800 | const names = list("Turing", "Curry");
|
801 | const years = list(1912, 1900);
|
802 | zipWith((name, year) => ({ name, year }), names, years);
|
803 | //=> list({ name: "Turing", year: 1912 }, { name: "Curry", year: 1900 });
|
804 | ```
|
805 |
|
806 | ### `zip`
|
807 |
|
808 | Iterate over two lists in parallel and collect the pairs.
|
809 |
|
810 | **Complexity**: `O(log(n))` where `n` is the length of the smallest list.
|
811 |
|
812 | **Example**
|
813 |
|
814 | ```js
|
815 | const names = list("a", "b", "c", "d", "e");
|
816 | const years = list(0, 1, 2, 3, 4, 5, 6);
|
817 | //=> list(["a", 0], ["b", 1], ["c", 2], ["d", 3], ["e", 4]);
|
818 | ```
|
819 |
|
820 | ### `sort`
|
821 |
|
822 | Sorts the given list. The list should contain values that can be compared using
|
823 | the `<` operator or values that implement the Fantasy Land
|
824 | [Ord](https://github.com/fantasyland/fantasy-land#ord) specification.
|
825 |
|
826 | Performs a stable sort.
|
827 |
|
828 | **Complexity**: `O(n * log(n))`
|
829 |
|
830 | **Example**
|
831 |
|
832 | ```js
|
833 | sort(list(5, 3, 1, 8, 2)); //=> list(1, 2, 3, 5, 8)
|
834 | sort(list("e", "a", "c", "b", "d"); //=> list("a", "b", "c", "d", "e")
|
835 | ```
|
836 |
|
837 | ### `sortBy`
|
838 |
|
839 | Sort the given list by passing each value through the function and comparing
|
840 | the resulting value. The function should either return values comparable using
|
841 | `<` or values that implement the Fantasy Land
|
842 | [Ord](https://github.com/fantasyland/fantasy-land#ord) specification.
|
843 |
|
844 | Performs a stable sort.
|
845 |
|
846 | **Complexity**: `O(n * log(n))`
|
847 |
|
848 | **Example**
|
849 |
|
850 | ```js
|
851 | sortBy(
|
852 | o => o.n,
|
853 | list({ n: 4, m: "foo" }, { n: 3, m: "bar" }, { n: 1, m: "baz" })
|
854 | );
|
855 | //=> list({ n: 1, m: "baz" }, { n: 3, m: "bar" }, { n: 4, m: "foo" })
|
856 |
|
857 | sortBy(s => s.length, list("foo", "bar", "ba", "aa", "list", "z"));
|
858 | //=> list("z", "ba", "aa", "foo", "bar", "list")
|
859 | ```
|
860 |
|
861 | ### `sortWith`
|
862 |
|
863 | Sort the given list by comparing values using the given function. The function
|
864 | receieves two values and should return `-1` if the first value is stricty
|
865 | larger than the second, `0` is they are equal and `1` if the first values is
|
866 | strictly smaller than the second.
|
867 |
|
868 | Note that the comparison function is equivalent to the one required by
|
869 | [`Array.prototype.sort`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort).
|
870 |
|
871 | Performs a stable sort.
|
872 |
|
873 | **Complexity**: `O(n * log(n))`
|
874 |
|
875 | **Example**
|
876 |
|
877 | ```js
|
878 | sortWith((a, b) => {
|
879 | if (a === b) {
|
880 | return 0;
|
881 | } else if (a < b) {
|
882 | return -1;
|
883 | } else {
|
884 | return 1;
|
885 | }
|
886 | }, list(5, 3, 1, 8, 2)); //=> list(1, 2, 3, 5, 8)
|
887 | ```
|
888 |
|
889 | ### Folds
|
890 |
|
891 | ### `isList`
|
892 |
|
893 | Returns `true` if the given argument is a list.
|
894 |
|
895 | **Complexity**: `O(1)`
|
896 |
|
897 | **Example**
|
898 |
|
899 | ```js
|
900 | isList([0, 1, 2]); //=> false
|
901 | isList("string"); //=> false
|
902 | isList({ foo: 0, bar: 1 }); //=> false
|
903 | isList(list(0, 1, 2)); //=> true
|
904 | ```
|
905 |
|
906 | ### `equals`
|
907 |
|
908 | Returns true if the two lists are equivalent.
|
909 |
|
910 | **Complexity**: `O(n)`
|
911 |
|
912 | **Example**
|
913 |
|
914 | ```js
|
915 | equals(list(0, 1, 2, 3), list(0, 1, 2, 3)); //=> true
|
916 | equals(list("a", "b", "c"), list("a", "z", "c")); //=> false
|
917 | ```
|
918 |
|
919 | ### `toArray`
|
920 |
|
921 | Converts a list into an array.
|
922 |
|
923 | **Complexity**: `O(n)`
|
924 |
|
925 | **Example**
|
926 |
|
927 | ```js
|
928 | toArray(list(0, 1, 2, 3, 4)); //=> [0, 1, 2, 3, 4]
|
929 | ```
|
930 |
|
931 | ### `nth`
|
932 |
|
933 | Gets the `n`th element of the list. If `n` is out of bounds
|
934 | `undefined` is returned.
|
935 |
|
936 | **Complexity**: `O(log(n))`, practically constant
|
937 |
|
938 | **Example**
|
939 |
|
940 | ```js
|
941 | const l = list(0, 1, 2, 3, 4);
|
942 | nth(2, l); //=> 2
|
943 | ```
|
944 |
|
945 | ### `length`
|
946 |
|
947 | Returns the length of a list. I.e. the number of elements that it
|
948 | contains.
|
949 |
|
950 | **Complexity**: `O(1)`
|
951 |
|
952 | **Example**
|
953 |
|
954 | ```js
|
955 | length(list(0, 1, 2, 3)); //=> 4
|
956 | ```
|
957 |
|
958 | ### `first`
|
959 |
|
960 | Returns the first element of the list. If the list is empty the
|
961 | function returns `undefined`.
|
962 |
|
963 | **Aliases**: `head`
|
964 |
|
965 | **Complexity**: `O(1)`
|
966 |
|
967 | **Example**
|
968 |
|
969 | ```js
|
970 | first(list(0, 1, 2, 3)); //=> 0
|
971 | first(list()); //=> undefined
|
972 | ```
|
973 |
|
974 | ### `last`
|
975 |
|
976 | Returns the last element of the list. If the list is empty the
|
977 | function returns `undefined`.
|
978 |
|
979 | **Complexity**: `O(1)`
|
980 |
|
981 | **Example**
|
982 |
|
983 | ```js
|
984 | last(list(0, 1, 2, 3)); //=> 3
|
985 | last(list()); //=> undefined
|
986 | ```
|
987 |
|
988 | ### `foldl`
|
989 |
|
990 | Folds a function over a list. Left-associative.
|
991 |
|
992 | **Aliases**: `reduce`
|
993 |
|
994 | **Complexity**: `O(n)`
|
995 |
|
996 | **Example**
|
997 |
|
998 | ```js
|
999 | foldl((n, m) => n - m, 1, list(2, 3, 4, 5));
|
1000 | 1 - 2 - 3 - 4 - 5; //=> -13
|
1001 | ```
|
1002 |
|
1003 | ### `foldr`
|
1004 |
|
1005 | Folds a function over a list. Right-associative.
|
1006 |
|
1007 | **Aliases**: `reduceRight`
|
1008 |
|
1009 | **Complexity**: `O(n)`
|
1010 |
|
1011 | **Example**
|
1012 |
|
1013 | ```js
|
1014 | foldr((n, m) => n - m, 5, list(1, 2, 3, 4));
|
1015 | 1 - (2 - (3 - (4 - 5))); //=> 3
|
1016 | ```
|
1017 |
|
1018 | ### `forEach`
|
1019 |
|
1020 | Invokes a given callback for each element in the list from left to
|
1021 | right. Returns `undefined`.
|
1022 |
|
1023 | This function is very similar to `map`. It should be used instead of
|
1024 | `map` when the mapping function has side-effects. Whereas `map`
|
1025 | constructs a new list `forEach` merely returns `undefined`. This makes
|
1026 | `forEach` faster when the new list is unneeded.
|
1027 |
|
1028 | **Complexity**: `O(n)`
|
1029 |
|
1030 | **Example**
|
1031 |
|
1032 | ```js
|
1033 | const l = list(0, 1, 2);
|
1034 | forEach(element => console.log(element));
|
1035 | //=> 0
|
1036 | //=> 1
|
1037 | //=> 2
|
1038 | ```
|
1039 |
|
1040 | ### `every`
|
1041 |
|
1042 | Returns `true` if and only if the predicate function returns `true`
|
1043 | for all elements in the given list.
|
1044 |
|
1045 | **Aliases**: `all`
|
1046 |
|
1047 | **Complexity**: `O(n)`
|
1048 |
|
1049 | **Example**
|
1050 |
|
1051 | ```js
|
1052 | const isEven = n => n % 2 === 0;
|
1053 | every(isEven, empty()); //=> true
|
1054 | every(isEven, list(2, 4, 6, 8)); //=> true
|
1055 | every(isEven, list(2, 3, 4, 6, 7, 8)); //=> false
|
1056 | every(isEven, list(1, 3, 5, 7)); //=> false
|
1057 | ```
|
1058 |
|
1059 | ### `some`
|
1060 |
|
1061 | Returns `true` if and only if there exists an element in the list for
|
1062 | which the predicate returns `true`.
|
1063 |
|
1064 | **Aliases**: `any`
|
1065 |
|
1066 | **Complexity**: `O(n)`
|
1067 |
|
1068 | **Example**
|
1069 |
|
1070 | ```js
|
1071 | const isEven = n => n % 2 === 0;
|
1072 | some(isEven, empty()); //=> false
|
1073 | some(isEven, list(2, 4, 6, 8)); //=> true
|
1074 | some(isEven, list(2, 3, 4, 6, 7, 8)); //=> true
|
1075 | some(isEven, list(1, 3, 5, 7)); //=> false
|
1076 | ```
|
1077 |
|
1078 | ### `indexOf`
|
1079 |
|
1080 | Returns the index of the first element in the list that is equal to
|
1081 | the given element. If no such element is found the function returns
|
1082 | `-1`.
|
1083 |
|
1084 | **Complexity**: `O(n)`
|
1085 |
|
1086 | **Example**
|
1087 |
|
1088 | ```js
|
1089 | const l = list(12, 4, 2, 89, 6, 18, 7);
|
1090 | indexOf(12, l); //=> 0
|
1091 | indexOf(89, l); //=> 3
|
1092 | indexOf(10, l); //=> -1
|
1093 | ```
|
1094 |
|
1095 | ### `find`
|
1096 |
|
1097 | Returns the first element for which the predicate returns `true`. If
|
1098 | no such element is found the function returns `undefined`.
|
1099 |
|
1100 | **Complexity**: `O(n)`
|
1101 |
|
1102 | **Example**
|
1103 |
|
1104 | ```js
|
1105 | find(isEven, list(1, 3, 5, 6, 7, 9, 10)); //=> 6
|
1106 | find(isEven, list(1, 3, 5, 7, 9)); //=> undefined
|
1107 | ```
|
1108 |
|
1109 | ### `findIndex`
|
1110 |
|
1111 | Returns the index of the first element for which the predicate returns
|
1112 | `true`. If no such element is found the function returns `-1`.
|
1113 |
|
1114 | **Complexity**: `O(n)`
|
1115 |
|
1116 | **Example**
|
1117 |
|
1118 | ```js
|
1119 | findIndex(isEven, list(1, 3, 5, 6, 7, 9, 10)); //=> 3
|
1120 | findIndex(isEven, list(1, 3, 5, 7, 9)); //=> -1
|
1121 | ```
|
1122 |
|
1123 | ### `none`
|
1124 |
|
1125 | Returns `true` if and only if the predicate function returns `false`
|
1126 | for all elements in the given list.
|
1127 |
|
1128 | **Complexity**: `O(n)`
|
1129 |
|
1130 | **Example**
|
1131 |
|
1132 | ```js
|
1133 | const isEven = n => n % 2 === 0;
|
1134 | none(isEven, empty()); //=> true
|
1135 | none(isEven, list(2, 4, 6, 8)); //=> false
|
1136 | none(isEven, list(2, 3, 4, 6, 7, 8)); //=> false
|
1137 | none(isEven, list(1, 3, 5, 7)); //=> true
|
1138 | ```
|
1139 |
|
1140 | ### `includes`
|
1141 |
|
1142 | Returns `true` if the list contains the specified element. Otherwise
|
1143 | it returns `false`.
|
1144 |
|
1145 | **Aliases**: `contains`
|
1146 |
|
1147 | **Complexity**: `O(n)`
|
1148 |
|
1149 | **Example**
|
1150 |
|
1151 | ```js
|
1152 | includes(3, list(0, 1, 2, 3, 4, 5)); //=> true
|
1153 | includes(3, list(0, 1, 2, 4, 5)); //=> false
|
1154 | ```
|
1155 |
|
1156 | ### `join`
|
1157 |
|
1158 | Concats the strings in a list separated by a specified separator.
|
1159 |
|
1160 | **Complexity**: `O(n)`
|
1161 |
|
1162 | **Example**
|
1163 |
|
1164 | ```js
|
1165 | join(", ", list("one", "two", "three")); //=> "one, two, three"
|
1166 | ```
|
1167 |
|
1168 | ## Benchmarks
|
1169 |
|
1170 | The benchmarks are located in the [`bench` directory](/test/bench).
|