/**
* A data type for immutable linked lists representing ordered collections of elements of type `A`.
*
* This data type is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access pattern, for example, random access or FIFO, consider using a collection more suited to this than `List`.
*
* **Performance**
*
* - Time: `List` has `O(1)` prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list. This includes the index-based lookup of elements, `length`, `append` and `reverse`.
* - Space: `List` implements structural sharing of the tail list. This means that many operations are either zero- or constant-memory cost.
*
* @since 1.0.0
*/
/**
* This file is ported from
*
* Scala (https://www.scala-lang.org)
*
* Copyright EPFL and Lightbend, Inc.
*
* Licensed under Apache License 2.0
* (http://www.apache.org/licenses/LICENSE-2.0).
*/
import * as Chunk from "@effect/data/Chunk"
import * as Either from "@effect/data/Either"
import * as Equal from "@effect/data/Equal"
import * as Equivalence from "@effect/data/Equivalence"
import { dual, identity, unsafeCoerce } from "@effect/data/Function"
import * as Hash from "@effect/data/Hash"
import { type Inspectable, NodeInspectSymbol, toJSON, toString } from "@effect/data/Inspectable"
import * as Option from "@effect/data/Option"
import type { Pipeable } from "@effect/data/Pipeable"
import { pipeArguments } from "@effect/data/Pipeable"
import type { Predicate, Refinement } from "@effect/data/Predicate"
import { isObject } from "@effect/data/Predicate"
import * as ReadonlyArray from "@effect/data/ReadonlyArray"
/**
* Represents an immutable linked list of elements of type `A`.
*
* A `List` is optimal for last-in-first-out (LIFO), stack-like access patterns.
* If you need another access pattern, for example, random access or FIFO,
* consider using a collection more suited for that other than `List`.
*
* @since 1.0.0
* @category models
*/
export type List = Cons | Nil
/**
* @since 1.0.0
* @category symbol
*/
export const TypeId: unique symbol = Symbol.for("@effect/data/List")
/**
* @since 1.0.0
* @category symbol
*/
export type TypeId = typeof TypeId
/**
* @since 1.0.0
* @category models
*/
export interface Nil extends Iterable, Equal.Equal, Pipeable, Inspectable {
readonly [TypeId]: TypeId
readonly _tag: "Nil"
}
/**
* @since 1.0.0
* @category models
*/
export interface Cons extends Iterable, Equal.Equal, Pipeable, Inspectable {
readonly [TypeId]: TypeId
readonly _tag: "Cons"
readonly head: A
readonly tail: List
}
/**
* Converts the specified `List` to a `ReadonlyArray`.
*
* @category conversions
* @since 1.0.0
*/
export const toReadonlyArray = (self: List): ReadonlyArray => Array.from(self)
/**
* @category equivalence
* @since 1.0.0
*/
export const getEquivalence = (isEquivalent: Equivalence.Equivalence): Equivalence.Equivalence> =>
Equivalence.mapInput(ReadonlyArray.getEquivalence(isEquivalent), toReadonlyArray)
const _equivalence = getEquivalence(Equal.equals)
const ConsProto: Omit, "head" | "tail"> = {
[TypeId]: TypeId,
_tag: "Cons",
toString(this: Cons) {
return toString(this.toJSON())
},
toJSON(this: Cons) {
return {
_id: "List",
_tag: "Cons",
values: toReadonlyArray(this).map(toJSON)
}
},
[NodeInspectSymbol]() {
return this.toJSON()
},
[Equal.symbol](this: Cons, that: unknown): boolean {
return isList(that) &&
this._tag === that._tag &&
_equivalence(this, that)
},
[Hash.symbol](this: Cons): number {
return Hash.array(toReadonlyArray(this))
},
[Symbol.iterator](this: Cons): Iterator {
let done = false
// eslint-disable-next-line @typescript-eslint/no-this-alias
let self: List = this
return {
next() {
if (done) {
return this.return!()
}
if (self._tag === "Nil") {
done = true
return this.return!()
}
const value: unknown = self.head
self = self.tail
return { done, value }
},
return(value?: unknown) {
if (!done) {
done = true
}
return { done: true, value }
}
}
},
pipe() {
return pipeArguments(this, arguments)
}
}
interface MutableCons extends Cons {
head: A
tail: List
}
const makeCons = (head: A, tail: List): MutableCons => {
const cons = Object.create(ConsProto)
cons.head = head
cons.tail = tail
return cons
}
const NilProto: Nil = {
[TypeId]: TypeId,
_tag: "Nil",
toString() {
return toString(this.toJSON())
},
toJSON() {
return {
_id: "List",
_tag: "Nil"
}
},
[NodeInspectSymbol]() {
return this.toJSON()
},
[Hash.symbol](): number {
return Hash.array(toReadonlyArray(this))
},
[Equal.symbol](that: unknown): boolean {
return isList(that) && this._tag === that._tag
},
[Symbol.iterator](): Iterator {
return {
next() {
return { done: true, value: undefined }
}
}
},
pipe() {
return pipeArguments(this, arguments)
}
} as const
const _Nil = Object.create(NilProto) as Nil
/**
* Returns `true` if the specified value is a `List`, `false` otherwise.
*
* @since 1.0.0
* @category refinements
*/
export const isList: {
(u: Iterable): u is List
(u: unknown): u is List
} = (u: unknown): u is List => isObject(u) && TypeId in u
/**
* Returns `true` if the specified value is a `List.Nil`, `false` otherwise.
*
* @since 1.0.0
* @category refinements
*/
export const isNil = (self: List): self is Nil => self._tag === "Nil"
/**
* Returns `true` if the specified value is a `List.Cons`, `false` otherwise.
*
* @since 1.0.0
* @category refinements
*/
export const isCons = (self: List): self is Cons => self._tag === "Cons"
/**
* Returns the number of elements contained in the specified `List`
*
* @since 1.0.0
* @category getters
*/
export const size = (self: List): number => {
let these = self
let len = 0
while (!isNil(these)) {
len += 1
these = these.tail
}
return len
}
/**
* Constructs a new empty `List`.
*
* @since 1.0.0
* @category constructors
*/
export const nil = (): List => _Nil
/**
* Constructs a new `List.Cons` from the specified `head` and `tail` values.
*
* @since 1.0.0
* @category constructors
*/
export const cons = (head: A, tail: List): Cons => makeCons(head, tail)
/**
* Constructs a new empty `List`.
*
* Alias of {@link nil}.
*
* @since 1.0.0
* @category constructors
*/
export const empty = nil
/**
* Constructs a new `List` from the specified value.
*
* @since 1.0.0
* @category constructors
*/
export const of = (value: A): Cons => makeCons(value, _Nil)
/**
* Constructs a new `List` from the specified `Iterable`.
*
* @since 1.0.0
* @category constructors
*/
export const fromIterable = (prefix: Iterable): List => {
const iterator = prefix[Symbol.iterator]()
let next: IteratorResult
if ((next = iterator.next()) && !next.done) {
const result = makeCons(next.value, _Nil)
let curr = result
while ((next = iterator.next()) && !next.done) {
const temp = makeCons(next.value, _Nil)
curr.tail = temp
curr = temp
}
return result
} else {
return _Nil
}
}
/**
* Constructs a new `List` from the specified values.
*
* @since 1.0.0
* @category constructors
*/
export const make = ]>(
...elements: Elements
): Cons => fromIterable(elements) as any
/**
* Appends the specified element to the end of the `List`, creating a new `Cons`.
*
* @category concatenating
* @since 1.0.0
*/
export const append: {
(element: B): (self: List) => Cons
(self: List, element: B): Cons
} = dual(2, (self: List, element: B): Cons => appendAllNonEmpty(self, of(element)))
/**
* Concatentates the specified lists together.
*
* @category concatenating
* @since 1.0.0
*/
export const appendAll: {
(that: List): (self: List) => List
(self: List, that: List): List
} = dual(2, (self: List, that: List): List => prependAll(that, self))
/**
* @category concatenating
* @since 1.0.0
*/
export const appendAllNonEmpty: {
(that: Cons): (self: List) => Cons
(that: List): (self: Cons) => Cons
(self: List, that: Cons): Cons
(self: Cons, that: List): Cons
} = dual(2, (self: Cons, that: List): Cons => appendAll(self, that) as any)
/**
* Prepends the specified element to the beginning of the list.
*
* @category concatenating
* @since 1.0.0
*/
export const prepend: {
(element: B): (self: List) => Cons
(self: List, element: B): Cons
} = dual(2, (self: List, element: B): Cons => cons(element, self))
/**
* Prepends the specified prefix list to the beginning of the specified list.
*
* @category concatenating
* @since 1.0.0
*/
export const prependAll: {
(prefix: List): (self: List) => List
(self: List, prefix: List): List
} = dual(2, (self: List, prefix: List): List => {
if (isNil(self)) {
return prefix
} else if (isNil(prefix)) {
return self
} else {
const result = makeCons(prefix.head, self)
let curr = result
let that = prefix.tail
while (!isNil(that)) {
const temp = makeCons(that.head, self)
curr.tail = temp
curr = temp
that = that.tail
}
return result
}
})
/**
* @category concatenating
* @since 1.0.0
*/
export const prependAllNonEmpty: {
(that: Cons): (self: List) => Cons
(that: List): (self: Cons) => Cons
(self: List, that: Cons): Cons
(self: Cons, that: List): Cons
} = dual(2, (self: Cons, that: List): Cons => prependAll(self, that) as any)
/**
* Prepends the specified prefix list (in reverse order) to the beginning of the
* specified list.
*
* @category concatenating
* @since 1.0.0
*/
export const prependAllReversed: {
(prefix: List): (self: List) => List
(self: List, prefix: List): List
} = dual(2, (self: List, prefix: List): List => {
let out: List = self
let pres = prefix
while (isCons(pres)) {
out = makeCons(pres.head, out)
pres = pres.tail
}
return out
})
/**
* Drops the first `n` elements from the specified list.
*
* @since 1.0.0
* @category combinators
*/
export const drop: {
(n: number): (self: List) => List
(self: List, n: number): List
} = dual(2, (self: List, n: number): List => {
if (n <= 0) {
return self
}
if (n >= size(self)) {
return _Nil
}
let these = self
let i = 0
while (!isNil(these) && i < n) {
these = these.tail
i += 1
}
return these
})
/**
* Check if a predicate holds true for every `List` element.
*
* @since 1.0.0
* @category elements
*/
export const every: {
(refinement: Refinement): (self: List) => self is List
(predicate: Predicate): (self: List) => boolean
(self: List, refinement: Refinement): self is List
(self: List, predicate: Predicate): boolean
} = dual(2, (self: List, refinement: Refinement): self is List => {
for (const a of self) {
if (!refinement(a)) {
return false
}
}
return true
})
/**
* Check if a predicate holds true for some `List` element.
*
* @since 1.0.0
* @category elements
*/
export const some: {
(predicate: Predicate): (self: List) => self is Cons
(self: List, predicate: Predicate): self is Cons
} = dual(2, (self: List, predicate: Predicate): self is Cons => {
let these = self
while (!isNil(these)) {
if (predicate(these.head)) {
return true
}
these = these.tail
}
return false
})
/**
* Filters a list using the specified predicate.
*
* @since 1.0.0
* @category combinators
*/
export const filter: {
(refinement: Refinement): (self: List) => List
(predicate: Predicate): (self: List) => List
(self: List, refinement: Refinement): List
(self: List, predicate: Predicate): List
} = dual(2, (self: List, predicate: Predicate): List => noneIn(self, predicate, false))
// everything seen so far is not included
const noneIn = (
self: List,
predicate: Predicate,
isFlipped: boolean
): List => {
/* eslint-disable no-constant-condition */
while (true) {
if (isNil(self)) {
return _Nil
} else {
if (predicate(self.head) !== isFlipped) {
return allIn(self, self.tail, predicate, isFlipped)
} else {
self = self.tail
}
}
}
}
// everything from 'start' is included, if everything from this point is in we can return the origin
// start otherwise if we discover an element that is out we must create a new partial list.
const allIn = (
start: List,
remaining: List,
predicate: Predicate,
isFlipped: boolean
): List => {
/* eslint-disable no-constant-condition */
while (true) {
if (isNil(remaining)) {
return start
} else {
if (predicate(remaining.head) !== isFlipped) {
remaining = remaining.tail
} else {
return partialFill(start, remaining, predicate, isFlipped)
}
}
}
}
// we have seen elements that should be included then one that should be excluded, start building
const partialFill = (
origStart: List,
firstMiss: List,
predicate: Predicate,
isFlipped: boolean
): List => {
const newHead = makeCons(unsafeHead(origStart)!, _Nil)
let toProcess = unsafeTail(origStart)! as Cons
let currentLast = newHead
// we know that all elements are :: until at least firstMiss.tail
while (!(toProcess === firstMiss)) {
const newElem = makeCons(unsafeHead(toProcess)!, _Nil)
currentLast.tail = newElem
currentLast = unsafeCoerce(newElem)
toProcess = unsafeCoerce(toProcess.tail)
}
// at this point newHead points to a list which is a duplicate of all the 'in' elements up to the first miss.
// currentLast is the last element in that list.
// now we are going to try and share as much of the tail as we can, only moving elements across when we have to.
let next = firstMiss.tail
let nextToCopy: Cons = unsafeCoerce(next) // the next element we would need to copy to our list if we cant share.
while (!isNil(next)) {
// generally recommended is next.isNonEmpty but this incurs an extra method call.
const head = unsafeHead(next)!
if (predicate(head) !== isFlipped) {
next = next.tail
} else {
// its not a match - do we have outstanding elements?
while (!(nextToCopy === next)) {
const newElem = makeCons(unsafeHead(nextToCopy)!, _Nil)
currentLast.tail = newElem
currentLast = newElem
nextToCopy = unsafeCoerce(nextToCopy.tail)
}
nextToCopy = unsafeCoerce(next.tail)
next = next.tail
}
}
// we have remaining elements - they are unchanged attach them to the end
if (!isNil(nextToCopy)) {
currentLast.tail = nextToCopy
}
return newHead
}
/**
* Filters and maps a list using the specified partial function. The resulting
* list may be smaller than the input list due to the possibility of the partial
* function not being defined for some elements.
*
* @since 1.0.0
* @category combinators
*/
export const filterMap: {
(f: (a: A) => Option.Option): (self: List) => List
(self: List, f: (a: A) => Option.Option): List
} = dual(2, (self: List, f: (a: A) => Option.Option): List => {
const bs: Array = []
for (const a of self) {
const oa = f(a)
if (Option.isSome(oa)) {
bs.push(oa.value)
}
}
return fromIterable(bs)
})
/**
* Removes all `None` values from the specified list.
*
* @since 1.0.0
* @category combinators
*/
export const compact = (self: List>): List => filterMap(self, identity)
/**
* Returns the first element that satisfies the specified
* predicate, or `None` if no such element exists.
*
* @category elements
* @since 1.0.0
*/
export const findFirst: {
(refinement: Refinement): (self: List) => Option.Option
(predicate: Predicate): (self: List) => Option.Option
(self: List, refinement: Refinement): Option.Option
(self: List, predicate: Predicate): Option.Option
} = dual(2, (self: List, predicate: Predicate): Option.Option => {
let these = self
while (!isNil(these)) {
if (predicate(these.head)) {
return Option.some(these.head)
}
these = these.tail
}
return Option.none()
})
/**
* Flat maps a list using the specified function.
*
* @since 1.0.0
* @category sequencing
*/
export const flatMap: {
(f: (a: A) => List): (self: List) => List
(self: List, f: (a: A) => List): List
} = dual(2, (self: List, f: (a: A) => List): List => {
let rest = self
let head: MutableCons | undefined = undefined
let tail: MutableCons | undefined = undefined
while (!isNil(rest)) {
let bs = f(rest.head)
while (!isNil(bs)) {
const next = makeCons(bs.head, _Nil)
if (tail === undefined) {
head = next
} else {
tail.tail = next
}
tail = next
bs = bs.tail
}
rest = rest.tail
}
if (head === undefined) {
return _Nil
}
return head
})
/**
* @category sequencing
* @since 1.0.0
*/
export const flatMapNonEmpty: {
(f: (a: A, i: number) => Cons): (self: Cons) => Cons
(self: Cons, f: (a: A, i: number) => Cons): Cons
} = flatMap as any
/**
* Applies the specified function to each element of the `List`.
*
* @since 1.0.0
* @category combinators
*/
export const forEach: {
(f: (a: A) => B): (self: List) => void
(self: List, f: (a: A) => B): void
} = dual(2, (self: List, f: (a: A) => B): void => {
let these = self
while (!isNil(these)) {
f(these.head)
these = these.tail
}
})
/**
* Returns the first element of the specified list, or `None` if the list is
* empty.
*
* @since 1.0.0
* @category getters
*/
export const head = (self: List): Option.Option => isNil(self) ? Option.none() : Option.some(self.head)
/**
* Returns the last element of the specified list, or `None` if the list is
* empty.
*
* @since 1.0.0
* @category getters
*/
export const last = (self: List): Option.Option => isNil(self) ? Option.none() : Option.some(unsafeLast(self)!)
/**
* Applies the specified mapping function to each element of the list.
*
* @since 1.0.0
* @category combinators
*/
export const map: {
(f: (a: A) => B): (self: List) => List
(self: List, f: (a: A) => B): List
} = dual(2, (self: List, f: (a: A) => B): List => {
if (isNil(self)) {
return self as unknown as List
} else {
const head = makeCons(f(self.head), _Nil)
let nextHead = head
let rest = self.tail
while (!isNil(rest)) {
const next = makeCons(f(rest.head), _Nil)
nextHead.tail = next
nextHead = next
rest = rest.tail
}
return head
}
})
/**
* Partition a list into two lists, where the first list contains all elements
* that did not satisfy the specified predicate, and the second list contains
* all elements that did satisfy the specified predicate.
*
* @since 1.0.0
* @category combinators
*/
export const partition: {
(refinement: Refinement): (self: List) => [List>, List]
(predicate: (a: A) => boolean): (self: List) => [List, List]
(self: List, refinement: Refinement): [List>, List]
(self: List, predicate: (a: A) => boolean): [List, List]
} = dual(2, (self: List, predicate: (a: A) => boolean): [List, List] => {
const left: Array = []
const right: Array = []
for (const a of self) {
if (predicate(a)) {
right.push(a)
} else {
left.push(a)
}
}
return [fromIterable(left), fromIterable(right)]
})
/**
* Partition a list into two lists, where the first list contains all elements
* for which the specified function returned a `Left`, and the second list
* contains all elements for which the specified function returned a `Right`.
*
* @since 1.0.0
* @category combinators
*/
export const partitionMap: {
(f: (a: A) => Either.Either): (self: List) => readonly [List, List]
(self: List, f: (a: A) => Either.Either): readonly [List, List]
} = dual(2, (self: List, f: (a: A) => Either.Either