Nanyx
PlaygroundPackages

prelude: sequences

Lazy sequences, and ranges

seq(a) is a lazy sequence: a function that, when pulled, gives back its first element and the rest of the sequence, or #done. Nothing is worked out until it is pulled, and pulling it changes nothing, so a sequence can be passed around, stored and pulled again. Ranges are sequences: 1..10 is a seq(int), and 0.. is one that never ends. The functions here are attached definitions on seq, so s \map(f) resolves to seq.map when s is a sequence, and are in the prelude, so no import is needed.

A function that gives back a sequence, such as seq.map, runs its callback when the sequence is pulled, not when it is called, so the sequence carries the callback’s contexts: mapping with a function that prints gives a [Console] seq(b), which can be pulled only where Console is (see Lazy sequences). A function that pulls the whole sequence now, such as seq.toList, needs them where it is called.

println((1..10) \seq.map { * 2 } \seq.toList)
println(0.. \seq.filter { x -> x % 3 == 0 } \seq.take(4) \seq.toList)
println((1..4) \seq.fold(0) { + })
-- [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
-- [0, 3, 6, 9]
-- 10

seq has list’s functions, with list’s names, argument order and results, where a sequence can give them: the ones that give back a sequence are lazy, the ones that find something, such as seq.find, seq.any and seq.head, stop pulling as soon as they have their answer, so they work on an endless sequence that has one, and the ones that read every element, such as seq.length, seq.max and seq.partition, never return on an endless sequence. Each function’s comment says which it is. reverse, the sort family, foldBack and dropLast are left out on purpose: each would have to read and keep the whole sequence before giving anything, which is a list’s job, so write xs \seq.toList \list.sort.

Reference

Seq

type Seq(a) = [k] protected (next: ([k] () -> #next(a, seq(a)) | #done))

A lazy sequence of as: a function that, when called, gives back the first element and the rest of the sequence, #next(x, rest), or #done. Calling it changes nothing, so a sequence can be pulled again, and does its work again. A sequence whose steps need contexts says so in its type, [Console] seq(int), and the rest of it needs them too. Ranges are sequences: 1..10 is seq.range(1, 10) and 0.. is seq.from(0).

seq.empty

def seq.empty: () -> seq(a)

The sequence of no elements.

seq.delay

def seq.delay: ([c] () -> [d] seq(a)) -> [c, d] seq(a)

The sequence f gives, worked out when it is pulled, not now: f runs each time the sequence is pulled.

seq.cons

def seq.cons: a, ([c] () -> [d] seq(a)) -> [c, d] seq(a)

x, then the elements of the sequence rest gives, which runs only when the sequence is pulled past x.

seq

def seq: ([c] () -> [d] seq(a)) -> [c, d] seq(a)

The sequence block gives, worked out when it is pulled. A block with yield in it is a sequence: seq { yield 1 yield 2 } gives 1 and 2, and the code after a yield runs only when the sequence is pulled that far.

Enumerable

context Enumerable(a) = (
  succ: a -> a
)

The values that come one after another, so that a range of them can be counted through: succ gives the value after x. A range, first..last, takes the values from first up to last in steps of succ, and stops by their Ord. A type gets it by attaching succ, as int does.

int.succ

def int.succ: int -> int

The value after n: n + 1. int’s Enumerable, which counts a range of ints.

seq.range

def seq.range: [Enumerable(a), Ord(a)] a, a -> seq(a)

The values from first up to last, both included, each the succ of the one before: 1..10. Empty when last is less than first.

seq.from

def seq.from: [Enumerable(a)] a -> seq(a)

The values from first up, each the succ of the one before, without end: 0...

seq.unfold

def seq.unfold: b, ([c] b -> #some(a, b) | #done) -> [c] seq(a)

The elements step gives, starting from state: #some(x, next) gives x and carries on from next, and #done ends the sequence. step runs when the sequence is pulled.

Iterable

context Iterable(c) = (
  elem: type
  toSeq: c -> seq(elem)
)

What can be iterated: a value of type c that gives a sequence of elems. A for loop walks anything Iterable, and the seq functions that read a sequence take one. A type gets it by attaching toSeq, whose type fixes elem: list.toSeq: list(a) -> seq(a) makes the elem of a list(int) an int. A signature that needs the element type fixes it by name, [Iterable(c, elem = string)]. The sequence toSeq gives needs no contexts.

seq.toSeq

def seq.toSeq: seq(a) -> seq(a)

s itself: a sequence is Iterable.

list.toSeq

def list.toSeq: list(a) -> seq(a)

The elements of xs, in order.

seq.fromList

def seq.fromList: list(a) -> seq(a)

The elements of xs, in order: seq.fromList([1, 2, 3]) \seq.toList is [1, 2, 3]. The same as list.toSeq.

seq.fromArray

def seq.fromArray: array(a) -> seq(a)

The elements of xs, in order, each read when the sequence is pulled. What a literal builds a sequence with, Seq[1, 2, 3]. The same as array.toSeq.

seq.map

def seq.map: ([c] seq(a)), ([d] a -> b) -> [c, d] seq(b)

f applied to each element of s, when it is pulled: (1..3) \seq.map { * 2 } gives 2, 4 and 6.

seq.zip

def seq.zip: ([c] seq(a)), ([d] seq(b)) -> [c, d] seq((a, b))

Pairs the elements of s and t in order, ending when either ends, as list.zip stops at the shorter list: seq.zip(0.., list.toSeq(["a", "b"])) gives (0, "a") and (1, "b"). Each pair pulls one element from each side, and nothing more.

seq.append

def seq.append: ([c] seq(a)), ([d] seq(a)) -> [c, d] seq(a)

The elements of s, then those of t.

seq.flatMap

def seq.flatMap: ([c] seq(a)), ([d] a -> [d] seq(b)) -> [c, d] seq(b)

The elements of the sequences f gives for each element of s, one after another, when it is pulled: (1..3) \seq.flatMap { n -> seq.range(1, n) } gives 1, 1, 2, 1, 2 and 3. Lazy: f runs on an element only when the sequence is pulled that far.

seq.flatten

def seq.flatten: ([c] seq(seq(a))) -> [c] seq(a)

The elements of each sequence of s, one after another: [[1, 2], [3]] \list.map(list.toSeq) \list.toSeq \seq.flatten gives 1, 2 and 3. Lazy: it pulls s one sequence at a time.

seq.select

def seq.select: ([c] seq(a)), ([d] a -> [d] seq(b)) -> [c, d] seq(b)

The values f yields for each element in turn, in the order it yields them, as list.select gives them for a list: seq.flatMap for a lambda with yield in it. Lazy: the code after a yield runs only when the sequence is pulled that far.

seq.filterMap

def seq.filterMap: ([c] seq(a)), ([d] a -> #some(b) | #skip) -> [c, d] seq(b)

The payload of each #some that f gives for the elements of s, skipping each #skip: (1..6) \seq.filterMap { n -> if n % 2 == 0 then #some(n * 10) else #skip } gives 20, 40 and 60. Lazy: pulling it pulls s until f gives a #some, in constant stack.

seq.mapIndexed

def seq.mapIndexed: ([c] seq(a)), ([d] (int, a) -> b) -> [c, d] seq(b)

f applied to the position of each element of s, counting from 0, and the element: ["a", "b"] \list.toSeq \seq.mapIndexed { i, x -> "{i}{x}" } gives "0a" and "1b". Lazy.

seq.skipWhile

def seq.skipWhile: ([c] seq(a)), ([d] a -> bool) -> [c, d] seq(a)

s from the first element for which predicate is false: (1..5) \seq.skipWhile { < 3 } gives 3, 4 and 5. Lazy: the elements it skips are pulled when the sequence is first pulled.

seq.scan

def seq.scan: ([c] seq(a)), b, ([d] (b, a) -> b) -> [c, d] seq(b)

The running totals of a fold: initial, then each value seq.fold passes along: (1..3) \seq.scan(0) { + } gives 0, 1, 3 and 6. Lazy: each total is worked out when it is pulled, so it works on an endless sequence.

seq.zipWith

def seq.zipWith: ([c] seq(a)), ([d] seq(b)), ([e] (a, b) -> f) -> [c, d, e] seq(f)

f applied to the elements of s and t in pairs, ending when either ends, as seq.zip does: seq.zipWith(1.., 10..12, { + }) gives 11, 13 and 15. Lazy.

seq.intersperse

def seq.intersperse: ([c] seq(a)), a -> [c] seq(a)

s with separator between each pair of neighbouring elements: (1..3) \seq.intersperse(0) gives 1, 0, 2, 0 and 3. Lazy.

seq.chunks

def seq.chunks: ([c] seq(a)), int -> [c] seq(list(a))

s cut into lists of size elements, in order; the last is shorter when the sequence ends part way through one: (1..5) \seq.chunks(2) gives [1, 2], [3, 4] and [5]. Lazy: each list is pulled when it is. A size below 1 crashes.

seq.windows

def seq.windows: ([c] seq(a)), int -> [c] seq(list(a))

Every run of size neighbouring elements, in order: (1..4) \seq.windows(2) gives [1, 2], [2, 3] and [3, 4], and a sequence shorter than size has none. Lazy: each window pulls one more element. A size below 1 crashes.

seq.distinct

def seq.distinct: [Eq(a)] seq(a) -> seq(a)

The elements of s without repeats, each where it first appears, compared with ==. Lazy, but it remembers each element it has given, so its memory grows with the distinct elements, and finding the next one compares with each of them.

seq.distinctBy

def seq.distinctBy: [Eq(b), Hash(b)] seq(a), (a -> b) -> seq(a)

The elements of s without two of the same key, each where the first with its key appears. Lazy, but it remembers each key it has seen, so its memory grows with the distinct keys.

seq.init

def seq.init: int, ([c] int -> a) -> [c] seq(a)

The sequence of count elements whose element at each position is f applied to the position: seq.init(3, { i -> i * 2 }) gives 0, 2 and 4. Lazy: f runs on a position when the sequence is pulled that far. A count of zero or less gives no elements.

seq.replicate

def seq.replicate: (a, count: int) -> seq(a)

count copies of x: seq.replicate(0, count = 3) gives 0, 0 and 0. A count of zero or less gives none.

seq.unzip

def seq.unzip: [c] ([c] seq((a, b))) -> ([c] seq(a), ([c] seq(b)))

The first parts of the pairs of pairs and their second parts, each a sequence: the inverse of seq.zip. Each side pulls pairs on its own, so a sequence whose steps have effects runs them once for each side pulled.

seq.filter

def seq.filter: ([c] seq(a)), ([d] a -> bool) -> [c, d] seq(a)

The elements of s for which predicate is true. Pulling it pulls s until one is, in constant stack.

seq.take

def seq.take: ([c] seq(a)), int -> [c] seq(a)

The first count elements of s, or all of them if it has fewer. It pulls no more of s than that, so it ends an endless sequence: (0..) \seq.take(3) is 0, 1 and 2.

seq.skip

def seq.skip: ([c] seq(a)), int -> [c] seq(a)

s without its first count elements, which are pulled and thrown away when it is pulled.

seq.takeWhile

def seq.takeWhile: ([c] seq(a)), ([d] a -> bool) -> [c, d] seq(a)

The elements of s up to the first for which predicate is false.

seq.fold

def seq.fold: [c, d] ([c] seq(a)), b, ([d] (b, a) -> b) -> b

step applied to initial and the first element, then to that result and the second, and so on, pulling the whole of s now. Stack-safe, but an endless sequence never ends.

seq.reduce

def seq.reduce: [c, d] ([c] seq(a)), ([d] (a, a) -> a) -> #some(a) | #none

The elements of s, pulled now, combined with f, in order, starting from the first: (1..5) \seq.reduce { * } is #some(120), and an empty sequence, having no first element, gives #none. To start from another value, use seq.fold.

seq.toList

def seq.toList: [c] ([c] seq(a)) -> list(a)

The elements of s, pulled now, as a list: (1..3) \seq.toList is [1, 2, 3]. Stack-safe, but an endless sequence never ends.

list.fromSeq

def list.fromSeq: [c] ([c] seq(a)) -> list(a)

The elements of s, pulled now, as a list: (1..3) \list.fromSeq is [1, 2, 3]. It requires the contexts the sequence’s steps do. An endless sequence never ends: cut it with seq.take.

list.build

def list.build: [c, d] ([c] () -> [d] seq(a)) -> list(a)

The list of what block yields: list.build { yield 1 if more then yield 2 }. The same as seq(block) \list.fromSeq.

seq.find

def seq.find: [c, d] ([c] seq(a)), ([d] a -> bool) -> #some(a) | #notFound

The first element of s for which matches is true, or #notFound: `(1..) \seq.find { n -> n * n

50 }is#some(8). It pulls s` up to that element.

seq.findIndex

def seq.findIndex: [c, d] ([c] seq(a)), ([d] a -> bool) -> #some(int) | #notFound

The position, counting from 0, of the first element of s for which matches is true, or #notFound. It pulls s up to that element.

seq.indexOf

def seq.indexOf: [Eq(a), c] ([c] seq(a)), a -> #some(int) | #notFound

The position, counting from 0, of the first element of s that is == x, or #notFound. It pulls s up to that element.

seq.contains

def seq.contains: [Eq(a), c] ([c] seq(a)), a -> bool

Whether s has an element == x. It pulls s until it finds one.

seq.any

def seq.any: [c, d] ([c] seq(a)), ([d] a -> bool) -> bool

Whether test holds for any element of s (so false for an empty one). It pulls s until it holds.

seq.all

def seq.all: [c, d] ([c] seq(a)), ([d] a -> bool) -> bool

Whether test holds for every element of s (so true for an empty one). It pulls s until it doesn’t.

seq.head

def seq.head: [c] ([c] seq(a)) -> #some(a) | #emptyList

The first element of s, or #emptyList when it has none, as list.head says. It pulls one element.

seq.at

def seq.at: [c] ([c] seq(a)), int -> #some(a) | #notFound

The element of s at index, counting from 0, or #notFound when index is negative or s ends before it. It pulls s up to that element.

seq.isEmpty

def seq.isEmpty: [c] ([c] seq(a)) -> bool

Whether s has no elements. It pulls one element.

seq.selectOne

def seq.selectOne: [c, d] ([c] seq(a)), ([d] a -> [d] seq(b)) -> #some(b) | #notFound

The first value f yields, running it on the elements in turn as seq.select does, or #notFound when it yields none. It stops at the first yield.

seq.count

def seq.count: [c, d] ([c] seq(a)), ([d] a -> bool) -> int

How many elements of s test holds for. It pulls the whole of s.

seq.length

def seq.length: [c] ([c] seq(a)) -> int

How many elements s has. It pulls the whole of s.

seq.last

def seq.last: [c] ([c] seq(a)) -> #some(a) | #emptyList

The last element of s, or #emptyList when it has none. It pulls the whole of s.

seq.max

def seq.max: [Ord(a), c] ([c] seq(a)) -> #some(a) | #emptyList

The largest element of s, or #emptyList when it has none; of equal ones, the first. It pulls the whole of s.

seq.min

def seq.min: [Ord(a), c] ([c] seq(a)) -> #some(a) | #emptyList

The smallest element of s, or #emptyList when it has none; of equal ones, the first. It pulls the whole of s.

seq.maxBy

def seq.maxBy: [Ord(b), c, d] ([c] seq(a)), ([d] a -> b) -> #some(a) | #emptyList

The element of s whose key is largest, or #emptyList when it has none; of equal keys, the first. It pulls the whole of s.

seq.minBy

def seq.minBy: [Ord(b), c, d] ([c] seq(a)), ([d] a -> b) -> #some(a) | #emptyList

The element of s whose key is smallest, or #emptyList when it has none; of equal keys, the first. It pulls the whole of s.

seq.sum

def seq.sum: [Add(a), c] ([c] seq(a)) -> a

The elements of s added up, from the element type’s zero: (1..4) \seq.sum is 10. It pulls the whole of s.

seq.partition

def seq.partition: [c, d] ([c] seq(a)), ([d] a -> bool) -> (list(a), list(a))

The elements of s for which test holds, and those for which it doesn’t, each a list in order. It pulls the whole of s.