Sequence.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature Sequence
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# Sequence -- ancestor for features that can be converted to a 'list'
#
# Sequences are empty, finite or infinite ordered collections of instances
# of a given type.  Sequences may calculate elements lazily on demand.
#
# Sequence is a 'ref' type, i.e., different sub-features may be assigned
# to a field of type 'Sequence'.
#
# Heirs of Sequence must implement 'as_list'.
#
public Sequence(public T type) ref
  : property.countable,
    property.orderable,
    property.hashable
is


  # equality of two Sequences is true iff both a element-wise equal and have
  # the same `count`.
  #
  # This works as long as one of the Sequences is finite, it will diverge if
  # both are equal and infinite.  A `check` will fail if `debug` is enabled and
  # both `a.finite.is_no` and `b.infinite.is_no`.
  #
  # This is defined only if T : property.equatable, it will result in a compile-time panic
  # if this is not the case.
  #
  public redef fixed type.equality(a, b Sequence T /* NYI: UNDER DEVELOPMENT: Sequence.this causes error */
                                  ) bool
  =>
    check
      debug: !(a.finite.is_no && b.finite.is_no)

    if T : property.equatable
      (a.zip b (=) ? id) && count_order a b .is_equal
    else
      compile_time_panic  # Sequence is not equatable since element type is not


  # A total order for Sequences is defined by element-wise comparison. The first
  # pair of elements that differ define the order.
  #
  # This works as long as one of the Sequences is finite, it will diverge if
  # both are equal and infinite.  A `check` will fail if `debug` is enabled and
  # both `a.finite.is_no` and `b.infinite.is_no`.
  #
  # This is defined only if T : property.orderable, it will result in a compile-time panic
  # if this is not the case.
  #
  public redef fixed type.lteq(a, b Sequence T /* NYI: UNDER DEVELOPMENT: Sequence.this causes error */
                              ) bool
  =>
    check
      debug: !(a.finite.is_no && b.finite.is_no)

    if T : property.orderable
      a.zip b (<>)
       .filter (.is_unequal)
       .first
       .or_else (count_order a b)
       .is_less_or_equal
    else
      compile_time_panic  # Sequence is not orderable since element type is not


  # The total order for Sequences defined only by `i32.lteq` applied to their
  # element count.
  #
  # This works as long as one of the Sequences is finite, it will diverge if
  # both are equal and infinite.  A `check` will fail if `debug` is enabled and
  # both `a.finite.is_no` and `b.infinite.is_no`.
  #
  public type.count_order(a, b Sequence T /* NYI: UNDER DEVELOPMENT: Sequence.this causes error */
                         ) order
  =>
    check
      debug: !(a.finite.is_no && b.finite.is_no)

    l := a.zip b _,_->unit .count
    al := a.drop l .take 1
    bl := b.drop l .take 1
    al.count <> bl.count


  # create hash code for this Sequence
  #
  # This should satisfy the following condition:
  #
  #   (T.equality a b) : (T.hash_code a = T.hash_code b)
  #
  # This will result in a compile-time `panic` in case T : property.hashable does not hold.
  #
  # The algorithm used here is a variation of (XXXHash)[https://xxhash.com] as used in
  # (Python's tuple)[https://github.com/python/cpython/blob/849a80ec412c36bbca5d400a7db5645b8cf54f1f/Objects/tupleobject.c#L305]:
  #
  #   we start with a constant `hash_prime1`
  #   for each value:
  #     we take its hash code * `hash_prime2` and add it
  #     then we rotate by `hash_rotate`
  #     and multiply by `hash_prime3`
  #
  public redef fixed type.hash_code(a Sequence T) u64
  =>
    if T : property.hashable then
      h0 := xxh_next xxh_first 0x9a632220e62c17c8  # created using https://cryptotools.dev/
      a.map (T.hash_code)
       .foldf h0 xxh_next
    else
      compile_time_panic  # Sequence is not hashable since element type is not


  # create a list from this Sequence.
  #
  # A list is immutable, so it can be reused and shared between threads.
  #
  # Heirs must provide an implementation of as_list.
  #
  public as_list list T => abstract


  # is this sequence known to be finite?  For infinite sequences, features like
  # count diverge.
  #
  # trit.yes       = known finite
  # trit.no        = known infinite
  # trit.unknown   = unknown
  #
  public redef finite trit => trit.unknown


  # is this Sequence known to be array backed? If so, this means that operations
  # like index[] are fast.
  #
  public is_array_backed bool => false


  # is this Sequence empty?
  #
  public is_empty bool => as_list.is_empty


  # count the number of elements in this Sequence.  Note that this typically
  # runs forever if executed on an endless Sequence
  #
  # For Sequences that are not array backed, this might require time in O(count).
  #
  public redef count i32
  => (map i32 (_ -> 1)).fold i32.sum


  # count the number of elements in this Sequence that match the
  # given predicate. Note that this typically
  # runs forever if executed on an endless Sequence.
  #
  public count(f T->bool) i32 =>
    (filter f).count


  # get the first element of this Sequence
  #
  public first option T
  => as_list.first


  # get the first element of this Sequence or default if sequence is empty
  #
  public first(default T) T
  =>
    first.or_default default


  # get the last element of this Sequence
  #
  # This may take time in O(count), in particular, it may not terminate
  # for an infinite Sequence.
  #
  public last option T
  => as_list.last


  # get the last element of this Sequence or default if sequence is empty
  #
  public last(default T) T
  =>
    last.or_default default


  # collect the contents of this Sequence into an array
  #
  public as_array array T =>
    if is_array_backed
      array count (i -> Sequence.this[i])
    else
      as_list.as_array


  # create an array backed version of this sequence in case this is not array
  # backed.  This will ensure that operations like index[] or drop perform
  # in constant time.
  #
  # returns Sequence.this if is_array_backed.
  #
  public as_array_backed Sequence T
  post
    debug: result.is_array_backed
  =>
    if is_array_backed
      Sequence.this
    else
      as_array


  # run `f` on each element in this Sequence in order.
  #
  # Note that this makes sense only if `f` has some side-effect, e.g., to print
  # each element, use `s.for_each say`
  #
  public for_each(f T -> unit) unit => as_list.for_each f


  # calls `f` for each element in the Sequence.
  #
  # Unlike `for_each` this returns itself
  # allowing easier composition with
  # other Sequence features.
  #
  # example:
  #
  #     [1,2,3,4,5]
  #       .filter is_prime
  #       .peek say
  #       .drop_while <10
  #
  public peek (f T -> unit) Sequence T
    post
      debug: finite = result.finite
      debug: finite.is_no_or_unknown || count = result.count
  =>
    map x->
      f x
      x


  # apply 'f' to each element 'e' as long as 'f e'
  #
  public for_while(f T -> bool) unit =>
    take_while f
      .for_each _->unit


  # create a new Sequence that contains the first elements of
  # this Sequence for which 'f e' is false
  #
  public before(f T -> bool) Sequence T =>
    take_while (x -> !(f x))


  # filter elements using predicate f
  # values for which f is false are dropped
  #
  public filter   (f T -> bool) Sequence T
    # NYI: BUG: count >= result.count sometimes recursive
    # post
      # NYI: BUG: debug: finite = result.finite
      # NYI: BUG: debug: finite.is_no_or_unknown || count >= result.count
  => as_list.filter f


  # check if predicate f holds for all elements
  #
  public infix ? (f T -> bool) bool => as_list ? f


  # check if predicate f holds for at least one element
  #
  public infix ? (f T -> bool) bool => as_list ? f


  # create a Sequence that consists only of the first n elements of this
  # Sequence, fewer if this Sequence has fewer elements
  #
  # NOTE: for negative n an empty Sequence is returned
  #
  public take (I type : integer, n I) Sequence T
    # NYI: BUG: breaks tail call optimization
    # post debug: n>0 || result.is_empty
  => as_list.take n


  # reverse the order of the elements in this Sequence
  #
  public reverse Sequence T
    pre
      debug: finite.is_yes_or_unknown
    post
      debug: finite = result.finite
      debug: count = result.count
  => as_list.reverse_list


  # create a Sequence that consists of the elements of this Sequence except the first
  # n elements
  #
  # NOTE: this may have performance in O(n) unless it is backed by an immutable array.
  #
  # NOTE: for negative n the Sequence is returned as is
  #
  public drop (I type : integer, n I) Sequence T
    # NYI: BUG: breaks tail call optimization
    # post debug: n>0 || count=result.count
  => as_list.drop n


  # get a function that, given an index, returns the element at that index
  #
  public index [] () integer -> T => n -> Sequence.this[n]


  # create a slice from this Sequence that consists of the elements starting at index
  # from (including) up to index to (excluding).
  #
  public slice(I type : integer, from, to I) Sequence T
    pre
      debug : from ? 0
      debug : to = 0 || (if is_array_backed || debug_level > 1 then is_valid_index to-1 else true)
      debug : from <= to
    # NYI: BUG: postcondition on parametrized feature do not work yet?
    # post
    #   debug: result.finite.is_yes_or_unknown
    #   debug: result.count = (to-from).as_i32
  =>
    drop from
      .take to-from


  # create a tuple of two Sequences by splitting this at
  #
  # either
  #
  #    the given index,
  #    i.e., a Sequence of length 'at' and one of length 'count-at'.
  #    at may be <= 0 or >= count, in which case the resulting tuple will be the
  #    (empty list, Sequence.this.as_list) or (Sequence.this.as_list, empty list), resp.
  #
  # or
  #
  #    at first result of condition function
  #
  public split_at(c i32 | T->bool) tuple (Sequence T) (Sequence T) =>
    match c
      at i32 => ((take at), (drop at))
      cond T->bool =>
        split_at (first_index_of cond)


  # returns the index of the first element
  # where `cond` is true.
  # If never true returns `count`
  #
  # NYI: UNDER DEVELOPMENT: do we want this public?
  #
  first_index_of(F type: T->bool, cond F) i32
  =>
    for i:=0, i+1
        el in Sequence.this
    while !cond el
    else
      i


  # Lazily take the first elements of this Sequence for which predicate 'p' holds.
  #
  public take_while (p T -> bool) Sequence T
    post
      analysis: result ? p
      analysis: {
        n := nth result.count
        !n || !(p n.or_panic)
      }
  => as_list.take_while p


  # Lazily drop the first elements of this Sequence for which predicate 'p' holds.
  #
  public drop_while (p T -> bool) Sequence T
    post
      analysis: result ? (x -> !(p x))
      analysis: {
        n := nth result.count
        !n || p n.or_panic
      }
  => as_list.drop_while p


  # create a Sequence that consists of all the elements of this Sequence followed
  # by all the elements of s
  #
  # General case: This will perform `as_list.concat_list` in case one of
  # `Sequence.this` or `s`is not known to be finite (`finite.is_no_or_unknown`) or
  # `s.count` is larger than `count`.
  #
  # Otherwise, if `Sequence.this` or `s` is empty, the result will be `s` or
  # `Sequence.this`, respectively.
  #
  # In all other cases, an instance of `container.expanding_array` will be
  # created and the elements of `this` and `s` will be added.  Note that
  # `concat` is redefined for `container.expanding_array` to achieve
  # average `O(1)` performance for repeated concatenation with `s.count < c`
  # for some constant `c`.
  #
  # Performance: O(count + s.count) worst case, O(s.count) average case
  #
  # NOTE: For repeated concatenation `a.concat b` that fall into the general
  # case the resulting sequence will have iteration performance in `O(n?)`
  # for `n` concatenation. Explicitly use `container.expanding_array` to
  # avoid this. This implementation cannot do this automatically since
  # repeated wrapping of `a` into an `expanding_array` would result
  # in `O(n?)` performance for the concatenations.
  #
  public concat (s Sequence T) Sequence T =>
    c1 :=   finite.is_yes ? count   : -1
    c2 := s.finite.is_yes ? s.count : -1
    if c1 = 0
      s
                      #
                      # if this sequence is infinite,
                      # no need to concat s
                      #
    else if c2 = 0 || finite.is_no
      Sequence.this

    #
    # if s is infinite we use list concat
    # otherwise we would hang forever
    #
    else if s.finite.is_no
      as_list.concat_list s.as_list
    else
      container.Finger_Tree T .empty
        .concat Sequence.this
        .concat s


  # return this Sequence as a Finger_Tree
  # or nil if Sequence is not (yet) a Finger_Tree
  #
  module as_finger_tree option (container.Finger_Tree T) => nil


  # infix operand synonym for concat
  #
  public infix ++ (s Sequence T) Sequence T => concat s


  # create a Sequence that repeats the current Sequence indefinitely.  In case 'Sequence.this'
  # is empty, returns 'nil'
  #
  public cycle Sequence T
   post debug: result.finite.is_no
  => as_list.cycle


  # create a Sequence that repeats the current Sequence `n` times.
  #
  public infix *(n i32) Sequence T
    pre
      debug: n >= 0
  =>
    if n <= 0 || is_empty then (Sequence T).empty
                          else Sequence.this ++ Sequence.this * (n-1)


  # create a lazy list of all the tails of this Sequence, including the complete Sequence
  # as a list and the empty list 'nil'.
  #
  public tails list (list T) => as_list.tails


  # create a string representation of this Sequence including all the string
  # representations of its contents, separated by ',' and enclosed in '['
  # and ']'.
  #
  # In case this Sequence is known to be `finite` or has at most (Sequence T).type
  # .AS_STRING_NON_FINITE_MAX_ELEMENTS elements, all elements will be shown in the
  # resulting string. Otherwise, only the first elements will be shown followed by
  # ",?" as in "[1,2,3,4,5,6,7,8,9,10,?]".
  #
  # To force printing of all elements of a finite `Sequence` for which `finite` is
  # false (which may be the case since a Sequence in general might not know that it
  # if finite), you may use `as_string_all`.
  #
  public redef as_string String =>
    if finite.is_yes
      as_string_all
    else
      max0 := (Sequence T).AS_STRING_NON_FINITE_MAX_ELEMENTS
      (zip 0..max0 (v,n -> if n < max0 then $v else "?".as_string)).as_string_all


  # create a string representation of this Sequence including all the string
  # representations of its contents, separated by ", " and enclosed in '['
  # and ']'.
  #
  # NOTE: In case this Sequence is not finite, this will attempt to create an
  # infinitely long string resulting in failure due to resource exhaustion.
  #
  public as_string_all String => "[{as_string ", "}]"


  # create a string representation of this Sequence including all the string
  # representations of its contents, separated by 'sep'.
  #
  # NOTE: In case this Sequence is not finite, this will attempt to create an
  # infinitely long string resulting in failure due to resource exhaustion.
  #
  public as_string (sep String) String => as_list.as_string sep


  # call 'as_string' on the elements
  #
  public as_strings Sequence String => map ($)


  # map the Sequence to a new Sequence applying function f to all elements
  #
  # This performs a lazy mapping, f is called only when the elements
  # in the resulting list are accessed.
  #
  public map(B type, f T->B) Sequence B
    # NYI: BUG: count = result.count sometimes recursive
    # post
      # NYI: BUG: debug: finite = result.finite
      # NYI: BUG: debug: finite.is_no_or_unknown || count = result.count
  =>
    as_list.map_to_list f


  # map the Sequence to a new Sequence applying function f to all elements
  #
  # This is an infix operator alias of map enabling piping code like
  #
  #     l := 1..10 | *10 | 300-
  #
  # to obtain 290,280,270,...200
  #
  # Note that map and therefore also this operator is lazy, so
  #
  #     _ := (1..10 | say)
  #
  # will not print anything while
  #
  #     (1..10 | say).for_each _->unit
  #
  # will print the elements since `for_each` is not lazy.
  #
  public infix | (B type, f T->B) Sequence B => map f


  # map each element of this Sequence to Sequence
  # Then flatten the result by one level,
  # essentially combining all the sequences.
  #
  public flat_map(B type, f T -> Sequence B) Sequence B =>
    as_list.flat_map_to_list f


  # Map this Sequence to f applied to neighboring pairs of values
  # in this Sequence.
  #
  # In case this Sequence has less than two elements, the result will
  # be the empty list.
  #
  # ex. to obtain a Sequence of differences, you may use `map_pairs (-)`:
  #
  #     [2,3,5,7,11,13,17,19,23,29].map_pairs a,b->b-a
  #
  # results in `[1,2,2,4,2,4,2,4,6]`
  #
  public map_pairs(B type, f (T,T)->B) Sequence B =>
    zip (drop 1) f


  # fold the elements of this Sequence using the given monoid.
  #
  # e.g., to sum the elements of a Sequence of i32, use s.fold i32.sum
  #
  public fold (m Monoid T) T => as_list.fold m.e m


  # fold the elements of this non-empty Sequence using the given function
  #
  # e.g., to find the minimum of a Sequence of i32, use `s.fold1 (<=)`
  #
  public fold1 (f (T,T)->T) T
  pre
    debug: !is_empty
  =>
    as_list.fold1 f


  # fold the elements of this Sequence using the given function and initial
  # value.
  #
  # In case this Sequence is empty, the result is `e`.
  #
  # e.g., to find the product of a Sequence of i32, use `s.foldf (*) 1`
  #
  public foldf (B type, e B, f (B,T)->B) B
  =>
    as_list.foldf e f


  # fold the elements of this Sequence using the given monoid right-to-left.
  #
  # e.g., to concat the elements of a Sequence `s` of Strings, use `s.foldr String.concat`
  #
  public foldr (m Monoid T) T => as_list.foldr m


  # fold the elements of this Sequence using the given monoid and initial value right-to-left.
  #
  # Used to fold a Sequence tail-recursively
  #
  public foldr (s T, m Monoid T) T => as_list.foldr m.e m


  # fold the elements of this non-empty Sequence using the given function right-to-left
  #
  # e.g., to concat the elements of a non-empty Sequence of Sequeces, use `foldr1 (++)`
  #
  public foldr1 (f (T,T)->T) T => as_list.foldr1 f


  # fold the elements of this Sequence using the given function right-to-left.
  #
  # e.g., to concat the elements of a Sequence of Sequences, use `foldrf [] (++)`
  #
  public foldrf (B type, e B, f (T,B)->B) B => as_list.foldrf e f


  # map this Sequence to a list that contains the result of folding
  # all prefixes using the given monoid.
  #
  # e.g., for a Sequence of i32 s, s.scan i32.sum creates a list of
  # partial sums (0..).map x->(s.take x).fold i32.sum
  #
  public scan (m Monoid T) Sequence T => as_list.scan_list m


  # map this Sequence to a Sequence that contains the result of folding
  # all prefixes using the given function and initial value.
  #
  # e.g., for a Sequence s `[3,8,10]`, `s.scan 0 (+)` creates a Sequence of
  # partial sums `[0, 3, 11, 21]`
  #
  public scan (R type, a R, f (R,T)->R) Sequence R => as_list.scan R a f


  # scan1 works like its counterpart with an initial value, except
  # that the initial value is taken to be the first element of the given
  # Sequence.
  #
  # for example, (1::id).scan (+) would create [1, 2, 3, 4, ...], while
  # (1..).scan (+) would create [1, 3, 6, 10, ...].
  #
  public scan1 (f (T,T)->T) Sequence T => as_list.scan1 f


  # reduce this Sequence to R with an initial value init
  # and a reducing function f.
  # the reduction is finished once f yields abort or
  # if the end of the sequence is reached.
  #
  public reduce(R type, init R, f (R,T) -> R | abort R) R =>
    match as_list
      nil => init
      c Cons =>
        match f init c.head
          a abort => a.val
          r R => c.tail.reduce r f


  # reduce this Sequence to `outcome R`
  # with an initial value `init` and a reducing function `f`.
  # the reduction is finished once `f` yields `abort` or
  # if the end of the sequence is reached.
  #
  public reduce_or_error(R type, init R, f (R,T) -> R | abort (outcome R)) outcome R =>
    match as_list
      nil => init
      c Cons =>
        match f init c.head
          a abort => a.val
          r R => c.tail.reduce_or_error r f


  # insert element v at position at
  #
  public insert(at i32, v T) Sequence T
  pre
    debug: at ? 0
  =>
    take at ++ [v] ++ drop at


  # sort this Sequence using the order defined by less_or_equal
  #
  public sort_by(less_or_equal (T, T) -> bool) container.sorted_array T => container.sorted_array Sequence.this less_or_equal


  # create a new Sequence from the result of applying 'f' to the
  # elements of this Sequence and 'b' in order.
  #
  public zip(U,V type, b Sequence U, f (T,U)->V) Sequence V => as_list.zip b f


  # create a new Sequence from the result of applying 'f' to the
  # elements all combinations of elements of this Sequence and
  # all elements of 'b' iterating of 'b' repeatedly as follows
  #
  #     Sequence.this[0]  , b[0]
  #     Sequence.this[0]  , b[1]
  #     Sequence.this[0]  , b[2]
  #     Sequence.this[0]  , ...
  #     Sequence.this[0]  , b.last
  #     Sequence.this[1]  , b[0]
  #     Sequence.this[1]  , b[1]
  #     Sequence.this[1]  , ...
  #     ...               , ...
  #     Sequence.this.last, b.last
  #
  public combine(U, V type, b Sequence U, f (T,U)->V) Sequence V =>
    flat_map x->
      b.map y->(f x y)


  # create a new Sequence from tuples of all combinations of elements
  # of this Sequence and all elements of 'b' iterating of 'b' repeatedly
  # as follows
  #
  #     (Sequence.this[0]  , b[0]  )
  #     (Sequence.this[0]  , b[1]  )
  #     (Sequence.this[0]  , b[2]  )
  #     (Sequence.this[0]  , ...   )
  #     (Sequence.this[0]  , b.last)
  #     (Sequence.this[1]  , b[0]  )
  #     (Sequence.this[1]  , b[1]  )
  #     (Sequence.this[1]  , ...   )
  #     (...               , ...   )
  #     (Sequence.this.last, b.last)
  #
  public pairs(U type, b Sequence U) Sequence ((T, U)) =>
    combine b tuple


  # takes a transducer xf, a reducer f and an initial value
  # returns the result of applying the reducer xf f to the Sequence
  public transduce(TA,U type, xf transducer TA U T, rf (TA,U) -> TA, init TA) TA =>
    red := xf.call rf
    for
      res := init, red.call res el
      el in Sequence.this do
    else
      res


  # apply transducer to sequence, returning a sequence of results
  #
  # example usage:
  # human(age i32) is
  # ages := map (Sequence i32) human i32 (x -> x.age)
  # gt_ten := filter (Sequence i32) i32 (x -> x > 10)
  # xf := ages ? gt_ten
  # say ([human 4, human 12, human 30].into xf) # [12,30]
  public into(TA type, xf transducer (Sequence TA) TA T) Sequence TA =>
    red := xf.call ((res,val) -> res ++ [val])
    for
      res := (Sequence TA).empty, (red.call res el)
      el in Sequence.this do
    else
      res


  # the nth element in the sequence if it exists, wrapped in an option,
  # nil otherwise.
  #
  # Complexity: if Sequence is array backed O(1) otherwise O(n)
  #
  public nth(n i32) option T
    pre
      debug: n ? 0
  =>
    if is_array_backed
      if (is_valid_index n) then Sequence.this[n] else nil
    else
      (drop n).first


  # check if argument is a valid index in this sequence.
  #
  # Note that this may have a performance in O(i) unless this
  # Sequence is_array_backed.
  #
  public is_valid_index(I type : integer, i I) bool =>
    (0 ? i.as_i32 && (if is_array_backed then i.as_i32 ? count
                                         else !(drop i.as_i32).is_empty))


  # the nth element in the sequence, must exist
  #
  public index [] (I type : integer, i I) T
    pre
      debug: is_valid_index i
  =>
    (nth i.as_i32).or_panic


  # adds the corresponding index to
  # every element in the sequence
  #
  public indexed Sequence (tuple i32 T) =>
    indexed 0


  # adds an index to every element
  # in the sequence starting at start_idx
  #
  public indexed(I type : has_interval, start_idx I) Sequence (tuple I T) =>
    zip (start_idx..) (a,b -> (b, a))


  # chop this Sequence into chunks of `chunk_size`.
  # the last chunk may be smaller than `chunk_size`.
  #
  public chunk(chunk_size i32) Sequence (Sequence T)
  pre debug: chunk_size > 0
  =>
    if is_empty
      (Sequence (Sequence T)).empty
    else
      (take chunk_size) : ((drop chunk_size).chunk chunk_size).as_list


  # chop this Sequence into tuples of size 2.  In case
  # the number of elements is not a multiple of 2,
  # the last count % 2 elements will be dropped silently.
  #
  # ex.
  #
  #     [1,2,3,4,5].tuples produces [(1,2),(3,4)]
  #
  public as_tuples Sequence (T, T)
  =>
    h := take 2
    t := drop 2
    if h.count < 2
      (Sequence (T,T)).empty
    else
      h.as_tuple : t.as_tuples.as_list


  # chop this Sequence into tuples of size 3.  In case
  # the number of elements is not a multiple of 3,
  # the last count % 3 elements will be dropped silently.
  #
  # ex.
  #
  #     [1,2,3,4,5,6,7].tuples3 produces [(1,2,3),(4,5,6)]
  #
  public as_3tuples Sequence (T, T, T)
  =>
    h := take 3
    t := drop 3
    if h.count < 3
      (Sequence (T,T,T)).empty
    else
      h.as_3tuple : t.as_3tuples.as_list


  # chop this Sequence into tuples of size 4.  In case
  # the number of elements is not a multiple of 4,
  # the last count % 4 elements will be dropped silently.
  #
  # ex.
  #
  #     [1,2,3,4,5].tuples4 produces [(1,2,3,4)]
  #
  public as_4tuples Sequence (T, T, T, T)
  =>
    h := take 4
    t := drop 4
    if h.count < 4
      (Sequence (T,T,T,T)).empty
    else
      h.as_4tuple : t.as_4tuples.as_list


  # chop this Sequence into tuples of size 5.  In case
  # the number of elements is not a multiple of 5,
  # the last count % 5 elements will be dropped silently.
  #
  # ex.
  #
  #     [1,2,3,4,5,6].tuples5 produces [(1,2,3,4,5)]
  #
  public as_5tuples Sequence (T, T, T, T, T)
  =>
    h := take 5
    t := drop 5
    if h.count < 5
      (Sequence (T,T,T,T,T)).empty
    else
      h.as_5tuple : t.as_5tuples.as_list


  # chop this Sequence into tuples of size 6.  In case
  # the number of elements is not a multiple of 6,
  # the last count % 6 elements will be dropped silently.
  #
  # ex.
  #
  #     [1,2,3,4,5,6,7].tuples6 produces [(1,2,3,4,5,6)]
  #
  public as_6tuples Sequence (T,T, T, T, T, T)
  =>
    h := take 6
    t := drop 6
    if h.count < 6
      (Sequence (T,T,T,T,T,T)).empty
    else
      h.as_6tuple : t.as_6tuples.as_list


  # convert a Sequence's head into a 2-tuple.
  #
  # ex.
  #
  #     [1,2,3,4,5].as_tuple  produces (1,2)
  #     [1,2].as_tuple        produces (1,2)
  #     [1].as_tuple          breaks the pre condition
  #     [].as_tuple           breaks the pre condition
  #
  public as_tuple() (T, T)
    pre
      debug: take 2 .count = 2
  =>
    match as_list
      c1 Cons =>
        match c1.tail
          c2 Cons => (c1.head, c2.head)
          nil => panic "as_tuple called on single element Sequence"
      nil => panic "as_tuple called on empty Sequence"


  # convert a Sequence's head into a 3-tuple.
  #
  # ex.
  #
  #     [1,2,3,4,5].as_3tuple  produces (1,2,3)
  #     [1,2,3].as_3tuple      produces (1,2,3)
  #     [1,2].as_3tuple        breaks the pre condition
  #     [1].as_3tuple          breaks the pre condition
  #     [].as_3tuple           breaks the pre condition
  #
  public as_3tuple() (T, T, T)
    pre
      debug: take 3 .count = 3
  =>
    r option (T, T, T) := match as_list
                            c1 Cons =>
                              match c1.tail
                                c2 Cons =>
                                  match c2.tail
                                    c3 Cons => (c1.head, c2.head, c3.head)
                                    nil => nil
                                nil => nil
                            nil => nil
    r.or_panic


  # convert a Sequence's head into a 4-tuple.
  #
  # ex.
  #
  #     [1,2,3,4,5].as_4tuple  produces (1,2,3,4)
  #     [1,2,3,4].as_4tuple    produces (1,2,3,4)
  #     [1,2,3].as_4tuple      breaks the pre condition
  #     [1,2].as_4tuple        breaks the pre condition
  #     [1].as_4tuple          breaks the pre condition
  #     [].as_4tuple           breaks the pre condition
  #
  public as_4tuple() (T, T, T, T)
    pre
      debug: take 4 .count = 4
  =>
    r option (T, T, T, T) := match as_list
                               c1 Cons =>
                                 match c1.tail
                                   c2 Cons =>
                                     match c2.tail
                                       c3 Cons =>
                                         match c3.tail
                                           c4 Cons => (c1.head, c2.head, c3.head, c4.head)
                                           nil => nil
                                       nil => nil
                                   nil => nil
                               nil => nil
    r.or_panic


  # convert a Sequence's head into a 5-tuple.
  #
  # ex.
  #
  #     [1,2,3,4,5,6].as_5tuple  produces (1,2,3,4,5)
  #     [1,2,3,4,5].as_5tuple    produces (1,2,3,4,5)
  #     [1,2,3,4].as_5tuple      breaks the pre condition
  #     [1,2,3].as_5tuple        breaks the pre condition
  #      ...
  #     [].as_5tuple             breaks the pre condition
  #
  public as_5tuple() (T, T, T, T, T)
    pre
      debug: take 5 .count = 5
  =>
    r option (T, T, T, T, T) := match as_list
                                  c1 Cons =>
                                    match c1.tail
                                      c2 Cons =>
                                        match c2.tail
                                          c3 Cons =>
                                            match c3.tail
                                              c4 Cons =>
                                                match c4.tail
                                                  c5 Cons => (c1.head, c2.head, c3.head, c4.head, c5.head)
                                                  nil => nil
                                              nil => nil
                                          nil => nil
                                      nil => nil
                                  nil => nil
    r.or_panic


  # convert a Sequence's head into a 6-tuple.
  #
  # ex.
  #
  #     [1,2,3,4,5,6,7].as_6tuple  produces (1,2,3,4,5,6)
  #     [1,2,3,4,5,6].as_6tuple    produces (1,2,3,4,5,6)
  #     [1,2,3,4,5].as_6tuple      breaks the pre condition
  #     [1,2,3,4].as_6tuple        breaks the pre condition
  #      ...
  #     [].as_6tuple               breaks the pre condition
  #
  public as_6tuple() (T, T, T, T, T, T)
    pre
      debug: take 6 .count = 6
  =>
    r option (T, T, T, T, T, T) := match as_list
                                     c1 Cons =>
                                       match c1.tail
                                         c2 Cons =>
                                           match c2.tail
                                             c3 Cons =>
                                               match c3.tail
                                                 c4 Cons =>
                                                   match c4.tail
                                                     c5 Cons =>
                                                       match c5.tail
                                                         c6 Cons => (c1.head, c2.head, c3.head, c4.head, c5.head, c6.head)
                                                         nil => nil
                                                     nil => nil
                                                 nil => nil
                                             nil => nil
                                         nil => nil
                                     nil => nil
    r.or_panic


  # convert this Sequence to an ordered map
  # via mapping all elements to key value pairs
  #
  public as_ordered_map(KEY type : property.orderable,
                        VALUE type,
                        mapper T -> (KEY,VALUE)
                        ) container.ordered_map KEY VALUE
  =>

    keys, values :=
      reduce ((Sequence KEY).empty,(Sequence VALUE).empty) (r,t)->
        mapper t ||> k,v->(r.0++[k],r.1++[v])

    container.ordered_map keys values


  # convert this Sequence to a hash map
  # via mapping all elements to key value pairs
  #
  public as_hash_map(KEY type : property.hashable,
                     VALUE type,
                     mapper T -> (KEY,VALUE)
                     ) container.hash_map KEY VALUE
  =>

    keys, values :=
      reduce ((Sequence KEY).empty,(Sequence VALUE).empty) (r,t)->
        mapper t ||> k,v->(r.0++[k],r.1++[v])

    container.hash_map keys.as_array values.as_array


  # sliding window with step size one
  # blocks of size elements, each is offset by one element to the previous one
  #
  # example:
  # `(0..5).sliding 3`
  # =>  `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`
  #
  public sliding (size i32) Sequence (Sequence T) =>
    sliding size 1


  # sliding window
  # blocks of size elements, each is offset by step elements to the previous one
  #
  # examples:
  # `(0..5).sliding 3 1`
  # =>  `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`
  #
  # `(0..9).sliding 3 2`
  # => `[[0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8]]`
  #
  public sliding (size i32, step i32) Sequence (Sequence T)
    pre
      debug: size > 0
      debug: step > 0
  =>
    as_list.sliding size step


  # group elements using key_f and reduce elements within a group using reduce_f
  # in contrast to the more general version, values in the resulting map must have the same type as in the input
  #
  # example: sum even and odd numbers individually
  #
  #     (0..10).group_reduce String (x -> x%%2 ? "even" : "odd") (+)
  #
  # => {(even => 30), (odd => 25)}
  #
  public group_reduce (
    # type of the keys
    K type : property.orderable,

    # function to generate the key
    key_f T->K,

    # function to reduce the elements
    reduce_f (T,T)->T) container.Map K T
  =>
    group_map_reduce K T key_f id reduce_f


  # group elements using key_f and
  # reduce elements within a group by first applying f and then using reduce_f to reduce
  #
  # example: count occurrences of letters, numbers and other characters
  #
  #     values array codepoint := ["A", "1", "b", "?", "X", "4"]
  #
  #     classify (c codepoint) String => c.is_ascii_letter ? "letter" : c.is_ascii_digit ? "digit" : "other"
  #
  #     values.group_map_reduce String i32 classify (_->1) (+)
  #
  # => {(digit => 2), (letter => 3), (other => 1)}
  #
  public group_map_reduce (
    # type of the keys
    K type : property.orderable,

    # type of the values in the result
    B type,

    # function to generate the keys
    key_f T->K,

    # function applied to elements before they are reduce
    f T->B,

    # function to reduce elements
    reduce_f (B,B)->B) container.Map K B
  =>
    lm : mutate is
    lm ! ()->
      res := (container.mutable_tree_map lm K B).empty

      for_each x->
        key := key_f x
        match res[key]
          nil => res.put key (f x)
          y B => res.put key (reduce_f y (f x))

      res.as_map


  # group the elements of this sequence by a key of type and applies function f to all elements
  #
  # example: group characters by category and add underscores around each character
  #
  #     values array codepoint := ["A", "1", "b", "?", "X", "4"]
  #
  #     classify (c codepoint) String => c.is_ascii_letter ? "letter" : c.is_ascii_digit ? "digit" : "other"
  #
  #     values.group_map String String classify (x->"_{x}_")
  #
  # => {(digit => [_1_, _4_]), (letter => [_A_, _b_, _X_]), (other => [_?_])}
  #
  public group_map (
    # type of the keys
    K type : property.orderable,

    # type of the values in the result
    B type,

    # function to generate the keys
    key_f T->K,

    # function applied to each element
    f T->B) container.Map K (Sequence B)
  =>
    lm : mutate is
    lm ! ()->
      res := (container.mutable_tree_map lm K (Sequence B)).empty

      for_each x->
        key := key_f x
        match res[key]
          nil => res.put key [(f x)]
          y Sequence => res.put key (y ++  [(f x)])

      res.as_map


  # group the elements of this sequence by a key of type K
  # using a custom Mutable_Map
  #
  # f determines the key of an element
  #
  public group_by_mutable_map(K type : property.equatable, M type : container.Mutable_Map K (Sequence T), f T -> K) container.Map K (Sequence T)
  =>
    res := M.empty

    for_each x->
      key := f x
      match res[key]
        nil => res.put key [x]
        s Sequence => res.put key s++[x]

    res.as_map


  # group the elements of this sequence by a key of type K
  # using a mutable_tree_map
  #
  # f determines the key of an element
  #
  public group_by(K type : property.orderable, f T -> K) container.Map K (Sequence T) =>
    lm : mutate is
    lm ! ()->
      group_by_mutable_map K (container.mutable_tree_map lm K (Sequence T)) f


  /* NYI: UNDER DEVELOPMENT: impl. restriction: Incompatible type parameter
  # group the elements of this sequence
  #
  public group(M type : container.Mutable_Map T (Sequence T)) container.Map T (Sequence T)
    pre T : property.equatable
  =>
    group_by T M id
  */




  # create an empty Sequence
  #
  public fixed type.empty Sequence T
    post
      result.finite.is_yes_or_unknown
      result.count = 0
  =>
    []


  # monoid of Sequences with infix concatenation operation.
  #
  public type.concat_monoid Monoid (Sequence T) =>

    _ : Monoid (Sequence T) is

      # associative operation
      #
      public redef infix ? (a, b Sequence T) Sequence T => a.concat b

      # identity element
      #
      public redef e Sequence T =>
        []


  # Maximum number of elements shown for on a call to `as_string` for a non-finite
  # Sequence.
  #
  public type.AS_STRING_NON_FINITE_MAX_ELEMENTS i32 => 10



# helper features for knuth morris pratt algorithm
#
# NYI: UNDER DEVELOPMENT: move to Sequence/equatable once we can do universe.find_lm
module find_lm : mutate is
module Node(T type, module top Sequence T, module next once find_lm (option (Node T)), module rest option (Node T)) ref is