tup.singeli

# Tuple utilities

local {
  include 'skin/cop'
  oper $ length prefix 30

  include 'util/kind'
  def sl{l, start, len} = slice{l, start, start + len}
}

# Tuple is empty
def empty{tup} = 0 == $tup

# Constant-time evaluation returning a list
def collect{vars,begin,end,exec if begin<=end} = {
  def inds = begin + range{end-begin}
  each{exec{., vars}, inds}
}

# Integers [0,n)
def iota{n if knum{n}} = range{n}

# All indices into tuple t
def inds{t} = range{$t}

# Tuple of n copies of v
def copy{n, v if knum{n}} = each{{_}=>v, range{n}}

# Merge a tuple of tuples
def join{l} = merge{...l}

# Shift l into r, retaining length of r, or vice-versa
def shiftright{l, r} = slice{merge{l, r}, 0, $r}
def shiftleft {l, r} = slice{merge{l, r}, - $l}

# Reversed tuple
def reverse{t} = select{t, ($t-1) - inds{t}}

# Tuple of length n made from t repeated cyclically
def cycle{n, t if knum{n}} = {
  def l = $t
  def m = n % l; def e = slice{t, 0, m}
  if (m == n) e
  else merge{...copy{(n-m)/l, t}, e}
}

# Split into groups of length n, possibly less for the last
def split{n, list if knum{n}} = {
  def d = __ceil{($list) / n}
  each{sl{list, ., n}, n*range{d}}
}
def split{{...n}, list} = {
  def start = shiftright{0, scan{+,n}}
  each{sl{list,...}, start, n}
}

# Transpose tuple of same-length tuples
def flip{tab} = each{tup, ...tab}

# Function table mapping over all combinations
def table = match {
  {f}           => f{}
  {f, t}        => each{f, t}
  {f, t, ...ts} => each{{e} => table{f{e,...}, ...ts}, t}
}
# Flattened into a single list
def flat_table = match {
  {f}           => tup{f{}}
  {f, t}        => each{f, t}
  {f, t, ...ts} => join{each{{e} => flat_table{f{e,...}, ...ts}, t}}
}

# Left fold, with or without initial element
def fold = match {
  {f, init, {}} => init
  {f, init, {x, ...rest}} => fold{f, f{init, x}, rest}
  {f,    {init, ...rest}} => fold{f, init, rest}
}

# Low-stack inclusive+exclusive scan implementation
local def scan_full = match {
  {f, init, {}}  => tup{init}
  {f, init, {x}} => tup{init, f{init, x}}
  {f, init, list} => {
    def m = length{list} >> 1
    def l = scan_full{f, init, slice{list, 0, m}}
    merge{l, scan{f, select{l, -1}, slice{list, m}}}
  }
}
# Inclusive left scan
def scan{f, init, list} = slice{scan_full{f, init, list}, 1}
def scan{f, {}} = tup{}
def scan{f, {h, ...t}} = scan_full{f, h, t}

# Extend to multiple list inputs, if initialized
def fold{f, i, ...ls={_, _, ..._}} = fold{{a, t} => f{a, ...t}, i, flip{ls}}
def scan{f, i, ...ls={_, _, ..._}} = scan{{a, t} => f{a, ...t}, i, flip{ls}}

# Copy list elements based on list, constant, or generator (like filter)
def replicate{reps, list} = join{each{copy, reps, list}}
def replicate{r, list if knum{r}} = join{each{copy{r,.}, list}}
def replicate{f, list if kgen{f}} = replicate{each{f,list}, list}

# For boolean i, return indices of 1s
def indices{i} = replicate{i, inds{i}}

# Search functions that return a single number
local def proc_find{out, f, i} = each{out, findmatches{f, i}}
# Index of only match, erroring if there are multiple
# If there are none, return the default if given and error otherwise
def find_index{sfor, sin, ...default if $default <= 1} = proc_find{
  {is} => match (is, default) { {{i}, _} => i; {{}, {d}} => d },
  sfor, sin
}
# Index of first match
def index_of{sfor, sin} = {
  def n = $sfor
  proc_find{match { {{i, ..._}} => i; {_} => n }, sfor, sin}
}
# Whether each element is found; how many times it's found
def contained_in = proc_find{{i} => 0 < $i, ...}
def count_matches = proc_find{length, ...}

# Grouping: gather indices or data values based on how a grouping
# argument matches the domain
# For group, domain can be a list of keys, a length, or omitted to infer length
# For key, the domain is the unique elements of the grouping argument in order
# group_inds: gather inds{values}
def group_inds = findmatches
def group_inds{values, len if knum{len}} = findmatches{values, range{len}}
def group_inds{{...vs} if fold{&, each{knum, vs}}} = {
  group_inds{vs, 1 + fold{__max, vs}}
}
# group: gather data
def group{{...vs}, ...g, {...data} if $vs == $data} = {
  select{data, group_inds{vs, ...g}}
}
# key: gather indices or data
def key{{...keys}} = {
  def i = findmatches{keys, keys}
  replicate{inds{i} == each{select{., 0}, i}, i}
}
def key{{...keys}, {...values} if $keys == $values} = select{key{keys}, values}
# Add a generator for the first argument to apply to each result
def extend resgen{gr} = {
  def gr{gen, ...args if kgen{gen}} = each{gen, gr{...args}}
}
extend resgen{group_inds}; extend resgen{group}; extend resgen{key}

# Self-search
local def index_self{list} = proc_find{select{., 0}, list, list}
local def umask_from_ind{i} = i == inds{i}
local def cls_from_umask_ind{u, i} = select{scan{+, -1, u}, i}
def unique_mask{list} = umask_from_ind{index_self{list}}
def unique{list} = replicate{unique_mask{list}, list}
def classify{list} = {
  def i = index_self{list}
  cls_from_umask_ind{umask_from_ind{i}, i}
}
def unique_classify{list} = {
  def i = index_self{list}
  def u = umask_from_ind{i}
  tup{replicate{u, list}, cls_from_umask_ind{u, i}}
}
def occurrence_count{list} = {
  def g = key{list}
  def c = join{each{inds, g}}
  group{{{i}}=>i, join{g}, c}
}