/Nim

Module sequtils

This module implements operations for the built-in seq type which were inspired by functional programming languages.

For functional style programming you may want to pass anonymous procs to procs like `filter` to reduce typing. Anonymous procs can use the special do notation which is more convenient in certain situations.

macros, strutils

Procs

`proc concat[T](seqs: varargs[seq[T]]): seq[T]`

Takes several sequences' items and returns them inside a new sequence.

Example:

```let
s1 = @[1, 2, 3]
s2 = @[4, 5]
s3 = @[6, 7]
total = concat(s1, s2, s3)
assert total == @[1, 2, 3, 4, 5, 6, 7]```
`proc count[T](s: openArray[T]; x: T): int`

Returns the number of occurrences of the item x in the container s.

Example:

```let
s = @[1, 2, 2, 3, 2, 4, 2]
c = count(s, 2)
assert c == 4```
`proc cycle[T](s: openArray[T]; n: Natural): seq[T]`

Returns a new sequence with the items of the container s repeated n times.

Example:

```let
s = @[1, 2, 3]
total = s.cycle(3)
assert total == @[1, 2, 3, 1, 2, 3, 1, 2, 3]```
`proc repeat[T](x: T; n: Natural): seq[T]`

Returns a new sequence with the item x repeated n times.

Example:

```let
total = repeat(5, 3)
assert total == @[5, 5, 5]```
`proc deduplicate[T](s: openArray[T]): seq[T]`

Returns a new sequence without duplicates.

Example:

```let
dup1 = @[1, 1, 3, 4, 2, 2, 8, 1, 4]
dup2 = @["a", "a", "c", "d", "d"]
unique1 = deduplicate(dup1)
unique2 = deduplicate(dup2)
assert unique1 == @[1, 3, 4, 2, 8]
assert unique2 == @["a", "c", "d"]```
`proc zip[S, T](s1: openArray[S]; s2: openArray[T]): seq[tuple[a: S, b: T]]`

Returns a new sequence with a combination of the two input containers.

For convenience you can access the returned tuples through the named fields a and b. If one container is shorter, the remaining items in the longer container are discarded.

Example:

```let
short = @[1, 2, 3]
long = @[6, 5, 4, 3, 2, 1]
words = @["one", "two", "three"]
zip1 = zip(short, long)
zip2 = zip(short, words)
assert zip1 == @[(1, 6), (2, 5), (3, 4)]
assert zip2 == @[(1, "one"), (2, "two"), (3, "three")]
assert zip1.b == 4
assert zip2.b == "three"```
`proc distribute[T](s: seq[T]; num: Positive; spread = true): seq[seq[T]]`

Splits and distributes a sequence s into num sub sequences.

Returns a sequence of num sequences. For some input values this is the inverse of the concat proc. The proc will assert in debug builds if s is nil or num is less than one, and will likely crash on release builds. The input sequence s can be empty, which will produce num empty sequences.

If spread is false and the length of s is not a multiple of num, the proc will max out the first sub sequences with `1 + len(s) div num` entries, leaving the remainder of elements to the last sequence.

On the other hand, if spread is true, the proc will distribute evenly the remainder of the division across all sequences, which makes the result more suited to multithreading where you are passing equal sized work units to a thread pool and want to maximize core usage.

Example:

```let numbers = @[1, 2, 3, 4, 5, 6, 7]
assert numbers.distribute(3) == @[@[1, 2, 3], @[4, 5], @[6, 7]]
assert numbers.distribute(3, false)  == @[@[1, 2, 3], @[4, 5, 6], @]
assert numbers.distribute(6) == @[1, 2]
assert numbers.distribute(6) == @```
`proc map[T, S](s: openArray[T]; op: proc (x: T): S {...}{.closure.}): seq[S] {...}{.inline.}`

Returns a new sequence with the results of op applied to every item in the container s.

Since the input is not modified you can use this version of `map` to transform the type of the elements in the input container.

Example:

```let
a = @[1, 2, 3, 4]
b = map(a, proc(x: int): string = \$x)
assert b == @["1", "2", "3", "4"]```
`proc map[T](s: var openArray[T]; op: proc (x: var T) {...}{.closure.}) {...}{.deprecated.}`

Applies op to every item in s modifying it directly.

Note that this version of `map` requires your input and output types to be the same, since they are modified in-place.

Example:

```var a = @["1", "2", "3", "4"]
echo repr(a)
# --> ["1", "2", "3", "4"]
map(a, proc(x: var string) = x &= "42")
echo repr(a)
# --> ["142", "242", "342", "442"]```

Deprecated since version 0.12.0: Use the `apply` proc instead.

`proc apply[T](s: var openArray[T]; op: proc (x: var T) {...}{.closure.}) {...}{.inline.}`

Applies op to every item in s modifying it directly.

Note that this requires your input and output types to be the same, since they are modified in-place. The parameter function takes a `var T` type parameter.

Example:

```var a = @["1", "2", "3", "4"]
echo repr(a)
# --> ["1", "2", "3", "4"]
apply(a, proc(x: var string) = x &= "42")
echo repr(a)
# --> ["142", "242", "342", "442"]```
`proc apply[T](s: var openArray[T]; op: proc (x: T): T {...}{.closure.}) {...}{.inline.}`

Applies op to every item in s modifying it directly.

Note that this requires your input and output types to be the same, since they are modified in-place. The parameter function takes and returns a `T` type variable.

Example:

```var a = @["1", "2", "3", "4"]
echo repr(a)
# --> ["1", "2", "3", "4"]
apply(a, proc(x: string): string = x & "42")
echo repr(a)
# --> ["142", "242", "342", "442"]```
`proc filter[T](s: openArray[T]; pred: proc (x: T): bool {...}{.closure.}): seq[T] {...}{.inline.}`

Returns a new sequence with all the items that fulfilled the predicate.

Example:

```let
colors = @["red", "yellow", "black"]
f1 = filter(colors, proc(x: string): bool = x.len < 6)
f2 = filter(colors) do (x: string) -> bool : x.len > 5
assert f1 == @["red", "black"]
assert f2 == @["yellow"]```
`proc keepIf[T](s: var seq[T]; pred: proc (x: T): bool {...}{.closure.}) {...}{.inline.}`

Keeps the items in the passed sequence if they fulfilled the predicate. Same as the `filter` proc, but modifies the sequence directly.

Example:

```var floats = @[13.0, 12.5, 5.8, 2.0, 6.1, 9.9, 10.1]
keepIf(floats, proc(x: float): bool = x > 10)
assert floats == @[13.0, 12.5, 10.1]```
`proc delete[T](s: var seq[T]; first, last: Natural)`

Deletes in s the items at position first .. last. This modifies s itself, it does not return a copy.

Example:

```let outcome = @[1,1,1,1,1,1,1,1]
var dest = @[1,1,1,2,2,2,2,2,2,1,1,1,1,1]
dest.delete(3, 8)
assert outcome == dest```
`proc insert[T](dest: var seq[T]; src: openArray[T]; pos = 0)`

Inserts items from src into dest at position pos. This modifies dest itself, it does not return a copy.

Example:

```var dest = @[1,1,1,1,1,1,1,1]
let
src = @[2,2,2,2,2,2]
outcome = @[1,1,1,2,2,2,2,2,2,1,1,1,1,1]
dest.insert(src, 3)
assert dest == outcome```
`proc all[T](s: openArray[T]; pred: proc (x: T): bool {...}{.closure.}): bool`

Iterates through a container and checks if every item fulfills the predicate.

Example:

```let numbers = @[1, 4, 5, 8, 9, 7, 4]
assert all(numbers, proc (x: int): bool = return x < 10) == true
assert all(numbers, proc (x: int): bool = return x < 9) == false```
`proc any[T](s: openArray[T]; pred: proc (x: T): bool {...}{.closure.}): bool`

Iterates through a container and checks if some item fulfills the predicate.

Example:

```let numbers = @[1, 4, 5, 8, 9, 7, 4]
assert any(numbers, proc (x: int): bool = return x > 8) == true
assert any(numbers, proc (x: int): bool = return x > 9) == false```

Iterators

`iterator filter[T](s: openArray[T]; pred: proc (x: T): bool {...}{.closure.}): T`

Iterates through a container and yields every item that fulfills the predicate.

Example:

```let numbers = @[1, 4, 5, 8, 9, 7, 4]
for n in filter(numbers, proc (x: int): bool = x mod 2 == 0):
echo(\$n)
# echoes 4, 8, 4 in separate lines```

Macros

`macro mapLiterals(constructor, op: untyped; nested = true): untyped`

applies `op` to each of the atomic literals like `3` or `"abc"` in the specified `constructor` AST. This can be used to map every array element to some target type:

Example:

```let x = mapLiterals([0.1, 1.2, 2.3, 3.4], int)
doAssert x is array[4, int]```

Short notation for:

`let x = [int(0.1), int(1.2), int(2.3), int(3.4)]`

If `nested` is true, the literals are replaced everywhere in the `constructor` AST, otherwise only the first level is considered:

`mapLiterals((1, ("abc"), 2), float, nested=false)`

Produces:

`(float(1), ("abc"), float(2))`

There are no constraints for the `constructor` AST, it works for nested tuples of arrays of sets etc.

Templates

`template filterIt(s, pred: untyped): untyped`

Returns a new sequence with all the items that fulfilled the predicate.

Unlike the proc version, the predicate needs to be an expression using the `it` variable for testing, like: `filterIt("abcxyz", it == 'x')`.

Example:

```let
temperatures = @[-272.15, -2.0, 24.5, 44.31, 99.9, -113.44]
acceptable = filterIt(temperatures, it < 50 and it > -10)
notAcceptable = filterIt(temperatures, it > 50 or it < -10)
assert acceptable == @[-2.0, 24.5, 44.31]
assert notAcceptable == @[-272.15, 99.9, -113.44]```
`template keepItIf(varSeq: seq; pred: untyped)`

Convenience template around the `keepIf` proc to reduce typing.

Unlike the proc version, the predicate needs to be an expression using the `it` variable for testing, like: `keepItIf("abcxyz", it == 'x')`.

Example:

```var candidates = @["foo", "bar", "baz", "foobar"]
keepItIf(candidates, it.len == 3 and it == 'b')
assert candidates == @["bar", "baz"]```
`template allIt(s, pred: untyped): bool`

Checks if every item fulfills the predicate.

Example:

```let numbers = @[1, 4, 5, 8, 9, 7, 4]
assert allIt(numbers, it < 10) == true
assert allIt(numbers, it < 9) == false```
`template anyIt(s, pred: untyped): bool`

Checks if some item fulfills the predicate.

Example:

```let numbers = @[1, 4, 5, 8, 9, 7, 4]
assert anyIt(numbers, it > 8) == true
assert anyIt(numbers, it > 9) == false```
`template toSeq(iter: untyped): untyped`

Transforms any iterator into a sequence.

Example:

```let
numeric = @[1, 2, 3, 4, 5, 6, 7, 8, 9]
odd_numbers = toSeq(filter(numeric) do (x: int) -> bool:
if x mod 2 == 1:
result = true)
assert odd_numbers == @[1, 3, 5, 7, 9]```
`template foldl(sequence, operation: untyped): untyped`

Template to fold a sequence from left to right, returning the accumulation.

The sequence is required to have at least a single element. Debug versions of your program will assert in this situation but release versions will happily go ahead. If the sequence has a single element it will be returned without applying `operation`.

The `operation` parameter should be an expression which uses the variables `a` and `b` for each step of the fold. Since this is a left fold, for non associative binary operations like subtraction think that the sequence of numbers 1, 2 and 3 will be parenthesized as (((1) - 2) - 3).

Example:

```let
numbers = @[5, 9, 11]
addition = foldl(numbers, a + b)
subtraction = foldl(numbers, a - b)
multiplication = foldl(numbers, a * b)
words = @["nim", "is", "cool"]
concatenation = foldl(words, a & b)
assert subtraction == -15, "Subtraction is (((5)-9)-11)"
assert multiplication == 495, "Multiplication is (((5)*9)*11)"
assert concatenation == "nimiscool"```
`template foldl(sequence, operation, first): untyped`

Template to fold a sequence from left to right, returning the accumulation.

This version of `foldl` gets a starting parameter. This makes it possible to accumulate the sequence into a different type than the sequence elements.

The `operation` parameter should be an expression which uses the variables `a` and `b` for each step of the fold. The `first` parameter is the start value (the first `a`) and therefor defines the type of the result.

Example:

```let
numbers = @[0, 8, 1, 5]
digits = foldl(numbers, a & (chr(b + ord('0'))), "")
assert digits == "0815"```
`template foldr(sequence, operation: untyped): untyped`

Template to fold a sequence from right to left, returning the accumulation.

The sequence is required to have at least a single element. Debug versions of your program will assert in this situation but release versions will happily go ahead. If the sequence has a single element it will be returned without applying `operation`.

The `operation` parameter should be an expression which uses the variables `a` and `b` for each step of the fold. Since this is a right fold, for non associative binary operations like subtraction think that the sequence of numbers 1, 2 and 3 will be parenthesized as (1 - (2 - (3))).

Example:

```let
numbers = @[5, 9, 11]
addition = foldr(numbers, a + b)
subtraction = foldr(numbers, a - b)
multiplication = foldr(numbers, a * b)
words = @["nim", "is", "cool"]
concatenation = foldr(words, a & b)
assert subtraction == 7, "Subtraction is (5-(9-(11)))"
assert multiplication == 495, "Multiplication is (5*(9*(11)))"
assert concatenation == "nimiscool"```
`template mapIt(s, typ, op: untyped): untyped`

Convenience template around the `map` proc to reduce typing.

The template injects the `it` variable which you can use directly in an expression. You also need to pass as typ the type of the expression, since the new returned sequence can have a different type than the original.

Example:

```let
nums = @[1, 2, 3, 4]
strings = nums.mapIt(string, \$(4 * it))
assert strings == @["4", "8", "12", "16"]```
Deprecated since version 0.12.0: Use the `mapIt(seq1, op)`
`template mapIt(s: typed; op: untyped): untyped`

Convenience template around the `map` proc to reduce typing.

The template injects the `it` variable which you can use directly in an expression.

Example:

```let
nums = @[1, 2, 3, 4]
strings = nums.mapIt(\$(4 * it))
assert strings == @["4", "8", "12", "16"]```
`template applyIt(varSeq, op: untyped)`

Convenience template around the mutable `apply` proc to reduce typing.

The template injects the `it` variable which you can use directly in an expression. The expression has to return the same type as the sequence you are mutating.

Example:

```var nums = @[1, 2, 3, 4]
nums.applyIt(it * 3)
assert nums + nums == 15```
`template newSeqWith(len: int; init: untyped): untyped`

creates a new sequence, calling init to initialize each value.

Example:

```var seq2D = newSeqWith(20, newSeq[bool](10))
seq2D = true
seq2D = true
seq2D = true

import random
var seqRand = newSeqWith(20, random(10))
echo seqRand```