::  /lib/seq/hoon
::    |seq
::    operations for working with values of type list
::  
|%
::    +all-pairs: [(list T1) (list T2)] -> (list [T1 T2])
::
::  Returns a new list that contains all pairings of elements from two non-empty
::  lists.
::    Examples
::      > (all-pairs ~['a' 'b' 'c'] ~[1 2 3])
::      ~[['c' 3] ['c' 2] ['c' 1] 
::        ['b' 3] ['b' 2] ['b' 1]
::        ['a' 3] ['a' 2] ['a' 1]]
::    Source
++  all-pairs
  |*  [p=(list) q=(list)]
  =/  a=(list _?>(?=(^ p) i.p))  p
  =/  res=(list [_?>(?=(^ p) i.p) _?>(?=(^ q) i.q)])  ~
  =/  scnd=(list _?>(?=(^ q) i.q))  q
  |-  ^-  (list [_?>(?=(^ p) i.p) _?>(?=(^ q) i.q)])
  ?~  a  res
  ?~  scnd  $(a t.a, scnd q)
  $(res [[i.a i.scnd] res], scnd +.scnd)
::    +append: [(list) (list)] -> (list)
::
::  Returns a new list that contains the elements of the first list followed by
::  elements of the second list.
::    Examples
::      > (append "urb" "it")
::      "urbit"
::      > (append (limo [1 2 ~]) (limo [3 4 ~]))
::      ~[1 2 3 4]
::    Source
++  append  weld
::    +average: (list @) -> @ud
::
::  Returns the average of the values in a non-empty list.
::    Examples
::      > (average `(list @ud)`~[1 2 3 4])
::      2
::    Source
++  average
  |*  a=(list @)
  (div (roll a add) (lent a))
::    +average-by: [(list T) projection:$-(T @ud)] -> @ud
::
::  Returns the average of values in a list generated by applying a function to
::  each element of the list.
::    Examples
::      > (average-by (limo ~[[1 1] [2 2] [3 3] [4 4]]) |=([a=@ b=@] (add a b)))
::      5
::    Source
++  average-by
  |*  [a=(list) b=$-(* @ud)]
  (div (roll (turn a b) add) (lent a))
::    +choose: [(list T1) $-(T1 (unit T2))] -> (list T2)
::
::  Applies a function to each element in a list and then returns a list of
::  values v where the applied function returns (unit v). 
::  Returns an empty list when the input list is empty or when the applied
::  chooser function returns ~ for all elements.
::    Examples
::      > =a |=(a=@ ?.((gte a 2) ~ (some (add a 10))))
::      > (choose `(list @)`[0 1 2 3 ~] a)
::      [i=12 t=[i=13 t=~]]
::    Source
++  choose  murn
::    +chunk-by-size: [(list T) chunkSize:@] -> (list (list T))
::
::  Divides the input list into lists (chunks) with a positive number of at
::  most chunkSize elements. Returns a new list containing the generated lists
::  (chunks) as its elements. Returns an empty list when the input list is empty
::    Examples
::      > (chunk-by-size (limo ~[1 2 3 4 5 6 7]) 2)
::      [i=~[1 2] t=[i=~[3 4] t=~[~[5 6] ~[7]]]]
::    Crash
::      'chunk size is 0'
::    Source
++  chunk-by-size
  |*  [p=(list) q=@ud]
  ?:  =(0 q)  ~|('chunk size is 0' !!)
  =/  res=(list (list _?>(?=(^ p) i.p)))  ~
  =/  i=@ud  0
  =/  next=(list _?>(?=(^ p) i.p))  ~
  |-  ^-  (list (list _?>(?=(^ p) i.p)))
  ?~  p  (flop [(flop next) res])
  ?:  =(i q)  $(i 0, res [(flop next) res], next ~)
  $(i +(i), next [i.p next], p t.p)
::    +collect: [(list T1) mapping:$-(T1 (list T2))] -> (list T2)
::
::  For each element of the list, applies the given function. Concatenates all
::  the results and return the combined list.
::    Examples
::      > (collect (limo ~[1 2 3]) |=(a=* (limo ~[a a])))
::      ~[1 1 2 2 3 3]
::    Source
++  collect
  |*  [p=(list) q=$-(* (list))]
  =/  res=(list)  ~
  |-
  ?~  p  (flop res)
  =/  c=(list)  (q i.p)
  |-
  ?~  c  ^$(p t.p)
  $(c t.c, res [i.c res])
::    +compare: [(list T) (list T) comparer:$-([T T] ?)] -> (list ?)
::
::  Compares two lists element by element using the given comparison function.
::  When an entry exists for both lists, returns the result of the comparer 
::  function. When the second list is longer than the first returns %.y for
::  entries of second where first does not exist. When first list is longer
::  returns %.n for entries of first where second does not exist.
::    Examples
::      > (compare "when" "than" aor)
::      ~[%.n %.y %.n %.y]
::    Source
++  compare
  |*  [b=(list) c=(list) a=$-([* *] ?)]
  =/  res=(list ?)  ~
  =/  bb  b
  =/  cc  c
  |-  ^-  (list ?)
  ?~  bb  ?~  cc  (flop res)  $(cc t.cc, res [%.y res])
  ?~  cc  $(bb t.bb, res [%.n res])
  $(bb t.bb, cc t.cc, res [(a i.bb i.cc) res])
::    +concat: (list (list)) -> (list)
::
::  Returns a new list that contains the elements of each of the lists in order.
::    Examples
::      > (concat (limo [(limo ['a' 'b' 'c' ~]) (limo ['e' 'f' 'g' ~]) 
::          (limo ['h' 'i' 'j' ~]) ~]))
::      ~['a' 'b' 'c' 'e' 'f' 'g' 'h' 'i' 'j']
::      > (concat (limo [(limo [1 'a' 2 'b' ~]) (limo [3 'c' 4 'd' ~]) ~]))
::      ~[1 97 2 98 3 99 4 100]
::    Source
++  concat  zing
::    +contains: [(list) value:*] -> ?
::
::  Tests if the list contains the specified element.
::    Examples
::      > (contains "yep" `(list tape)`~["nope" "yep"])
::      %.y
::    Source
++  contains
  |*  [p=(list) q=*]
  |-  ^-  ?
  ?~  p  %.n
  ?:  =(q i.p)  %.y
  $(p t.p)
::    +count-by: [(list T1) projection:$-(T1 T2)] -> (list [T2 @ud])
::
::  Applies a key-generating function to each element of a list and returns a
::  list yielding unique keys and their number of occurrences in the original
::  list.
::    Examples
::      > %:  count-by
::            (limo ~["where" "when" "there" "then"])
::            |=(a=tape (scag 2 a))
::            ==
::      ~[[[i=t' t="h"] 2] [[i='w' t="h"] 2]]
::    Source
++  count-by
  |*  [p=(list) q=$-(* *)]
  =/  res=(map _?>(?=(^ p) (q i.p)) @ud)  ~
  |-  ^-  (list [_?>(?=(^ p) (q i.p)) @ud])
  ?~  p  ~(tap by res)
  =/  key=_?>(?=(^ p) (q i.p))  (q i.p)
  =/  val  (~(get by res) key)
  ?~  val  $(res `(map _?>(?=(^ p) (q i.p)) @ud)`(~(put by res) key 1), p t.p)
  %=  $
    res  `(map _?>(?=(^ p) (q i.p)) @ud)`(~(put by res) key +(`@ud`(need val)))
    p    t.p
  ==
::    +distinct: (list) -> (list)
::
::  Returns a list that contains no duplicate entries according to generic hash
::  and equality comparisons on the entries. If an element occurs multiple times
::  in the list then the later occurrences are discarded.
::    Examples
::      > (distinct `(list tape)`~["tape1" "tape0" "tape1" "tape0"])
::      ~["tape1" "tape0"]
::    Source
++  distinct
  |*  a=(list)
  =/  b=(list _?>(?=(^ a) i.a))  ~
  =/  c=(set)  ~
  |-  ^+  a
  ?~  a  (flop b)
  ?:  (~(has in c) i.a)  $(a t.a)
  $(a t.a, b [i.a b], c (~(put in c) i.a))
::    +distinct-by: [(list T1) projection:$-(T1 T2)] -> (list T1)
::
::  Returns a list that contains no duplicate entries according to the generic
::  hash and equality comparisons on the keys returned by the given
::  key-generating function. If an element occurs multiple times in the list
::  then the later occurrences are discarded.
::    Examples
::      > =foo `(list [@ @])`~[[1 1] [1 2] [1 3] [2 1]]
::      > (distinct-by foo |=([a=@ b=@] (add a b)))
::      ~[[1 1] [1 2] [1 3]]
::    Source
++  distinct-by
  |*  [p=(list) q=$-(* *)]
  =/  b=(list _?>(?=(^ p) i.p))  ~
  =/  c=(set)  ~
  |-  ^+  p
  ?~  p  (flop b)
  ?:  (~(has in c) (q i.p))  $(p t.p)
  $(p t.p, b [i.p b], c (~(put in c) (q i.p)))
::    +empty: $ -> *(list $)
::
::  Returns an empty list typed by the mold. (The bunt of the typed list.)
::    Examples
::      > (empty @t)
::      ~
::    Source
++  empty
  |*  a=mold
  *(list a)
::    +exactly-one: (list T) -> T
::
::  Returns the only element of the list. Crashes if list has different length.
::    Examples
::      > (exactly-one (limo ~["tape"]))
::      "tape"
::    Crash
::      'list length is not 1'
::    Source
++  exactly-one
  |*  a=(list)
  ?:  =(1 (lent a))  -.a
  ~|('list length is not 1' !!)
::    +except: [(list T) items-to-exclude:(list T)] -> (list T)
::
::  Returns a new list with the distinct elements of the input list which do not
::  appear in the items-to-exclude list, using generic hash and equality
::  comparisons to compare values.
::    Examples
::      > %:  except
::            (limo ~["able" "baker" "charlie" "dog"]) 
::            (limo ~["baker" "dog"])
::        ==
::      ~[[i='a' t="ble"] [i='c' t="harlie"]]
::    Source
++  except
  |*  [p=(list) q=(list)]
  =/  qq  (silt q)
  =/  b=(list _?>(?=(^ p) i.p))  ~
  |-  ^+  p
  ?~  p  (flop b)
  ?:  (~(has in qq) i.p)  $(p t.p)
  $(p t.p, b [i.p b], qq (~(put in qq) i.p))
::    +exists: [(list T) predicate:$-(T ?)] -> ?
::
::  Tests if any element of the list satisfies the given predicate.
::    Examples
::      > =foo |=  a=tape
::        ?:  ?&(=(4 (lent a)) =('a' -.a))  %.y  %.n
::      > (exists (limo ~["aaa" "able" "baker" "charlie" "dog"]) foo)
::      %.y
::    Source
++  exists
  |*  [a=(list) b=$-(* ?)]
  |-  ^-  ?
  ?~  a  %.n
  ?:  (b i.a)  %.y
  $(a t.a)
::    +exists2: [(list T1) (list T2) predicate:$-([T1 T2] ?)] -> ?
::
::  Tests if any pair of corresponding elements of the lists satisfies the given
::  predicate.
::    Examples
::      > =foo |=  [a=tape b=tape]
::        ?:  =(-.a -.b)  %.y  %.n
::      > (exists2 (limo ~["cat" "betty"]) (limo ~["able" "butter"]) foo)
::      %.y
::    Source
++  exists2
  |*  [a=(list) b=(list) c=$-([* *] ?)]
  |-  ^-  ?
  ?~  a  %.n
  ?~  b  %.n
  ?:  (c [i.a i.b])  %.y
  $(a t.a, b t.b)
::    +filter: [(list T) predicate:$-(T ?)] -> (list T)
::
::  Returns a new list containing only the elements of the list for
::  which the given predicate returns "true"
::    Examples
::      > =a |=(a=@ (gth a 1))
::      > (filter `(list @)`[0 1 2 3 ~] a)
::      [i=2 t=~[3]]
::    Source
++  filter  skim
::
::    +findx: [(list T) predicate:$-(T ?)] -> T
::
::  Returns the first element for which the given function returns True. 
::  Crashes if no such element exists.
::    Examples
::      > (findx (gulf [1 30]) |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5)))))
::      15
::    Crash
::      'not found'
::    Source
++  findx
  |*  [a=(list) b=$-(* ?)]
  |-  ^-  _?>(?=(^ a) i.a)
  ?~  a  ~|('not found' !!)
  ?:  (b i.a)  i.a  $(a t.a)
::    +find-all: [(list T) predicate:$-(T ?)] -> (list T))
::
::  Returns all elements for which the given function returns True. 
::  Crashes if no such element exists.
::    Examples
::      > (find-all (gulf [1 30]) |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5)))))
::      ~[15 30]
::    Crash
::      'not found'
::    Source
++  find-all
  |*  [a=(list) b=$-(* ?)]
  =/  c=(list _?>(?=(^ a) i.a))  ~
  |-
  ?~  a  ?~  c  ~|('not found' !!)  (flop c)
  ?:  (b i.a)  $(a t.a, c [i.a c])  $(a t.a)
::    +find-all-by-list: [(list T) arg:(list T) -> (list @)]
::
::  Produces list of indices of all occurrences of the argument list sequence in
::  the sequence of the source list.
::    Examples
::      > (find-all-by-list "cbabab" "ba")
::      ~[1 3]
::    Source
++  find-all-by-list
  |*  [hstk=(list) nedl=(list)]
  ^-  (list @)
  (fand nedl hstk)
::    +find-all-by-unit: [(list T1) chooser:$-(T1 (unit T2))] -> (list T2)
::
::  Applies the given function to successive elements, returning the list of
::  elements where the function returns Some(x). 
::  Crashes when no such element exists.
::    Examples
::      >  %:  find-all-by-unit
::             (limo ~[1 2 3 4])
::             |=(a=@ ?:(=((mod a 2) 0) `a ~))
::            ==
::      ~[2 4]
::    Crash
::      'not found'
::    Source
++  find-all-by-unit
  |*  [hstk=(list) nedl=$-(* (unit *))]
  =/  b=(list _?>(?=(^ hstk) i.hstk))  ~
  |-  ^-  (list _?>(?=(^ hstk) i.hstk))
  ?~  hstk  ?~  b  ~|('not found' !!)
  (flop b)
  =/  x  (nedl i.hstk)
  ?~  x  $(hstk t.hstk)
  $(hstk t.hstk, b [(need x) b])
::    +find-back: [(list T) predicate:$-(T ?)] -> T
::
::  Returns the last element for which the given function returns True. 
::  Crashes if no such element exists.
::    Examples
::      > %:  find-back
::            (gulf [1 30])
::            |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::        ==
::      30
::    Crash
::      'not found'
::    Source
++  find-back
  |*  [a=(list) b=$-(* ?)]
  ?~  a  ~|('not found' !!)
  (findx (flop a) b)
::    +find-back-by-list: [(list T) arg:(list T)] -> @
::
::  Produces the index of the last occurrence of the argument list sequence in
::  the sequence of the source list.
::    Examples
::      > (find-back-by-list "cbabab" "ba")
::      3
::    Source
++  find-back-by-list
  |*  [hstk=(list) nedl=(list)]
  (tail-end (find-all-by-list hstk nedl))
::    +find-back-by-unit: [(list T1) chooser:$-(T1 (unit T2))] -> T2
::
::  Applies the given function to successive elements from the end back, 
::  returning the first result where function returns Some(x) for some x.
::  Crashes when no such element exists.
::    Examples
::      >  %:  find-back-by-unit
::             (limo ~[1 2 3 4])
::             |=(a=@ ?:(=((mod a 2) 0) `a ~))
::          ==
::      4
::    Crash
::      'not found'
::    Source
++  find-back-by-unit
  |*  [hstk=(list) nedl=$-(* (unit *))]
  ^-  _?>(?=(^ hstk) i.hstk)
  (find-by-unit (flop hstk) nedl)
::    +find-by-list: [(list T) arg:(list T)] -> @
::
::  Produces the index of the first occurrence of the argument list sequence in
::  the sequence of the source list.
::    Examples
::      > (find-by-list "cbabab" "ab")
::      2
::    Crash
::      'not found'
::    Source
++  find-by-list
  |*  [hstk=(list) nedl=(list)]
  ^-  @
  =/  x  (find nedl hstk)
  ?~  x  ~|('not found' !!)  (need x)
::    +find-by-unit: [(list T1) chooser:$-(T1 (unit T2))] -> T2
::
::  Applies the given function to successive elements, returning the first
::  result where function returns Some(x) for some x. Crashes when no such
::  element exists.
::    Examples
::      >  (find-by-unit (limo ~[1 2 3 4]) |=(a=@ ?:(=((mod a 2) 0) `a ~)))
::      2
::    Crash
::      'not found'
::    Source
++  find-by-unit
  |*  [hstk=(list) nedl=$-(* (unit *))]
  |-  ^-  _?>(?=(^ hstk) i.hstk)
  ?~  hstk  ~|('not found' !!)
  =/  x  (nedl i.hstk)
  ?~  x  $(hstk t.hstk)
  (need x)
::    +find-index: [(list T) predicate:$-(T ?)] -> @
::
::  Returns the index of the first element in the list that satisfies the given
::  predicate. Crashes if no such element exists.
::    Examples
::      > %:  find-index
::            (gulf [1 30])
::            |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::        ==
::      14
::    Crash
::      'not found'
::    Source
++  find-index
  |*  [a=(list) b=$-(* ?)]
  =/  i  0
  |-  ^-  @
  ?~  a  ~|('not found' !!)
  ?:  (b i.a)  i  $(a t.a, i +(i))
::    +find-index-all: [(list T) predicate:$-(T ?)] -> (list @)
::
::  Returns the list of indices in the list that satisfies the given predicate.
::    Examples
::      > %:  find-index-all
::            (gulf [1 30])
::            |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::          ==
::      ~[14 29]
::    Source
++  find-index-all
  |*  [a=(list) b=$-(* ?)]
  =/  c=(list @)  ~
  =/  i  0
  |-  ^-  (list @)
  ?~  a  (flop c)
  ?:  (b i.a)  $(a t.a, c [i c], i +(i))  $(a t.a, i +(i))
::    +find-index-back: [(list T) predicate:$-(T ?)] -> @
::
::  Returns the index of the last element in the list that satisfies the given
::  predicate. Crashes if no such element exists.
::    Examples
::      > %:  find-index-back
::            (gulf [1 30])
::            |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::        ==
::      29
::    Crash
::      'not found'
::    Source
++  find-index-back
  |*  [a=(list) c=$-(* ?)]
  ?~  a  ~|('not found' !!)
  =/  b  (flop a)
  =/  i  (dec (lent a))
  |-  ^-  @ud
  ?~  b  ~|('not found' !!)
  ?:  (c i.b)  i  
  ?:  =(0 i)  ~|('not found' !!)
  $(b t.b, i (dec i))
::    +first-n: [(list T) count:@ud] -> (list T)
::
::  Returns the first N elements of the list.
::    Examples
::      > (first-n `(list @)`[1 2 3 4 ~] 2)
::      [i=1 t=~[2]]
::      > (first-n `(list @)`[1 2 3 4 ~] 10)
::      [i=1 t=~[2 3 4]]
::    Source
++  first-n
  |*  [p=(list) q=@]
  (scag q p)
::    +fold: [(list T1) state:T2 folder:$-([T1 T2] T2)] -> T2 
::
::  Applies a function to each element of the list, threading an
::  accumulator argument through the computation. Take the second argument, and
::  apply the function to it and the first element of the list. Then feed this
::  result into the function along with the second element and so on. Return the
::  final result. If the input function is f and the elements are i0...iN then
::  computes f (... (f s i0) i1 ...) iN.
::    Examples
::      > (fold (gulf 1 5) 0 |=([n=@ state=@] (add state (mul n n))))
::      55
::    Source
++  fold
  |*  [a=(list) b=* c=_|=(^ [** +<+])]
  |-  ^-  _b
  ?~  a  b
  $(a t.a, b (c i.a b))
::    +fold2: [(list T1) (list T2) state:T3 folder:$-([T1 T2 T3] T3)] -> T3
::
::  Applies a function to corresponding elements of two lists, threading
::  an accumulator argument through the computation. The lists must have
::  identical sizes. If the input function is f and the elements are i0...iN and
::  j0...jN then computes f (... (f s i0 j0)...) iN jN.
::    Examples
::      > %:  fold2
::            (limo ~["Tails" "Head" "Tails"])
::            (limo ~["Tails" "Head" "Head"])
::            0
::            |=([n1=tape n2=tape state=@] ?:(=(n1 n2) +(state) state))
::          ==
::      2
::    Crash
::      'lists of unequal length'
::    Source
++  fold2
  |*  [a=(list) b=(list) c=* d=_|=(^ [** ** +<+])]
  |-  ^-  _c
  ?~  a  ?~  b  c  ~|('lists of unequal length' !!)
  ?~  b  ~|('lists of unequal length' !!)
  $(a t.a, b t.b, c (d i.a i.b c))
::    +fold-back: [(list T1) state:T2 folder:$-([T1 T2] T2)] -> T2
::
::  Applies a function to each element of the list, starting from the end,
::  threading an accumulator argument through the computation. If the input
::  function is f and the elements are i0...iN then computes f i0 (...(f iN s)).
::    Examples
::      > =less-hungry |=  [n=tape state=(list [tape @])]
::          ^+  state
::          ?~  state  (limo ~[[n 1]])
::          [[n +(+.i.state)] state]
::      > %:  fold-back
::            (limo ~["Apple" "Pear" "Orange"])
::            `(list [tape @])`~ 
::            less-hungry
::          ==
::      [i=["Apple" 3] t=~[["Pear" 2] ["Orange" 1]]]
::    Source
++  fold-back
  |*  [a=(list) b=* c=$-([* *] *)]
  (fold (flop a) b c)
::    +fold-back2: [(list T1) (list T2) state:T3 folder:$-([T1 T2 T3] T3)] -> T3
::
::  Applies a function to corresponding elements of two lists, threading
::  an accumulator argument through the computation. The lists must have
::  identical sizes. If the input function is f and the elements are i0...iN and
::  j0...jN then computes f i0 j0 (...(f iN jN s)).
::    Examples
::      > %:  fold-back2
::            (limo ~["Tails" "Head" "Tails"])
::            (limo ~["Tails" "Head" "Head"])
::            `(list tape)`~ 
::            |=([n1=tape n2=tape state=(list tape)] [(weld n1 n2) state])
::          ==
::      ~["TailsTails" "HeadHead" "TailsHead"]
::    Source
++  fold-back2
  |*  [a=(list) b=(list) c=* d=$-([* * *] *)]
  (fold2 (flop a) (flop b) c d)
::    +forall: [(list T) predicate:$-(T ?)] -> ?
::
::  Tests if all elements of the list satisfy the given predicate.
::    Examples
::      > (forall (limo ~[2 4 8]) |=(a=@ ?:(=(0 (mod a 2)) %.y %.n)))
::      %.y
::      > (forall (limo ~[2 1 8]) |=(a=@ ?:(=(0 (mod a 2)) %.y %.n)))
::      %.n
::    Source
++  forall
  |*  [a=(list) predicate=$-(* ?)]
  |-  ^-  ?
  ?~  a  %.y
  ?.  (predicate i.a)  %.n
  $(a t.a)
::    +forall2: [(list T1) (list T2) predicate:$-([T1 T2] ?)] -> ?
::
::  Tests if all corresponding elements of the list satisfy the given
::  predicate pairwise. Crashes on lists of unequal length
::    Examples
::      > %:  forall2
::            (limo ~[1 4 8])
::            (limo ~[3 4 8])
::            |=([a=@ b=@] ?:(=(0 (mod (add a b) 2)) %.y %.n))
::          ==
::      %.y
::      > %:  forall2
::            (limo ~[1 5 8])
::            (limo ~[3 4 8])
::            |=([a=@ b=@] ?:(=(0 (mod (add a b) 2)) %.y %.n))
::          ==
::      %.n
::    Crash
::      'lists of unequal length'
::    Source
++  forall2
  |*  [a=(list) b=(list) predicate=$-(* ?)]
  ?.  =((lent a) (lent b))  ~|('lists of unequal length' !!)
  |-  ^-  ?
  ?~  a  %.y
  ?~  b  ~|('cant get here' !!)
  ?.  (predicate i.a i.b)  %.n
  $(a t.a, b t.b)
::    +from-map: (map) -> (list [* *])
::
::  Produces the list of all key element pairs in map.
::    Examples
::      > =map-00 (to-map (limo ~[['aa' 1] ['bb' 2] ['cc' 3] ['dd' 4]]))
::      > (from-map map-00)
::      ~[[p='bb' q=2] [p='dd' q=4] [p='cc' q=3] [p='aa' q=1]]
::    Source
++  from-map
  |*  a=(map)
  ~(tap by a)
::    +from-set: -> (list)
::
::  Produces the list of element in set
::    Examples
::      > (from-set `(set tap)`[[n="tlon"] l=["urbit" ~ ~] r=["uqbar" ~ ~]])
::    Source
++  from-set
  |*  a=(set)
  ~(tap in a)
::    +get-head: (list T) -> T
::
::  Returns the first element of the list. Crashes on empty list.
::    Examples
::      > (get-head ~[1 2])
::      1
::    Crash
::      'empty list'
::    Source
++  get-head
  |*  a=(list)
  ?~  a  ~|('empty list' !!)
  i.a
::    +get-tail: (list T) -> (list T)
::
::  Returns the list after removing the first element.
::    Examples
::      > (get-tail ~[1 2])
::      ~[2]
::    Crash
::      'empty list'
::    Source
++  get-tail
  |*  a=(list)
  ?~  a  ~|('empty list' !!)
  t.a
::    +group-by: [(list T1) projection:$-(T1 T2)] -> (list [T2 (list T1)]) 
::
::  Applies a key-generating function to each element of a list and yields a
::  list of unique keys. Each unique key contains a list of all elements that
::  match to this key.
::    Examples
::      > (group-by (gulf 1 5) |=(a=@ (mod a 2)))
::      ~[[p=0 q=[i=4 t=~[[2 0]]]] [p=1 q=[i=5 t=~[[3 [1 0] 0]]]]]
::    Source
++  group-by
  |*  [a=(list) b=$-(* *)]
  =/  d=(map * (list *))  ~
  |-
  ?~  a  ~(tap by d)
  =/  e  (b i.a)
  =/  f  (~(get by d) e)
  ?~  f  $(a t.a, d (~(put by d) e ~[i.a]))
  $(a t.a, d (~(put by d) e ~[i.a (need f)]))
::    +indexed: (list T) -> (list [@ T]) 
::
::  Returns a new list whose elements are the corresponding elements of the
::  input list paired with the index (from 0) of each element.
::    Examples
::      > (indexed (gulf 1 3))
::      ~[[0 1] [1 2] [2 3]]
::    Source
++  indexed
  |*  a=(list)
  =/  b=(list [@ _?>(?=(^ a) i.a)])  ~
  =/  i  0
  |-  ^-  (list [@ _?>(?=(^ a) i.a)])
  ?~  a  (flop b)
  $(a t.a, b [[i i.a] b], i +(i))
::    +init: [length:@ud initializer:$-(@ud T)] -> (list T)
::
::  Creates a list by calling the given generator on each index.
::  Crashes on length = 0.
::    Examples
::      > (init 3 |=(a=@ (add a 5)))
::      ~[6 7 8]
::    Crash
::      'empty list'
::    Source
++  init
  |*  [len=@ ini=$-(@ *)]
  =/  a=(list *)  ~
  ?:  =(0 len)  ~|('empty list' !!)
  |-
  ?:  =(0 len)  a
  $(len (dec len), a [(ini len) a])
::    +insert-at: [(list T) index:@ value:T] -> (list T)
::
::  Return a new list with a new item inserted before the given index.
::    Examples
::      > (insert-at (limo ~[2 3 4]) 1 11)
::      ~[2 11 3 4]
::    Source
++  insert-at  into
::    +insertManyAt: [(list T) values=(list T) index=@] -> (list T)
::
::  Return a new list with new items inserted before the given index.
::    Examples
::      > (insert-many-at (limo ~[1 2 5 6 7]) (limo ~[3 4]) 2)
::      ~[1 2 3 4 5 6 7]
::    Crash
::      'out of range'
::    Source
++  insert-many-at
  |*  [a=(list) values=(list) i=@]
  ?:  =(0 (lent values))  a  
  =/  len-a  (lent a)
  ?:  (gth i len-a)  ~|('out of range' !!)
  ?~  values  a
  ?:  =(0 i)  (weld values a)
  ?:  =(len-a i)  (weld a values)
  =/  start  (scag i a)
  =/  end  (slag i a)
  (weld (weld start values) end)
::    +is-empty: (list) -> ?
::
::  Returns true if the list contains no elements, false otherwise.
::    Examples
::      > (is-empty `(list @)`~[2])
::      %.n
::      > (is-empty `(list @)`~)
::      %.y
::    Source
++  is-empty
  |*  a=(list)
  ?~  a  %.y  %.n
::    +item: [(list T) index:@] -> T
::
::  Indexes into the list. The first element has index 0.
::    Examples
::      > (item `(list @)`~["aa" "bb" "cc" "dd"] 2)
::      "cc"
::    Source
++  item
  |*  [a=(list) i=@]
  (snag i a)
::    +iter: [(list T) fun:$-(T *)] -> ~
::
::  Applies the given function to each element of the list, dropping the
::  results.
::    Examples
::      > (iter (limo ~["tape1" "tape2"]) |=(a=tape (lent a)))
::      ~
::    Source
++  iter
  |*  [a=(list) fun=$-(* *)]
  =/  b  (turn a fun)
  ~
::    +iter2: [(list T1) (list T2) fun:$-(T1 T2 *)] -> ~
::
::  Applies the given function to two lists simultaneously, dropping the
::  results. The lists must have identical size.
::    Examples
::      > %:  iter2
::            (limo ~["tape1" "tape2"])
::            (limo ~["tape3" "tape4"])
::            |=([a=tape b=tape] (add (lent a) (lent b)))
::          ==
::      ~
::    Crash
::      'lists of unequal length'
::    Source
++  iter2
  |*  [a=(list) b=(list) fun=$-(* *)]
  =/  b  (map2 a b fun)
  ~
::    +iteri: [(list T) fun:$-([@ T] *)] -> ~
::
::  Applies the given function to each element of the list and the index
::  of element, dropping the results.
::    Examples
::      > (iteri (limo ~[1 2 3]) |=([a=@ b=@] (add a b)))
::      ~
::    Source
++  iteri
|*  [a=(list) fun=$-(* *)]
  =/  b  (mapi a fun)
  ~
::    +iteri2: [(list T1) (list T2) fun:$-(@ T1 T2 *)] -> ~
::
::  Applies the given function to two lists and the current index,
::  dropping the results. The lists must have identical size.
::    Examples
::      > %:  iteri2
::            (limo ~[1 2 3])
::            (limo ~[4 5 6])
::            |=([a=@ b=@ c=@] (add (add a b) c))
::          ==
::      ~
::    Crash
::      'lists of unequal length'
::    Source
++  iteri2
  |*  [a=(list) b=(list) fun=$-(* *)]
  =/  b  (mapi2 a b fun)
  ~
::    +last-n: [(list  T) count:@] -> (list  T)
::
::  Returns the last N elements of the list.
::    Examples
::      > (last-n `(list @)`[1 2 3 4 ~] 2)
::      [i=3 t=~[4]]
::      > (last-n `(list @)`[1 2 3 4 ~] 10)
::      [i=1 t=~[2 3 4]]
::    Source
++  last-n
  |*  [p=(list) q=@]
  (flop (scag q (flop p)))
::    +length: (list  T) -> @u
::
::  Returns the length of the list.
::    Examples
::      > (length [1 2 3 4 ~])
::      4
::      > (length [1 'a' 2 'b' (some 10) ~])
::      5
::    Source
++  length  lent
::    +map-seq: [(list T1) mapping:$-(T1 T2)] -> (list T2)
::
::  Builds a new list whose elements are the results of applying the given
::  gate to each of the elements of the list.
::    Examples
::      > (map (limo [104 111 111 110 ~]) @t)
::      <|h o o n|>
::      > =a |=(a=@ (add a 4))
::      > (map (limo [1 2 3 4 ~]) a)
::      ~[5 6 7 8]
::    Source
++  map-seq  turn
::    +map2: [(list T1) (list T2) mapping:$-([T1 T2] T3)] -> (list T3)
::
::  Builds a new list whose elements are the results of applying the given
::  function to the corresponding elements of the two lists pairwise.
::  Crashes if lists are of unequal length
::    Examples
::      >  (map2 (limo ~[1 2 3 4]) (limo ~[5 6 7 8]) |=(a=[@ @] (add -.a +.a)))
::      ~[6 8 10 12]
::    Crash
::      'lists of unequal length'
::    Source
++  map2
  |*  [a=(list) b=(list) c=gate]
  =/  d=(list)  ~
  |-
  ?~  a  ?~  b  (flop d)  ~|('lists of unequal length' !!)
  ?~  b  ~|('lists of unequal length' !!)
  $(a t.a, b t.b, d [(c i.a i.b) d])
::    +map3: [(list T1) (list T2) (list T3) $-([T1 T2 T3] T4)] -> (list T4)
::
::  Builds a new list whose elements are the results of applying the given
::  function to the corresponding elements of the three lists
::  simultaneously.
::    Examples
::      > %:  map3
::            (limo ~[1 2 3 4])
::            (limo ~[5 6 7 8])
::            (limo ~[9 10 11 12])
::            |=(a=[@ @ @] (add (add -.a +<.a) +>.a))
::          ==
::      ~[15 18 21 24]
::    Crash
::      'lists of unequal length'
::    Source
++  map3
  |*  [a=(list) b=(list) c=(list) d=gate]
  =/  e=(list)  ~
  |-
  ?~  a  ?~  b  ?~  c  (flop e)
    ~|('lists of unequal length' !!)
    ~|('lists of unequal length' !!)
  ?~  b  ~|('lists of unequal length' !!)
  ?~  c  ~|('lists of unequal length' !!)
  $(a t.a, b t.b, c t.c, e [(d i.a i.b i.c) e])
::    +map-fold: [(list T1) state:T2 $-([T1 T2] [T3 T2])] -> [(list T3) T2]
::
::  Combines map and fold. Builds a new list whose elements are the results of
::  applying the given function to each of the elements of the input list. The
::  function is also used to accumulate a final value.
::    Examples
::      > =input `(list [@t @])`~[['in' 1] ['out' 2] ['in' 3]]
::      > =foo |*  [p=[@t @] state=@]
::      ^-  [[@t @] @]
::      ?:  =(-.p 'in')  [['in' (mul +.p 2)] (add state +.p)]
::      [['out' (mul +.p 2)] (mul state +.p)]
::      > (map-fold input 0 foo)
::      [~[['in' 2] ['out' 4] ['in' 6]] 5]
::    Source
++  map-fold  spin
::    +map-fold-back: [(list T1) state:T2 $-([T1 T2] [T3 T2])] -> [(list T3) T2]
::
::  Combines map and foldBack. Builds a new list whose elements are the results
::  of applying the given function to each of the elements of the input list, 
::  starting from the end. 
::  The function is also used to accumulate a final value.
::    Examples
::      > =input `(list [@t @])`~[['in' 1] ['out' 2] ['in' 3]]
::      > =foo |*  [p=[@t @] state=@]
::      ^-  [[@t @] @]
::      ?:  =(-.p 'in')  [['in' (mul +.p 2)] (add state +.p)]
::      [['out' (mul +.p 2)] (mul state +.p)]
::      > (map-fold-back input 0 foo)
::      [~[['in' 6] ['out' 4] ['in' 2]] 7]
::    Source
++  map-fold-back
  |*  [a=(list) state=* c=$-([* *] [* *])]
  (spin (flop a) state c)
::    +mapi: [(list T1) mapping:$-([@ T1] T2)] -> (list T2)
::
::  Builds a new list whose elements are the results of applying the given
::  function to each of the elements of the list. The integer index passed
::  to the function indicates the index (from 0) of element being transformed.
::    Examples
::      > (mapi (limo ~[1 2 3]) |=([a=@ b=@] (add a b)))
::      ~[1 3 5]
::    Source
++  mai
  |*  [a=(list) b=gate]
  =|  i=@ud
  =>  .(a (homo a))
  ^-  (list _?>(?=(^ a) (b i i.a)))
  |-
  ?~  a  ~
  :-  i=(b i i.a) 
  t=$(a t.a, i +(i))
++  mapi
  |*  [a=(list) fun=$-([@ *] *)]
  =/  i  0
  =/  b=(list)  ~
  |-
  ?~  a  (flop b)
  $(a t.a, b [(fun i i.a) b], i +(i))
::    +mapi2: [(list T1) (list T2) mapping:$-([@ T1 T2] T3)] -> (list T3)
::
::  Like mapi, but mapping corresponding elements from two lists of equal length.
::    Examples
::      > %:  mapi2
::            (limo ~[1 2 3])
::            (limo ~[4 5 6])
::            |=([a=@ b=@ c=@] (add (add a b) c))
::          ==
::      ~[5 8 11]
::    Crash
::      'lists of unequal length'
::    Source
++  mapi2
  |*  [a=(list) b=(list) fun=$-([@ * *] *)]
  =/  i  0
  =/  c=(list)  ~
  |-
  ?~  a  ?~  b  (flop c)  ~|('lists of unequal length' !!)
  ?~  b  ~|('lists of unequal length' !!)
  $(a t.a, b t.b, c [(fun i i.a i.b) c], i +(i))
::    +maxi: (list T) -> T
::
::  Return the greatest of all elements of the list, compared via Operators.max.
::    Examples
::      > (maxi (limo ~[10 12 11]))
::      12
::      > (maxi (limo ~["max" "add" "busy"]))
::    Crash
::      'empty list'
::    Source
++  maxi
  |*  a=(list)
  ~|  'empty list'
  =/  m  -.a
  |-
  ?~  a  m
  ?:  (aor m i.a)  $(m i.a, a t.a)
  $(a t.a)
::    +maxBy: [(list T) projection:$-(* *)] -> T
::
::  Returns the greatest of all elements of the list, compared via Operators.max
::  on the function result.
::    Examples
::      > (max-by (limo ~["aa" "mmmm" "zzz"]) |=(a=tape (lent a)))
::      "mmmm"
::    Crash
::      'empty list'
::    Source
++  max-by
  |*  [a=(list) q=$-(* *)]
  ~|  'empty list'
  =/  m  -.a
  |-
  ?~  a  m
  ?:  (aor (q m) (q i.a))  $(m i.a, a t.a)
  $(a t.a)
::    +mini: (list T) 
::
::  Returns the lowest of all elements of the list, compared via Operators.min.
::    Examples
::      > (mini (limo ~[11 12 10]))
::      10
::      > (mini (limo ~["min" "add" "busy"]))
::      "add"
::    Crash
::      'empty list'
::    Source
++  mini
  |*  a=(list)
  ~|  'empty list'
  =/  m  -.a
  |-
  ?~  a  m
  ?.  (aor m i.a)  $(m i.a, a t.a)
  $(a t.a)
::    +minBy: (list T) projection
::
::  Returns the lowest of all elements of the list, compared via Operators.min
::  on the function result
::    Examples
::      > (min-by (limo ~["aa" "mmmm" "zzz"]) |=(a=tape (lent a)))
::      "aa"
::    Crash
::      'empty list'
::    Source
++  min-by
  |*  [a=(list) q=$-(* *)]
  ~|  'empty list'
  =/  m  -.a
  |-
  ?~  a  m
  ?.  (aor (q m) (q i.a))  $(m i.a, a t.a)
  $(a t.a)
::    +pairwise: (list T) -> (list [T T]) 
::
::  Returns a list of each element in the input list and its predecessor, with
::  the exception of the first element which is only returned as the predecessor
::  of the second element.
::    Examples
::    > (pairwise (limo ~[1 2 3 4]))
::    ~[[1 2] [2 3] [3 4]]
::    Source
++  pairwise
  |*  a=(list)
  =/  b=(list [_?>(?=(^ a) i.a) _?>(?=(^ a) i.a)])  ~
  |-
  ?:  (lth (lent a) 2)  (flop b)
  ?~  a  ~|('cant get here' !!)
  ?~  t.a  ~|('cant get here' !!)
  $(a t.a, b [[i.a i.t.a] b])
::    +partition: [(list T) predicate:$-( T ?)] -> [(list T) (list T)]
::
::  Splits the list into two lists, containing the elements for
::  which the given predicate returns True and False respectively. Element order
::  is preserved in both of the created lists.
::    Examples
::      > =a |=(a=@ (gth a 1))
::      > (partition `(list @)`[0 1 2 3 ~] a)
::      [p=[i=2 t=~[3]] q=[i=0 t=~[1]]]
::    Source
++  partition  skid
::    +permute: [(list T) projection:$-(@ @)] -> (list T)
::
::  Returns a list with all elements permuted according to the permutation
::  specified by operating on the element indices.
::    Examples
::      > (permute (limo ~[1 2 3 4]) |=(i=@ (mod +(i) 4)))
::      ~[4 1 2 3]
::    Source
++  permute
  |*  [a=(list) q=$-(@ @)]
  =/  b=(list [@ _?>(?=(^ a) i.a)])  ~
  =/  i  0
  |-
  ?~  a  +:(unzip (sort b aor))
  $(a t.a, b [[(q i) i.a] b], i +(i))
::    +reduce: [(list T) reduction:$-([T T] T)] -> T
::
::  Apply a function to each element of the list, threading an accumulator
::  argument through the computation. Apply the function to the first two
::  elements of the list. Then feed this result into the function along with the
::  third element and so on. Return the final result. If the input function is f
::  and the elements are i0...iN then computes f (... (f i0 i1) i2 ...) iN.
::    Examples
::      > %+  reduce
::            `(list tape)`~["urbit" "is" "fun"]
::            |=([a=tape b=tape] (welp (snoc a ' ') b))
::      "urbit is fun"
::    Crash
::      'empty list'
::    Source
++  reduce
  |*  [a=(list) q=$-([* *] *)]
  ?~  a  ~|('empty list' !!)
  =/  b  `_?>(?=(^ a) i.a)`i.a
  =/  c  t.a
  |-  
  ?~  c  b
  $(b (q b i.c), c t.c)
::    +reduceBack: [(list T) reduction:$-([T T] T)] -> T
::
::  Applies a function to each element of the list, starting from the end,
::  threading an accumulator argument through the computation. If the input
::  function is f and the elements are i0...iN then computes 
::  f i0 (...(f iN-1 iN)).
::    Examples
::      > %+  reduce-back
::            `(list tape)`~["urbit" "is" "fun"]
::            |=([a=tape b=tape] (welp (snoc a ' ') b))
::      "fun is urbit"
::    Crash
::      'empty list'
::    Source
++  reduce-back
  |*  [a=(list) q=$-([* *] *)]
  (reduce (flop a) q)
::    +remove-at: [(list T) index:@] -> (list T)
::
::  Return a new list with the item at a given index removed.
::    Examples
::      > (remove-at "good day, urbit!" 8)
::      "good day urbit!"
::      > (remove-at `(list @)`[1 2 3 4 ~] 2)
::      ~[1 2 4]
::    Crash
::      'out of range'
::    Source
++  remove-at
  |*  [a=(list) i=@]
  ?:  (gte i (lent a))  ~|('out of range' !!)
  (oust [i 1] a)
::    +remove-many-at: [(list T) index=@ count=@] -> (list T)
::
::  Return a new list with the number of items starting at a given index removed
::    Examples
::      > (remove-many-at "good day, urbit!" [4 5])
::      "good urbit!"
::      > (remove-many-at `(list @)`[1 2 3 4 ~] [2 2])
::      ~[1 2]
::    Crash
::      'out of range'
::    Source
++  remove-many-at
  |*  [a=(list) i=@ c=@]
  ?:  (gth (add i c) (lent a))  ~|('out of range' !!)
  (oust [i c] a)
::    +replicate: [count=@ initial=T] -> (list T)
::
::  Creates a list by replicating the given initial value.
::    Examples
::      > (replicate 20 %a)
::      ~[%a %a %a %a %a %a %a %a %a %a %a %a %a %a %a %a %a %a %a %a]
::      > (replicate 5 ~s1)
::      ~[~s1 ~s1 ~s1 ~s1 ~s1]
::      > `@dr`(roll (replicate 5 ~s1) add)
::      ~s5
::    Source
++  replicate  reap
::    +reverse: (list T) -> (list T)
::
::  Returns a new list with the elements in reverse order.
::    Examples
::      > =a [1 2 3 ~]
::      > (flop a)
::      ~[3 2 1]
::      > (flop (flop a))
::      ~[1 2 3]
::    Source
++  reverse  flop
::    +scanx: [(list T1) state:T2 folder:$-([T1 T2] T2)] -> (list T2)
::
::  Applies a function to each element of the list and an accumulator, threading
::  the accumulator argument through the computation. Returns the list of 
::  intermediate results and the final result.
::    Examples
::      > %:  scanx
::            `(list tape)`~["urbit" "is" "fun"]
::            ""
::           |=([a=tape b=tape] (welp (snoc b ' ') a))
::        ==
::      ~["" " urbit"  "urbit is" " urbit is fun"]
::    Source
++  scanx
  |*  [a=(list) state=* fun=$-([* *] *)]
  =/  b=(list _state)  ~
  |-  ^-  (list _?>(?=(^ a) i.a))
  ?~  a  (flop [state b])
  $(a t.a, b [state b], state (fun i.a state))
::    +scan-back: [(list T) state:T2 folder:$-(T1 T2)] -> (list T2)
::
::  Like fold-back, but returns both the intermediary and final results
::    Examples
::    Source
++  scan-back
  |*  [a=(list) state=* fun=$-([* *] *)]
  =/  c=(list _?>(?=(^ a) i.a))  (flop a)
  =/  b=(list _state)  ~
  |-  ^-  (list _?>(?=(^ a) i.a))
  ?~  c  (flop [state b])
  $(c t.c, b [state b], state (fun i.c state))
::    +singleton: value: T -> (list T)
::
::  Returns a list that contains one item only.
::    Examples
::      > (singleton "tape")
::      ~["tape"]
::    Source
++  singleton
  |*  a=*
  (limo ~[a])
::    +skip-n: [(list T) count:@] -> (list T)
::
::  Returns the list after removing the first N elements.
::    Examples
::      > (skip-n `(list @)`[1 2 3 4 ~] 2)
::      ~[3 4]
::    Crash
::      'out of range'
::    Source
++  skip-n
  |*  [p=(list) q=@]
  ?~  p  ?~  q  p  ~|('out of range' !!)
  ?~  q  p
  $(p t.p, q (dec q))
::    +skip-while: [(list T) predicate:$-(T ?)] -> (list T)
::
::  Bypasses elements in a list while the given predicate returns True, and then
::  returns the remaining elements of the list.
::    Examples
::    > %:  skip-while
::          (limo ~["a" "bbb" "cc" "d"])
::          |=(a=tape (lth (lent a) 3))
::      ==
::    ~["bbb" "cc" "d"]
::    Source
++  skip-while
  |*  [a=(list) b=$-(* ?)]
  =/  c=(list _?>(?=(^ a) i.a))  ~
  |-  ^+  a
  ?~  a  (flop c)  
  ?~  c  ?:  (b i.a)  $(a t.a)  $(a t.a, c [i.a c])
  $(a t.a, c [i.a c])
::    +sort-by: [(list T) projection:$-(T *)] -> (list T)
::
::  Sorts the given list using keys given by the given projection. Keys are
::  compared using Operators.compare.
::    Examples
::      > (sort-by (limo ~["bb" "a" "dddd" "ccc"]) |=(a=tape (lent a)))
::      ~["a" "bb" "ccc" "dddd"]
::    Source
++  sort-by
  |*  [a=(list) proj=$-(* *)]
  =/  b  (turn a proj)
  =/  c  (zip b a)
  +:(unzip (sort c aor))
::    +sort-by-descending: [(list T) projection:$-(T *)] -> (list T)
::
::  Sorts the given list in descending order using keys given by the given
::  projection. Keys are compared using Operators.compare.
::    Examples
::      > %:  sort-by-descending
::            (limo ~["bb" "a" "dddd" "ccc"])  |=(a=tape (lent a))
::        ==
::      ~["dddd" "ccc" "bb" "a"]
::    Source
++  sort-by-descending
  |*  [a=(list) proj=$-(* *)]
  =/  b  (turn a proj)
  =/  c  (zip b a)
  +:(unzip (sort c |=([a=* b=*] (aor b a))))
::    +sort-descending: (list T) -> (list T)
::
::  Sorts the given list in descending order using Operators.compare.
::    Examples
::      > (sort-descending (limo ~[4 2 1 3]))
::      ~[4 3 2 1]
::    Source
++  sort-descending
  |*  a=(list)
  (sort a |=([a=* b=*] (aor b a)))
::    +sort-qik: (list T) -> (list T)
::
::  Sorts the given list in ascending order using Operators.compare.
::    Examples
::      > (sort-qik (limo ~[4 2 1 3]))
::      ~[1 2 3 4]
::    Source
++  sort-qik
  |*  a=(list)
  (sort a aor)
::    +split-at: [(list T) index:@] -> [(list T) (list T)]
::
::  Splits a list into two lists, at the given index.
::    Examples
::      > (split-at (limo ~[1 2 3 4 5]) 2)
::      [~[1 2] ~[3 4 5]]
::    Source
++  split-at
  |*  [p=(list) i=@]
  [(scag i p) (slag i p)]
::    +split-into: [(list T) count:@] -> (list (list T))
::
::  Splits the input list into at most count chunks.
::    Examples
::    >  (split-into (gulf 1 10) 4)
::    Crash
::      'count is 0'
::    Source
++  split-into
  |*  [a=(list) i=@]
  ?~  i  ~|('count is 0' !!)
  =/  b=(list (list _?>(?=(^ a) i.a)))  ~
  |-
  ?:  =(0 (lent a))  (flop b)
  =/  q  (div (lent a) i)
  =/  r  (mod (lent a) i)
  =/  l  ?:  =(0 r)  q  +(q)
  =/  c=(list _?>(?=(^ a) i.a))  ~
  |-
  ?~  l  ^$(b [(flop c) b], i (dec i))
  ?~  a  ?~  c  (flop b)  (flop [(flop c) b])
  $(c [i.a c], l (dec l), a t.a)
::    +sum: (list @) -> @
::
::  Returns the sum of the elements in the list.
::    Examples
::      > (sum (limo ~[1 2 3]))
::      6
::    Source
++  sum
  |*  a=(list @)
  =/  b=@  0
  |-
  ?~  a  b
  $(a t.a, b (add b i.a))
::    +sum-by: [(list T) projection:$-(T @)] -> @
::
::  Returns the sum of the results generated by applying the function to each
::  element of the list.
::    Examples
::      > (sum-by (limo ~["a" "bb" "ccc"]) |=(a=tape (lent a)))
::      6
::    Source
++  sum-by
  |*  [a=(list) proj=$-(* @)]
  =/  b=@  0
  |-
  ?~  a  b
  $(a t.a, b (add b (proj i.a)))
::    +tail-end: (list T) -> T
::
::  Returns the last element of the list.
::  Crash when the input does not have any elements.
::    Examples
::      > (last ~[1 2 3])
::      3
::    Crash
::      'empty list'
::    Source
++  tail-end
  |*  a=(list)
  ?~  a  ~|('empty list' !!)
  (rear a)
::    +take-while: [(list T) predicate:$-(T ?)] -> (list T)
::
::  Returns a list that contains all elements of the original list while the
::  given predicate returns True, and then returns no further elements.
::    Examples
::      > %:  take-while
::            (limo ~["a" "bb" "ccc" "d"]) 
::            |=(a=tape (lth (lent a) 3))
::        ==
::      ~["a" "bb"]
::    Source
++  take-while
  |*  [a=(list) b=$-(* ?)]
  =/  c=(list _?>(?=(^ a) i.a))  ~
  |-  ^+  a
  ?~  a  (flop c)  
  ?:  (b i.a)  $(a t.a, c [i.a c])
  (flop c)
::    +to-map: (list [* *]) ->
::
::  Produces a map from a list.
::    Examples
::      > (to-map (limo ~[['aa' 1] ['bb' 2] ['cc' 3] ['dd' 4]]))
::      [n=[p='dd' q=4] l=[n=[p='cc' q=3] l=[n=[p='aa' q=1] l=~ r=~] r=~] 
::                      r=[n=[p='bb' q=2] l=~ r=~]]
::    Source
++  to-map
  |*  a=(list)
  (malt a)
::    +to-set: (list) ->
::
::  Produces a set from a list.
::    Examples
::      > (to-map (limo ~[['aa' 1] ['bb' 2] ['cc' 3] ['dd' 4]]))
::      [n=['dd' 4] l=[n=['cc' 3] l=[n=['aa' 1] ~ ~] ~] r=[n=['bb' 2] ~ ~]]
::    Source
++  to-set
  |*  a=(list)
  (silt a)
::    +transpose: (list (list T)) -> ?([~ ~] (list (list T)))
::
::  Returns the transpose of the given sequence of lists.
::  Returns [~ ~] when all lists of list are ~.
::    Examples
::      > %-  transpose
::              %:  limo 
::                  (limo ~["a" "b" "c"]) 
::                  (limo ~["aa" "bb" "cc"]) 
::                  (limo ~["aaa" "bbb" "ccc"])
::                  ~
::              ==
::      ~[~["a" "aa" "aaa"] ~["b" "bb" "bbb"] ~["c" "cc" "ccc"]]
::    Crash
::      'lists of unequal length'
::    Source
++  transpose
  |*  a=(list (list))
  =/  aa  a
  =/  equal=?  %.y
  ~|  'lists of unequal length'
  |-  ^-  (list (list _?>(?=(^ ^ a) -.-.a)))
  ?:  =(%.n equal)  !!
  ?~  aa  (transpose-jgd a)
  ?~  t.aa  (transpose-jgd a)
  ?:  =((lent i.aa) (lent i.t.aa))  $(aa t.aa)  $(equal %.n)
::    +transpose-jgd: (list (list T)) -> ?([~ ~] (list (list T)))
::
::  Returns the jagged transpose of the given sequence of lists.
::  Returns [~ ~] when all lists of list are ~.
::    Examples
::      > %-  transpose-jgd
::              %:  limo 
::                  (limo ~["a" "b" "c"]) 
::                  (limo ~["aa" "cc"]) 
::                  (limo ~["aaa" "bbb" "ccc"])
::                  ~
::              ==
::      ~[~["a" "aa" "aaa"] ~["b" "cc" "bbb"] ~["c" "ccc"]]
::    Source
++  transpose-jgd
  |*  a=(list (list))
  =/  aa=(list (list _?>(?=(^ ^ a) -.-.a)))  a
  =/  b=(list (list _?>(?=(^ ^ a) -.-.a)))  ~
  =/  bb=(list _?>(?=(^ ^ a) -.-.a))  ~
  |-  ^-  (list (list _?>(?=(^ ^ a) -.-.a)))
  ?~  a  (flop b)
  =/  c=(list (list _?>(?=(^ ^ a) -.-.a)))  ~
  |-
  ?~  aa
    %=  ^$
      a   (flop c)
      aa  (flop c)
      b   [(flop bb) b]
      bb  ~
    ==
  ?~  -.aa  $(aa t.aa)
  ?~  ->.aa  $(aa t.aa, bb [-<.aa bb])
  $(aa t.aa, bb [-<.aa bb], c [->.aa c])
::    +try-exactly-one: (list T) -> (unit T)
::
::  Returns the only element of the list or None if it is empty or contains more
::  than one element.
::    Examples
::      > (try-exactly-one (limo ~["tape"]))
::      [~ i=[i=t' t="ape"]]
::    Source
++  try-exactly-one
  |*  a=(list)
  ?:  =(1 (lent a))  `-.a
  ~
::    +try-find: [(list T) predicate:$-(T ?)] -> (unit T)
::
::  Returns the first element for which the given function returns True.
::  Return None if no such element exists.
::    Examples
::      > (try-find (gulf [1 30]) |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5)))))
::      `15
::    Source
++  try-find
  |*  [a=(list) b=$-(* ?)]
  |-  ^-  (unit _?>(?=(^ a) i.a))
  ?~  a  ~
  ?:  (b i.a)  `i.a  $(a t.a)
::    +try-find-back: [(list T) predicate:$-(T ?)] -> (unit T)
::
::  Returns the last element for which the given function returns True.
::  Return None if no such element exists.
::    Examples
::      > %:  try-find-back
::            (gulf [1 30])
::            |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::        ==
::      `30
::    Source
++  try-find-back
  |*  [a=(list) b=$-(* ?)]
  ?~  a  ~
  (try-find (flop a) b)
::    +try-find-by-unit: [(list T) chooser:$-(T (unit T))] -> (unit T)
::
::  Applies the given function to successive elements, returning Some(x) for the
::  first result where function returns Some(x).
::  If no such element exists then return None.
::    Examples
::      >  (search-by-unit (limo ~[1 2 3 4]) |=(a=@ ?:(=((mod a 2) 0) `a ~)))
::      `2
::    Crash
::      'not found'
::    Source
++  try-find-by-unit
  |*  [hstk=(list) nedl=$-(* (unit *))]
  |-  ^-  (unit _?>(?=(^ hstk) i.hstk))
  ?~  hstk  ~
  =/  x  (nedl i.hstk)
  ?~  x  $(hstk t.hstk)  x
::    +try-find-index: [(list T) predicate:$-(T ?)] -> (unit @)
::
::  Returns the index of the first element in the list that satisfies the given
::  predicate. Return None if no such element exists.
::    Examples
::      > %:  try-find-index
::            (gulf [1 30])
::            |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::          ==
::      `14
::    Source
++  try-find-index
  |*  [a=(list) b=$-(* ?)]
  =/  i  0
  |-  ^-  (unit @)
  ?~  a  ~
  ?:  (b i.a)  `i  $(a t.a, i +(i))
::    +try-find-index-back: [(list T) predicate:$-(T ?)] -> (unit @)
::
::  Returns the index of the last element in the list that satisfies the given
::  predicate. Return None if no such element exists.
::    Examples
::    > %:  try-find-index-back
::          (gulf [1 30])
::          |=(a=@ud ?&(=(0 (mod a 3)) =(0 (mod a 5))))
::        ==
::    `29
::    Source
++  try-find-index-back
  |*  [a=(list) c=$-(* ?)]
  ?~  a  ~
  =/  b  (flop a)
  =/  i  (dec (lent a))
  |-  ^-  (unit @ud)
  ?~  b  ~
  ?:  (c i.b)  `i  
  ?:  =(0 i)  ~
  $(b t.b, i (dec i))
::    +try-head: (list T) -> (unit T)
::
::  Returns the first element of the list, or None if the list is empty.
::    Examples
::      > (try-head ~[1 2])
::      `1
::    Source
++  try-head
  |*  a=(list)
  ?~  a  ~
  `i.a
::    +try-item: [(list T) index:@] -> (unit T)
::
::  Tries to find the nth element in the list. Returns None if index is negative
::  or the list does not contain enough elements.
::    Examples
::      > (try-item `(list @)`~["aa" "bb" "cc" "dd"] 2)
::        [~ "cc"]
::      > (try-item `(list tape)`~["aa" "bb"] 2)
::      ~
::    Source
++  try-item
  |*  [a=(list) i=@]
  ?:  (gte i (lent a))  ~
  `(snag i a)
::    +try-remove-at: [(list T) index:@] -> (unit (list T))
::
::  Attempt a new list with the item at a given index removed returning 
::  Some((list T)) upon success.
::    Examples
::      > (try-remove-at "good day, urbit!" 8)
::      [~ "good day urbit!"]
::      > (try-remove-at `(list @)`[1 2 3 4 ~] 2)
::      [~ ~[1 2 4]]
::    Source
++  try-remove-at
  |*  [a=(list) i=@]
  ?:  (gte i (lent a))  ~
  `(oust [i 1] a)
::    +try-remove-many-at: [(list T) index=@ count=@] -> (list T)
::
::  Return a new list with the number of items starting at a given index removed
::  returning Some((list T)) upon success.
::    Examples
::      > (try-remove-many-at "good day, urbit!" [4 5])
::      [~ "good urbit!"]
::      > (try-remove-many-at `(list @)`[1 2 3 4 ~] [2 2])
::      [~ ~[1 2]]
::    Source
++  try-remove-many-at
  |*  [a=(list) i=@ c=@]
  ?:  (gth (add i c) (lent a))  ~
  `(oust [i c] a)
::    +try-tail: (list T) -> (unit (list T))
::
::  Returns the elements of the list after the first.
::    Examples
::      > (try-tail ~[1 2])
::      `~[2]
::    Source
++  try-tail
  |*  a=(list)
  ?~  a  ~
  `t.a
::    +try-tail-end: (list T) -> (unit T)
::
::  Returns the last element of the list. Return None if no such element exists.
::    Examples
::      > (try-tail-end ~[1 2 3])
::      `3
::    Source
++  try-tail-end
  |*  a=(list)
  ?~  a  ~
  `(rear a)
::    +try-update-at: [(list T) index:@ value:T] -> (list T)
::
::  Return a new list with the item at a given index set to the new value.
::    Examples
::      > (try-update-at (limo ~[2 3 4]) 1 11)
::      [~ ~[2 11 4]]
::      > (try-update-at (limo ~[2 3 4]) 3 11)
::      ~
::    Crash
::      'not found'
::    Source
++  try-update-at
  |*  [a=(list) b=@ c=*]
  ?:  (gte b (lent a))  ~
  `(snap a b c)
::    +unfold: [state:T1 generator:$-(T1 -> (unit [T1 T2]))] -> (list T2)
::
::  Returns a list that contains the elements generated by the given computation
::  The generator is repeatedly called to build the list until it returns None.
::  The given initial state argument is passed to the element generator.
::    Examples
::      > (unfold 1 |=(a=@ ?:((gth a 100) ~ `[(mul a 2) a])))
::      ~[1 2 4 8 16 32 64]
::    Source
++  unfold
  |*  [state=* gen=$-(* (unit [* *]))]
  =/  res=(list)  ~
  |-
  =/  x  (gen state)
  ?~  x  (flop res)
  =/  y  (need x)
  $(state -.y, res [+.y res])
::    +unzip: (list [T1 T2]) - [(list T1) (list T2)]
::
::  Splits a list of pairs into two lists.
::    Examples
::      > (unzip (limo ~[[1 "aa"] [2 "bb"]]))
::      [~[1 2] ~["aa" "bb"]]
::    Source
++  unzip
  |*  a=(list [* *])
  =/  b=(list *)  ~
  =/  c=(list *)  ~
  |-
  ?~  a  [(flop b) (flop c)]
  $(a t.a, b [-.i.a b], c [+.i.a c])
::    +unzip3: (list [T1 T2 T3]) - [(list T1) (list T2) (list T3)]
::
::  Splits a list of triples into three lists.
::    Examples
::      > (unzip3 (limo ~[[1 "aa" 'a'] [2 "bb" 'b']]))
::      [~[1 2] ~["aa" "bb"] ~['a' 'b']]
::    Source
++  unzip3
  |*  a=(list [* *])
  =/  b=(list *)  ~
  =/  c=(list *)  ~
  =/  d=(list *)  ~
  |-
  ?~  a  [(flop b) (flop c) (flop d)]
  $(a t.a, b [-.i.a b], c [+<.i.a c], d [+>.i.a d])
::    +update-at: [(list T) index:@ value:T] -> (list T)
::
::  Return a new list with the item at a given index set to the new value.
::    Examples
::      > (update-at (limo ~[2 3 4]) 1 11)
::      ~[2 11 4]
::    Crash
::      'not found'
::    Source
++  update-at
  |*  [a=(list) b=@ c=*]
  ?:  (gte b (lent a))  ~|('not found' !!)
  (snap a b c)
::    +windowed: [(list T) window-size:@] -> (list (list T))
::
::  Returns a list of sliding windows containing elements drawn from the input
::  list. Each window is returned as a fresh list.
::    Examples
::      > (windowed (limo ~[1 2 3 4 5]) 3)
::      ~[~[1 2 3] ~[2 3 4] ~[3 4 5]]
::    Crash
::      'empty list'
::      'window length is 0'
::      'list shorter than window'
::    Source
++  windowed
  |*  [p=(list *) q=@]
  ?~  q  ~|('window length is 0' !!)
  =/  b=(list (list _?>(?=(^ p) i.p)))  ~
  =/  sub-tree=(list _?>(?=(^ p) i.p))  ~
  =/  pp=(list _?>(?=(^ p) i.p))  p
  |-  ^-  (list (list _?>(?=(^ p) i.p)))
  ?~  p  ~|('empty list' !!)
  ?~  pp  ?:  (lth (lent sub-tree) q)  
      ?~  b  ~|('list shorter than window' !!)  (flop b)
  $(pp t.p, b [(flop sub-tree) b], sub-tree ~)
  ?:  =((lent sub-tree) q)
    $(p t.p, pp t.p, b [(flop sub-tree) b], sub-tree ~)
  $(pp t.pp, sub-tree [i.pp sub-tree])
::    +zip: [(list T1) (list T2)] -> (list [T1 T2])
::
::  Combines the two lists into a list of pairs. The two lists must have equal
::  lengths.
::    Examples
::      > (zip `(list @)`~[1 2] `(list @)`~["aa" "bb"])
::      ~[[1 "aa"] [2 "bb"]]
::    Crash
::      'lists of unequal length'
::    Source
++  zip
  |*  [a=(list) b=(list)]
  =/  c=(list [_?>(?=(^ a) i.a) _?>(?=(^ b) i.b)])  ~
  |-  ^-  (list [_?>(?=(^ a) i.a) _?>(?=(^ b) i.b)])
  ?~  a  ?~  b  (flop c)  ~|('lists of unequal length' !!)
  ?~  b  ~|('lists of unequal length' !!)
  $(a t.a, b t.b, c [[i.a i.b] c])
::    +zip3: [(list T1) (list T2) (list T3)] -> (list [T1 T2 T3])
::
::  Combines the three lists into a list of triples. The lists must have equal
::  lengths.
::    Examples
::      > %:  zip3
::            `(list @)`~[1 2]
::            `(list tape)`~["aa" "bb"]
::            `(list @t)`~['a' 'b']
::          ==
::      ~[[1 "aa" 'a'] [2 "bb" 'b']]
::    Crash
::      'lists of unequal length'
::    Source
++  zip3
  |*  [a=(list) b=(list) c=(list)]
  =/  d=(list [_?>(?=(^ a) i.a) _?>(?=(^ b) i.b) _?>(?=(^ c) i.c)])  ~
  |-  ^-  (list [_?>(?=(^ a) i.a) _?>(?=(^ b) i.b) _?>(?=(^ c) i.c)])
  ?~  a  ?~  b  ?~  c  (flop d)
                ~|('lists of unequal length' !!)
         ~|('lists of unequal length' !!)
  ?~  b   ~|('lists of unequal length' !!)
  ?~  c   ~|('lists of unequal length' !!)
  $(a t.a, b t.b, c t.c, d [[i.a i.b i.c] d])
--