• Effekt Logo Effekt Library
    • list
      • List
        • Nil
        • Cons
      • empty
      • singleton
      • fill
      • build
      • isEmpty
      • nonEmpty
      • head
      • tail
      • headOption
      • last
      • get
      • foreach
      • foreach
      • foreachIndex
      • foreachIndex
      • map
      • collect
      • flatMap
      • all
      • any
      • count
      • foldLeft
      • foldRight
      • sum
      • size
      • reverse
      • reverseOnto
      • append
      • join
      • join
      • take
      • drop
      • slice
      • splitAt
      • updateAt
      • modifyAt
      • deleteAt
      • insert
      • replace
      • zip
      • zipWith
      • unzip
      • partition
      • sequences
      • ascending
      • descending
      • mergeAll
      • mergePairs
      • merge
      • sortBy
      • sort
      • sort
      • isSortedBy
      • show
      • show
      • show
      • show
      • show
      • println
      • println
      • println
      • println
    • list
      • Jump to source: libraries/common/list.effekt
      Example usage: examples/stdlib/list
      • List [A]
        • Immutable linked list for finite sequences of elements.
        • Nil
        • Cons (head: A, tail: List[A])
      • empty [A]: List[A] / {} 
        • Create an empty list.

O(1)
      • singleton [A] (x: A): List[A] / {} 
        • Create a list with one element.

O(1)
      • fill [A] (size: Int, default: A): List[A] / {} 
        • Create a list of length `size` where all elements are `default`.

O(size)
      • build [A] (size: Int) { index: (Int) => A }: List[A] / {} 
        • Create a list from a function `index` of given `size`.

O(size)
      • isEmpty [A] (l: List[A]): Bool / {} 
        • Check if list is empty.

O(1)
      • nonEmpty [A] (l: List[A]): Bool / {} 
        • Check if list is nonempty.

O(1)
      • head [A] (l: List[A]): A / {Exception[MissingValue]} 
        • Return the first element of a given list.
Throws a `MissingValue` exception if it's empty.

O(1)
      • tail [A] (l: List[A]): List[A] / {Exception[MissingValue]} 
        • Return all elements of a given list except the first element.
Throws a `MissingValue` exception if it's empty.

O(1)
      • headOption [A] (l: List[A]): Option[A] / {} 
        • Return the first element of a given list.
Returns `None()` if it's empty.

O(1)
      • last [A] (l: List[A]): A / {Exception[MissingValue]} 
        • Returns the last element of a given list.

O(N)
      • get [A] (list: List[A], index: Int): A / {Exception[OutOfBounds]} 
        • Get the value at given index.

O(N)
      • foreach [A] (l: List[A]) { f: (A) => Unit }: Unit / {} 
        • Traverse a list, applying the given action on every element.

O(N)
      • foreach [A] (l: List[A]) { f: (A){Control} => Unit }: Unit / {} 
        • Traverse a list, applying the given action on every element.

O(N)
      • foreachIndex [A] (list: List[A]) { f: (Int, A) => Unit }: Unit / {} 
        • Traverse a list, applying the given action on every element and its (zero-based) index.

O(N)
      • foreachIndex [A] (list: List[A]) { f: (Int, A){Control} => Unit }: Unit / {} 
        • Traverse a list, applying the given action on every element and its (zero-based) index.

O(N)
      • map [A, B] (l: List[A]) { f: (A) => B }: List[B] / {} 
        • Map a function `f` over elements in a given list.

O(N)
      • collect [A, B] (l: List[A]) { f: (A) => Option[B] }: List[B] / {} 
        • Map a function `f` over elements in a given list,
keeping only the elements for which the function returned `Some(...)`,
discarding the elements for which the function returned `None()`.

O(N)
      • flatMap [A, B] (l: List[A]) { f: (A) => List[B] }: List[B] / {} 
        • Map a function `f` over elements in a given list and concatenate the results.

O(N)
      • all [A] (list: List[A]) { predicate: (A) => Bool }: Bool / {} 
        • Check if predicate is true for all elements of the given list.

O(N)
      • any [A] (list: List[A]) { predicate: (A) => Bool }: Bool / {} 
        • Check if predicate is true for at least one element of the given list.

O(N)
      • count [A] (list: List[A]) { predicate: (A) => Bool }: Int / {} 
        • Count how many elements of a list satisfy the given predicate.

Examples:
```
> ["AB", "BC", "A", "GG", "AAA"].count { x => x.length == 2 }
3

> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].count { x => (x * 2) > 10 }
5
```
O(N)
      • foldLeft [A, B] (l: List[A], init: B) { f: (B, A) => B }: B / {} 
        • Fold a list using `f`, starting from the left given a starting value.

O(N)
      • foldRight [A, B] (l: List[A], init: B) { f: (A, B) => B }: B / {} 
        • Fold a list using `f`, starting from the right given a starting value.

O(N)
      • sum (list: List[Int]): Int / {} 
        • Sum the elements of the list.

O(N)
      • size [A] (l: List[A]): Int / {} 
        • Calculate the size of the list.

O(N)
      • reverse [A] (l: List[A]): List[A] / {} 
        • Reverse the list.

O(N)
      • reverseOnto [A] (l: List[A], other: List[A]): List[A] / {} 
        • Reverse a list `l` and append `other` to it.

Example:
```
> [1,2,3].reverseOnto([4,5,6])
[3,2,1,4,5,6]
```

O(|l|)
      • append [A] (l: List[A], other: List[A]): List[A] / {} 
        • Concatenate list `l` with list `other`:

Example:
```
> [1,2,3].append([4,5,6])
[1,2,3,4,5,6]
```

O(N)
      • join [A] (lists: List[List[A]]): List[A] / {} 
        • Flatten a list of lists into a single list.

Examples:
```
> [[1, 2, 3], [4, 5], [6]].join()
[1, 2, 3, 4, 5, 6]

> [[]].join()
[]
```

O(N)
      • join [A] (lists: List[List[A]], between: List[A]): List[A] / {} 
        • Flatten a list of lists into a single list,
putting the `between` list in between each list in the input.

Examples:
```
> [[100], [200, 300], [400]].join([1, 2, 3])
[100, 1, 2, 3, 200, 300, 1, 2, 3, 400]

> [[]].join([1, 2, 3])
[]
```

O(N)
      • take [A] (l: List[A], n: Int): List[A] / {} 
        • Take the first `n` elements of a given list.

Examples:
```
> [1, 2, 3].take(2)
[1, 2]

> [1, 2, 3].take(0)
[]

> [1, 2, 3].take(3)
[1, 2, 3]

> [1, 2, 3].take(5)
[1, 2, 3]

> [1, 2, 3].take(-1)
[]
```

O(n)
      • drop [A] (l: List[A], n: Int): List[A] / {} 
        • Drop the first `n` elements of a given list.

Examples:
```
> [1, 2, 3].drop(2)
[3]

> [1, 2, 3].drop(0)
[1, 2, 3]

> [1, 2, 3].drop(3)
[]

> [1, 2, 3].drop(5)
[]

> [1, 2, 3].drop(-1)
[1, 2, 3]
```

O(n)
      • slice [A] (list: List[A], start: Int, stopExclusive: Int): List[A] / {} 
        • Return a slice of a given list from the starting index (inclusive)
to the given end index (exclusive).

Examples:
```
> [1, 2, 3, 4, 5, 6].slice(1, 4)
[2, 3, 4]

> [1, 2, 3, 4, 5, 6].slice(1, 2)
[2]

> [1, 2, 3, 4, 5, 6].slice(1, 1)
[]

> [1, 2, 3, 4, 5, 6].slice(4, 1)
[]

> [1, 2, 3, 4, 5, 6].slice(-100, 100)
[1, 2, 3, 4, 5, 6]
```

O(N)
      • splitAt [A] (list: List[A], index: Int): Tuple2[List[A], List[A]] / {} 
        • Split the list at given index.

Law: `val (l, r) = list.splitAt(i); l.append(r) === list`

O(N)
      • updateAt [A] (list: List[A], index: Int) { update: (A) => A }: List[A] / {} 
        • Update the element at given index in the list using the `update` function.
Returns the original list if the index is out of bounds.

See: `modifyAt`
Examples:
```
> [1, 2, 3].updateAt(1) { n => n + 100 }
[1, 102, 3]

> [1, 2, 3].updateAt(10) { n => n + 100 }
[1, 2, 3]
```

O(N)
      • modifyAt [A] (list: List[A], index: Int) { update: (A) => A }: List[A] / {Exception[OutOfBounds]} 
        • Modify the element at given index in the list using the `update` function.
Throws `OutOfBounds` if the index is out of bounds.

See: `updateAt`
Examples:
```
> [1, 2, 3].modifyAt(1) { n => n + 100 }
Some([1, 102, 3])

> [1, 2, 3].modifyAt(10) { n => n + 100 }
None()
```

O(N)
      • deleteAt [A] (list: List[A], index: Int): List[A] / {} 
        • Delete the element at given index in the list.

Example:
```
> [1, 2, 3, 4].deleteAt(1)
[1, 3, 4]

> [1, 2, 3, 4].deleteAt(-1)
[1, 2, 3, 4]

> [1, 2, 3, 4].deleteAt(10)
[1, 2, 3, 4]
```

O(N)
      • insert [A] (list: List[A], index: Int, x: A): List[A] / {} 
        • Add an element at given index in the list.

Examples:
```
> [1, 2, 3].insert(-1, 0)
[0, 1, 2, 3]

> [1, 2, 3].insert(0, 0)
[0, 1, 2, 3]

> [1, 2, 3].insert(1, 0)
[1, 0, 2, 3]

> [1, 2, 3].insert(3, 0)
[1, 2, 3, 0]

> [1, 2, 3].insert(10, 0)
[1, 2, 3, 0]
```

O(N)
      • replace [A] (list: List[A], index: Int, x: A): List[A] / {} 
        • Replace an element at given index in the list.
Returns the original list when the index is out of bounds.

Examples:
```
> [1, 2, 3].replace(0, 42)
[42, 2, 3]

> [1, 2, 3].replace(-1, 42)
[1, 2, 3]

> [1, 2, 3].replace(10, 42)
[1, 2, 3]
```

O(N)
      • zip [A, B] (left: List[A], right: List[B]): List[Tuple2[A, B]] / {} 
        • Produce a list of pairs from a pair of lists.
The length of the result is the minimum of lengths of the two lists.

Examples:
```
> zip([1, 2, 3], [100, 200, 300])
[(1, 100), (2, 200), (3, 300)]

> zip([1, 2, 3], Nil[Int]())
[]

> zip(Nil[Int](), [1, 2, 3])
[]

> zip([1, 2, 3], [42])
[(1, 42)]
```

O(N)
      • zipWith [A, B, C] (left: List[A], right: List[B]) { combine: (A, B) => C }: List[C] / {} 
        • Combine two lists with the given function.
The length of the result is the minimum of lengths of the two lists.

Examples:
```
> zipWith([1, 2, 3], [100, 200, 300]) { (a, b) => a + b }
[101, 202, 303]

> zipWith([1, 2, 3], Nil[Int]()) { (a, b) => a + b }
[]

> zipWith(Nil[Int](), [1, 2, 3]) { (a, b) => a + b }
[]

> zipWith([1, 2, 3], [42]) { (a, b) => a + b }
[43]
```

O(N)
      • unzip [A, B] (pairs: List[Tuple2[A, B]]): Tuple2[List[A], List[B]] / {} 
        • Produce a pair of lists from a list of pairs.

Examples:
```
> [(1, 100), (2, 200), (3, 300)].unzip()
([1, 2, 3], [100, 200, 300])
```

O(N)
      • partition [A] (l: List[A]) { pred: (A) => Bool }: Tuple2[List[A], List[A]] / {} 
        • Partition a given list into two lists.
The left list contains the elements that satsify the predicate,
the right list contains the elements that do not.

O(N)
      • sequences [A] (list: List[A]) { compare: (A, A) => Bool }: List[List[A]] / {} 
        • Splits the given list into monotonic segments (so a list of lists).

Internally used in the mergesort 'sortBy' to prepare the to-be-merged partitions.
      • ascending [A] (current: A, rest: List[A]) { runDiff: (List[A]) => List[A] } { compare: (A, A) => Bool }: List[List[A]] / {} 
        • When in an ascending sequence, try to add `current` to `run` (if possible)
      • descending [A] (current: A, run: List[A], rest: List[A]) { compare: (A, A) => Bool }: List[List[A]] / {} 
        • When in an descending sequence, try to add `current` to `run` (if possible)
      • mergeAll [A] (runs: List[List[A]]) { compare: (A, A) => Bool }: List[A] / {}
      • mergePairs [A] (runs: List[List[A]]) { compare: (A, A) => Bool }: List[List[A]] / {}
      • merge [A] (l1: List[A], l2: List[A]) { compare: (A, A) => Bool }: List[A] / {}
      • sortBy [A] (list: List[A]) { lessOrEqual: (A, A) => Bool }: List[A] / {} 
        • Sort a list given a comparison operator (like less-or-equal!)
The sorting algorithm is stable and should act reasonably well on partially sorted data.

Examples:
```
> [1, 3, -1, 5].sortBy { (a, b) => a <= b }
[-1, 1, 3, 5]

> [1, 3, -1, 5].sortBy { (a, b) => a >= b }
[5, 3, 1, -1]

> [(1, 0), (0, 1), (-1, 1), (0, 0)].sortBy { (a, b) => a.first + a.second <= b.first + b.second }
[(1, -1), (0, 0), (1, 0), (0, 1)]

> Nil[Int]().sortBy { (a, b) => a <= b }
[]
```

Note: this implementation is not stacksafe!
(works for ~5M random elements just fine, but OOMs on ~10M random elements)

O(N log N) worstcase
      • sort (l: List[Int]): List[Int] / {} 
        • Sort a list of integers in an ascending order.
See 'sortBy' for more details.

O(N log N) worstcase
      • sort (l: List[Double]): List[Double] / {} 
        • Sort a list of doubles in an ascending order.
See 'sortBy' for more details.

O(N log N) worstcase
      • isSortedBy [A] (list: List[A]) { lessOrEqual: (A, A) => Bool }: Bool / {} 
        • Check if a list is sorted according to the given comparison function (less-or-equal).

O(N)
      • show [A] (l: List[A]) { showA: (A) => String }: String / {}
      • show (l: List[Int]): String / {}
      • show (l: List[Double]): String / {}
      • show (l: List[Bool]): String / {}
      • show (l: List[String]): String / {}
      • println (l: List[Int]): Unit / {}
      • println (l: List[Double]): Unit / {}
      • println (l: List[Bool]): Unit / {}
      • println (l: List[String]): Unit / {}