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' or a
# 'stream'
#
# 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 either 'as_list' or 'as_stream'.  Failure
# to implement any of these results in an endless recursion when the Sequence
# is used.
#
public Sequence(T type) ref is


  # create a list from this Sequence.
  #
  # A list is immutable, so it can be reused and shared between threads.
  # Compared to a stream, a list may require more (heap) allocation.
  #
  # Default implementation uses as_stream. Heirs must redefine at least
  # one of as_list or as_stream.
  #
  public as_list list T is as_stream.as_list


  # create a stream of T.
  #
  # A stream contains mutable state, so it cannot be reused or shared
  # between threads.
  #
  # Default implementation uses as_list.  Heirs must redefine at least
  # one of as_list or as_stream.
  #
  public as_stream stream T is as_list.as_stream


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


  # count the number of elements in this Sequence.  Note that this typically
  # runs forever if executed on an endless list
  #
  public count
  pre
    analysis: finite  # in practice, we do not always have this information
  => (map_sequence i32 (_ -> 1)).fold i32.type.sum


  # get the first element of this Sequence
  #
  # Sequence must not be empty, causes precondition failure if debug is enabled.
  #
  public first
  pre
    debug: !is_empty
  => as_list.head.get


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


  # get the last element of this Sequence
  #
  # Sequence must not be empty, causes precondition failure if debug is enabled.
  #
  # This may take time in O(count), in particular, it may not terminate
  # for an infinite Sequence.
  #
  public last
  pre
    debug: !is_empty
  => as_list.last


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


  # collect the contents of this Sequence into an array
  #
  public as_array array T is
    s := as_stream
    array T count i->s.next


  # create a list and call 'for_each f' on it
  #
  public for_each(f T -> unit) unit is as_list.for_each f


  # create a list and have it consumed by f, infix operator synonym of for_each.
  #
  public infix | (f T -> unit) => for_each f


  # create a stream, postfix operator synonym for as_stream
  #
  public postfix | => as_stream


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


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


  # filter elements using predicate f
  # values for which f is false are dropped
  #
  public filter   (f T -> bool) list T is as_list.filter f


  # filter elements using predicate f, infix operator
  # synonym of filter.
  #
  public infix |& (f T -> bool) => filter f


  # filter elements using predicate f, infix operator
  # synonym of filter.
  #
  # NYI: What is better, 'infix |&' or 'infix &', or something else?
  #
  public infix & (f T -> bool) => filter f


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


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


  # create a list that consists only of the first n elements of this
  # Sequence, fewer if this Sequence has fewer elements
  #
  public take (n i32) => as_list.take n


  # create a list that consists of the elements of this Sequence except the first
  # n elements
  #
  public drop (n i32) => as_list.drop n


  # get a function that, given an index, returns the element at that index
  #
  public index [] () i32 -> T is 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(from, to i32) Sequence T is
    drop(from).take to-from


  # create a tuple of two Sequences by splitting this at 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.
  #
  public split_at(at i32) => ((take at), (drop at))

  # Lazily take the first elements of this Sequence for which predicate 'p' holds.
  #
  public take_while (p T -> bool) => as_list.take_while p


  # Lazily drop the first elements of this Sequence for which predicate 'p' holds.
  #
  public drop_while (p T -> bool) => as_list.drop_while p


  # create a Sequence that consists of all the elements of this Sequence followed
  # by all the elements of s
  #
  public concat_sequences (s Sequence T) list T is as_list.concat s.as_list


  # infix operand synonym for concat_sequences
  #
  public infix ++ (s Sequence T) => as_list ++ s.as_list


  # create a list that repeats the current Sequence indefinitely.  In case 'Sequence.this'
  # is empty, returns 'nil'
  #
  public cycle list T is as_list.cycle


  # 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) is as_list.tails


  # create a string representation of this Sequence including all the string
  # representations of its contents, separated by ',' and enclosed in '['
  # and ']'.
  #
  public redef as_string => as_list.as_string


  # create a string representation of this Sequence including all the string
  # representations of its contents, separated by 'sep'.
  #
  public as_string (sep String) => as_list.as_string sep


  # call 'as_string' on the elements
  #
  public as_strings => map_sequence c->c.as_string


  # map the Sequence to a new list applying function f to all elements
  #
  # This performs a lazy mapping, f is called only when the elements
  # in the resulting list are accessed.
  #
  # NYI: As long as covariance for result type is not permitted we cannot
  # call this 'map' since this would clash with, e.g., 'array.map'
  #
  public map_sequence(B type, f T -> B) => as_list.map f


  # NYI "error 1: Cannot redefine feature with generic arguments
  #      To solve this, ask the Fuzion team to remove this restriction :-)"
  #
  # flat_map(B type, f T -> Sequence B) =>
  #   as_list.flat_map f
  public flat_map_sequence(B type, f T -> Sequence B) =>
    as_list.flat_map 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) => as_list.fold m.e m


  # 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 is
    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 is
    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)
  pre
    debug: at ≥ 0
  =>
    take at ++ [v] ++ drop at


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


  # sort this Sequence using total order defined for 'f a[i]'
  public sort_by(O type : property.orderable, f T->O) => sort (a, b -> f a ≤ f b)


  # create a new list 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) => as_list.zip0 b.as_list f


  # 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 is
    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) list TA is
    red := xf.call ((res,val) -> res ++ [val])
    for
      res (list TA) := (list TA).type.empty , (red.call res el).as_list
      el in Sequence.this do
    else
      res


  # the nth element in the sequence if it exists, wrapped in an option,
  # nil otherwise.
  #
  public nth(n i32) option T
    pre
      debug: n ≥ 0
  is
    match drop n
      nil => nil
      c Cons => c.head


  # is this sequence known to be finite?  For infinite sequences, features like
  # count diverge.
  #
  public finite => false


  # the nth element in the sequence, must exist
  #
  public index [] (i i32) T
    pre
      debug: 0 ≤ i,
      debug: finite: i < count,
      debug: !finite: !(drop i-1).is_empty
  is
    (nth i).get


  # adds the corresponding index to
  # every element in the sequence
  #
  public indexed list (tuple i32 T) is
    indexed 0


  # adds an index to every element
  # in the sequence starting at start_idx
  #
  public indexed(I type : has_interval, start_idx I) list (tuple I T) is
    # NYI: This should work without the type hints again.
    zip I (tuple I T) (start_idx..) (a,b -> (b, a))



  # group the elements of this sequence by a key of type K
  #
  # f determines the key of an element
  #
  public group_by(K type : property.hashable, f T -> K) container.Map K (list T) is
    # NYI It should be possible to choose the map implementation that is used.
    res := (container.ctrie K (list T)).type.empty
    for_each (x ->
      key := f x
      match res[key]
        nil => res.add key [x].as_list
        s list T => res.add key (s ++ [x].as_list)
      )
    res



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



  # monoid of Sequences with infix concatentation operation.
  #
  public type.concat_monoid : Monoid (Sequence T) is

    # associative operation
    #
    infix ∙ (a, b Sequence T) Sequence T is a.concat_sequences b

    # identity element
    #
    e Sequence T is
      (list T).type.empty