std.oak
// libstd is the core standard library for Oak.
//
// It defines basic functions for working with Oak values and functions,
// iterators, and control flow.
// identity returns its first argument
fn identity(x) x
// is returns a predicate that reports whether its argument is equal to x
fn is(x) fn(y) x = y
// constantly returns a function that always returns x
fn constantly(x) fn() x
// _baseIterator is a helper function that returns the "base iterator" of a
// type, or the "zero value" version of the type.
fn _baseIterator(v) if type(v) {
:string -> ''
:list -> []
:object -> {}
}
// _asPredicate takes a predicate argument pred (a common interface across
// iterator-related functions here) and returns a predicate function.
//
// if a string, atom, or int is given rather than a function, the predicate
// function will return the property of the given object by that given label.
fn _asPredicate(pred) if type(pred) {
:atom -> {
prop := string(pred)
fn(x) x.(prop)
}
:string, :int -> fn(x) x.(pred)
_ -> pred
}
// default returns x if x is not null, or base otherwise. It is useful when
// taking optional arguments in functions with default values. For example, we
// can write
//
// fn repeat(n, times) {
// // times = 2 by default
// times := default(times, 2)
// }
fn default(x, base) if x {
? -> base
_ -> x
}
_nToH := '0123456789abcdef'
// toHex takes a number and returns its hexadecimal representation in a string.
// It fails for negative values of N.
fn toHex(n) {
fn sub(p, acc) if p < 16 {
true -> _nToH.(p) + acc
_ -> int(p / 16) |> sub(_nToH.(p % 16) + acc)
}
sub(int(n), '')
}
_hToN := {
0: 0
1: 1
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9
a: 10, A: 10
b: 11, B: 11
c: 12, C: 12
d: 13, D: 13
e: 14, E: 14
f: 15, F: 15
}
// fromHex takes a hexadecimal representation of a number and parses it out to
// an integer. It returns ? if the input is not a valid hexadecimal number.
fn fromHex(s) {
fn sub(i, acc) if {
i = len(s) -> acc
? != next := _hToN.(s.(i)) -> sub(i + 1, acc * 16 + next)
}
sub(0, 0)
}
// clamp takes values n, m and "clamps" or constrains it to the range [min,
// max], inclusive. If n > m, n takes priority and clams m down to the lower
// value. In the returned value, the following are guaranteed:
//
// - min <= n <= max
// - min <= m <= max
// - n <= m
fn clamp(min, max, n, m) {
// assumes that at least min < max & n < m
n := if n < min {
true -> min
_ -> n
}
m := if m < min {
true -> min
_ -> m
}
m := if m > max {
true -> max
_ -> m
}
n := if n > m {
true -> m
_ -> n
}
[n, m]
}
// slice takes an iterable xs (string or list), and returns a "slice" of the
// original from the range [min, max). The slice is a copy, and mutating it
// will not mutate the original.
//
// Both min and max are optional, and will default to 0 and len(xs)
// respectively.
fn slice(xs, min, max) {
min := default(min, 0)
max := default(max, len(xs))
[min, max] := clamp(0, len(xs), min, max)
fn sub(acc, i) if i {
max -> acc
_ -> sub(
acc << xs.(i)
i + 1
)
}
sub(_baseIterator(xs), min)
}
// clone takes any Oak value and produces a shallow clone of it that will not
// mutate if the original mutates.
fn clone(x) if type(x) {
:string -> '' + x
:list -> slice(x)
:object -> keys(x) |> reduce({}, fn(acc, key) acc.(key) := x.(key))
_ -> x
}
// functional iterators
// range returns a list of numbers in range [start, end), incrementing by step.
// It is analogous to Python's range builtin, and will default to step = 0 and
// start = 0 when those optional values are missing.
fn range(start, end, step) {
step := default(step, 1)
if end = ? -> [start, end] <- [0, start]
if step {
0 -> []
_ -> {
list := []
if step > 0 {
true -> fn sub(n) if n < end {
true -> {
list << n
sub(n + step)
}
_ -> list
}
_ -> fn sub(n) if n > end {
true -> {
list << n
sub(n + step)
}
_ -> list
}
}
sub(start)
}
}
}
// reverse reverses the order of all elements in a given iterable, producing a
// copy.
fn reverse(xs) {
fn sub(acc, i) if i < 0 {
true -> acc
_ -> sub(
acc << xs.(i)
i - 1
)
}
sub(_baseIterator(xs), len(xs) - 1)
}
// map produces a copy of the given iterable where each element has been put
// through some mapper predicate f. If f is a function, it receives arguments
// (element, index).
fn map(xs, f) {
f := _asPredicate(f)
fn sub(acc, i) if i {
len(xs) -> acc
_ -> sub(
acc << f(xs.(i), i)
i + 1
)
}
sub(_baseIterator(xs), 0)
}
// each calls the given iterator function f for each element of the given
// iterable xs. The iterator function receives arguments (element, index).
fn each(xs, f) {
fn sub(i) if i {
len(xs) -> ?
_ -> {
f(xs.(i), i)
sub(i + 1)
}
}
sub(0)
}
// filter produces an iterable containing only the elements of xs that return
// true when passed to the filter predicate f. If f is a function, it receives
// arguments (element, index).
fn filter(xs, f) {
f := _asPredicate(f)
fn sub(acc, i) if i {
len(xs) -> acc
_ -> {
if f(x := xs.(i), i) -> acc << x
sub(acc, i + 1)
}
}
sub(_baseIterator(xs), 0)
}
// exclude produces an iterable containing only the elements of xs that return
// false when passed to the exclude predicate f. If f is a function, it
// receives arguments (element, index).
fn exclude(xs, f) {
f := _asPredicate(f)
fn sub(acc, i) if i {
len(xs) -> acc
_ -> {
if !f(x := xs.(i), i) -> acc << x
sub(acc, i + 1)
}
}
sub(_baseIterator(xs), 0)
}
// separate produces a pair of two iterables [is, isnt], where is contains the
// result of filter(xs, f) and isnt contains the result of exclude(xs, f).
fn separate(xs, f) {
f := _asPredicate(f)
fn sub(is, isnt, i) if i {
len(xs) -> [is, isnt]
_ -> {
if f(x := xs.(i), i) {
true -> is << x
_ -> isnt << x
}
sub(is, isnt, i + 1)
}
}
sub(_baseIterator(xs), _baseIterator(xs), 0)
}
// reduce accumulates elements of the iterable xs on a value, starting with
// seed and passing it to the reducer function f. The reducer receives
// arguments (accumulator, element, index).
//
// For example, a "sum" function may be implemented:
//
// numbers |> with reduce(0) fn(accumulator, elem) accumulator + elem
fn reduce(xs, seed, f) {
fn sub(acc, i) if i {
len(xs) -> acc
_ -> sub(
f(acc, xs.(i), i)
i + 1
)
}
sub(seed, 0)
}
// flatten takes a list of lists and flattens it to a list of elements. The
// flattening is only 1 level deep.
fn flatten(xs) xs |> reduce([], append)
// compact returns a copy of the given list with all of its null elements
// filtered out.
fn compact(xs) xs |> filter(fn(x) x != ?)
// some checks whether at least one item in the given iterable is true, or is
// true by some predicate pred.
fn some(xs, pred) {
pred := default(pred, identity)
xs |> reduce(false, fn(acc, x, i) acc | pred(x, i))
}
// every checks whether every item in the given iterable is true, or is true by
// some predicate pred.
fn every(xs, pred) {
pred := default(pred, identity)
xs |> reduce(true, fn(acc, x, i) acc & pred(x, i))
}
// append joins two iterable values (strings or lists) together, mutating the
// first argument. If mutation is not desired, use std.join.
fn append(xs, ys) ys |> with reduce(xs) fn(zs, y) zs << y
// join joins two iterable values (strings or lists) together, while mutating
// neither values. If efficiency is desired, use std.append.
fn join(xs, ys) clone(xs) |> append(ys)
// zip "zips" together each pair of items from two iterables. If the zipper
// function is not given, each pair of items are put into a 2-element list.
// Otherwise, zipper is called on each pair of items and the result is placed
// into the resulting list.
//
// Illustrative examples:
//
// zip([1, 2, 3], [4, 5, 6])
// // => [[1, 2], [3, 4], [5, 6]]
// with zip([1, 2, 3], [4, 5, 6]) fn(a, b) a * b
// // => [4, 10, 18]
fn zip(xs, ys, zipper) {
zipper := default(zipper, fn(x, y) [x, y])
max := if len(xs) < len(ys) {
true -> len(xs)
_ -> len(ys)
}
fn sub(acc, i) if i {
max -> acc
_ -> sub(
acc << zipper(xs.(i), ys.(i), i)
i + 1
)
}
sub([], 0)
}
// partition divides the sequence of items in the iterable xs into a list of
// lists (partitions). If `by` is an integer, each partition will contain that
// number of items. If `by` is a function, the partition will be cut anywhere
// the result of the function changes from one item to the next. For any other
// values of `by`, partition returns null.
fn partition(xs, by) if type(by) {
:int -> xs |> reduce([], fn(acc, x, i) if i % by {
0 -> acc << [x]
_ -> {
acc.(len(acc) - 1) << x
acc
}
})
:function -> {
last := fn {} // a clever trick ;) -- fn {} is not equal to anything but itself
xs |> reduce([], fn(acc, x) {
if this := by(x) {
last -> acc.(len(acc) - 1) << x
_ -> acc << [x]
}
last <- this
acc
})
}
}
// uniq takes a list `xs`, and returns a similar list where no element of `xs`
// occurs twice in a row. Elements may occur twice in the list if they are
// separated by other elements. uniq takes an optional `pred` predicate, by
// which elements' equality may be compared. uniq runs in O(n) time.
//
// To ensure that no element occurs more than once in the whole list, first
// sort the list.
fn uniq(xs, pred) {
pred := default(pred, identity)
ys := _baseIterator(xs)
last := fn {} // empty fn is not equal to anything else
fn sub(i) if i {
len(xs) -> ys
_ -> if p := pred(x := xs.(i)) {
last -> sub(i + 1)
_ -> {
ys << x
last <- p
sub(i + 1)
}
}
}
sub(0)
}
// first returns the first item in an iterable. It's trivial, but useful to
// have in the stdlib for use in pipelines or iterators.
fn first(xs) xs.0
// last returns the last item in an iterable. It's trivial, but useful to have
// in the stdlib for use in pipelines or iterators.
fn last(xs) xs.(len(xs) - 1)
// take accepts an iterable and returns a version of it containing the first N
// elements.
fn take(xs, n) xs |> slice(0, n)
// takeLast accepts an iterable and returns a version of it containing the last
// N elements.
fn takeLast(xs, n) xs |> slice(len(xs) - n)
// find returns the index of the first item in the iterable xs for which the
// predicate returns true. If no match is found, find returns -1.
fn find(xs, pred) {
fn sub(i) if i {
len(xs) -> -1
_ -> if pred(xs.(i)) {
true -> i
_ -> sub(i + 1)
}
}
sub(0)
}
// rfind returns the index of the last item in the iterable xs for which the
// predicate returns true, searching backwards from the end. If no match is
// found, rfind returns -1.
fn rfind(xs, pred) {
fn sub(i) if i {
-1 -> -1
_ -> if pred(xs.(i)) {
true -> i
_ -> sub(i - 1)
}
}
sub(len(xs) - 1)
}
// indexOf returns the index of the first item equal to x in the iterable xs.
// If no match is found, indexOf returns -1.
fn indexOf(xs, x) {
fn sub(i) if i {
len(xs) -> -1
_ -> if xs.(i) {
x -> i
_ -> sub(i + 1)
}
}
sub(0)
}
// rindexOf returns the index of the last item equal to x in the iterable xs,
// searching backwards from the end. If no match is found, rindexOf returns -1.
fn rindexOf(xs, x) {
fn sub(i) if i {
-1 -> -1
_ -> if xs.(i) {
x -> i
_ -> sub(i - 1)
}
}
sub(len(xs) - 1)
}
// contains? reports whether an iterable contains an item equal to x.
fn contains?(xs, x) indexOf(xs, x) > -1
// values takes an object and returns a list of its values in arbitrary order.
fn values(obj) keys(obj) |> with map() fn(key) obj.(key)
// entries takes an object and returns a list of pairs [key, value] in arbitrary order.
fn entries(obj) keys(obj) |> with map() fn(key) [key, obj.(key)]
// fromEntries takes an object entry list (of the shape that entries() returns)
// and assembles it into an object.
fn fromEntries(entries) entries |>
with reduce({}) fn(o, entry) o.(entry.0) := entry.1
// merge takes a list of objects and merges entries of all subsequent objects
// onto the first object, mutating the first object. If there are no objects
// given, merge returns ?.
fn merge(os...) if len(os) {
0 -> ?
_ -> with reduce(os, os.0) fn(acc, o) {
with reduce(keys(o), acc) fn(root, k) root.(k) := o.(k)
}
}
// once takes a function f, and returns a new function g that wraps f so that
// calling g one or more times ensures f gets called exactly once, the first
// time g is called. once is useful for ensuring that some callback or
// initialization logic runs exactly once.
fn once(f) {
called? := false
fn(args...) if !called? -> {
called? <- true
f(args...)
}
}
// loop takes a loop count `max` and a callback, and invokes the callback `max`
// times. It can be used to infinitely loop if max < 0. Callback is called with
// two arguments:
// - count, the current loop count starting from 0
// - breaker, a fn to be called to exit early from the loop, which takes an
// optional return value to be returned by the loop() call
fn loop(max, f) {
// allow passing just a callback with no loop count, implying an infinite
// loop with max = -1
if type(max) = :function -> [max, f] <- [-1, max]
max := default(max, -1)
ret := ?
broken := false
fn breaker(x) {
ret <- x
broken <- true
}
fn sub(count) if count != max -> if {
broken -> ret
_ -> {
f(count, breaker)
sub(count + 1)
}
}
sub(0)
}
// aloop takes a loop count `max` and a callback, and invokes the callback
// `max` times asynchronously. It can be used to infinitely loop if max < 0.
// Callback is called with three arguments:
// - count, the current loop count starting from 0
// - next, a fn to be called when the current iteration is done
// - done, a fn to be called to exit early from the loop
fn aloop(max, f, done) {
// allow passing just the callbacks with no loop count, implying an infinite
// loop with max = -1
if type(max) = :function -> [max, f, done] <- [-1, max, f]
max := default(max, -1)
done := done |> default(fn {})
fn sub(count) if count {
max -> done()
_ -> f(count, fn() sub(count + 1), done)
}
sub(0)
}
// serial enables asynchronous iteration over xs such that only one item is
// processed at once. This is the asynchronous version of each. The predicate f
// is invoked with four arguments:
// - x, the item being iterated over
// - i, the index of x in xs
// - next, a fn to be called when the current iteration is done
// - done, a fn to be called to exit early from the loop
fn serial(xs, f, done) {
done := done |> default(fn {})
fn sub(i) if i {
len(xs) -> done()
_ -> f(xs.(i), i, fn() sub(i + 1), done)
}
sub(0)
}
// parallel enables asynchronous iteration over xs such that all items are
// processed at once, and the callback is invoked when the last item to finish
// has processed. The predicate f is invoked with four arguments:
// - x, the item being iterated over
// - i, the index of x in xs
// - next, a fn to be called when the current iteration is done
// - done, a fn to be called to exit early from the loop. Calling this will
// effectively make parallel behave as if all iterations are "racing" to a
// first result
fn parallel(xs, f, done) {
done := done |> default(fn {})
count := 0
broken? := false
xs |> with each() fn(x, i) {
with f(x, i, fn if !broken? -> {
count <- count + 1
if count = len(xs) -> done()
}) fn {
broken? <- true
done()
}
}
}
// debounce takes a function f, and returns a new function g that wraps f so
// that calling g one or more times within some given duration is guaranteed to
// only call f once per duration, with the most final arguments passed to it.
//
// if firstCall = :leading, the first call of g after a quiet period will also
// call f. If firstCall = :trailing, this "leading edge call" will be a no-op,
// but the following debounced calls will occur as normal. firstCall is
// :leading by default, and may be omitted.
fn debounce(duration, firstCall, f) {
if f = ? -> [firstCall, f] <- [:trailing, firstCall]
dargs := ? // debounced args, should never be used uninitialized to [...]
waiting? := false
target := time() - duration
fn debounced(args...) {
// to ensure that the duration is honored as closely to real wall time
// as possible, we measure time() at this point in execution and re-use
// it later to set timers.
tcall := time()
dargs <- args
if !waiting? -> if target <= tcall {
// leading edge call
true -> {
target <- tcall + duration
if firstCall {
:leading -> f(dargs...)
:trailing -> {
waiting? <- true
with wait(target - time()) fn {
waiting? <- false
f(dargs...)
}
}
}
}
// trailing debounced call
_ -> {
waiting? <- true
timeout := target - tcall
target <- target + duration
with wait(timeout) fn {
waiting? <- false
f(dargs...)
}
}
}
}
}
// OS interfaces
// stdin reads and returns all data from standard input. It attempts to read
// standard input with input() continuously until an EOF is encountered.
fn stdin {
file := ''
with loop() fn(_, break) {
evt := input()
file << evt.data
if evt.type {
:error -> break(file)
_ -> file << '\n'
}
}
}
// println prints every value passed to it, in its default string
// representation, separated by a space.
//
// this implementation tries to use a single call to print() unnecessarily, in
// the hopes that in a browser environment, when writing output without a
// trailing '\n' is impossible, println will still behave as expected.
fn println(xs...) if len(xs) {
0 -> print('\n')
_ -> {
out := xs |> slice(1) |> with reduce(string(xs.0)) fn(acc, x) {
acc + ' ' + string(x)
}
print(out + '\n')
}
}