list.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 list
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# list -- feature used to define lists
#
# list provides an abstract type for a sequence of elements of the same type.
#
# A list sequence may be empty and contain no element, or it may have a fixed
# or even an infinite number of elements.
#
# The core of the implementation of an actual list lies in the implementation
# of the actual Cons cell a non-empty list consists of.
#
# Lists can typically be traversed using only immutable data. This makes them
# more flexible than streams that require to store and update their state.
#
# A list is immutable, so it can be reused and shared between threads.
# Due to the nature of lists, in which many Cons cells are used, a list
# may require more (heap) allocation than an array.
#
#
#
public list(public A type)
  : choice nil (Cons A (list A)),
    Sequence A
is

  # equality of two list is true iff `a` and `b` are both empty or `a` and `b` are both
  # non-empty and `T` and T.equality a.or_panic b.or_panic.
  #
  # 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 list A) bool
  =>
    (a.head = b.head                 &&
     (a.is_empty || a.tail = b.tail)    )


  # A total order for lists is defined as follows: An empty list `nil` is always
  # less-than-or-equal any other value and iff `a` and `b` are both non-empty, and the
  # `a.head` and `b.head` differ, then `T.lteq a.head b.head`, otherwise `T.lteq a.tail b.tail`.
  #
  # 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 list A) bool
  =>
    a.head <= b.head && (a.head <  b.head   ||
                         lteq a.tail b.tail  # a.tail <= b.tail currently does not result in tail recursion optimization
                        )


  # create hash code for this list.
  #
  # 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 list A) u64
  =>
    if A : property.hashable then
      h0 := xxh_next xxh_first 0xf9284f0baf063243  # created using https://cryptotools.dev/
      a.map A.hash_code
       .foldf h0 xxh_next
    else
      compile_time_panic  # list is not hashable since element type is not


  # Return this list as a list.
  #
  # This is a helper function that needs to be defined because list is an heir
  # of Sequence.
  #
  public redef as_list list A => list.this


  # 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 =>
    list.this ? nil    => trit.yes
              | c Cons => c.finite


  # is this list empty?
  #
  public redef is_empty bool =>
    list.this ? nil  => true
              | Cons => false


  # count the elements of this list
  #
  public redef count i32 => count_n 0


  # count the elements of this list starting at n.
  # carries n around to make this tail-recursive
  #
  count_n (n i32) i32 =>
    list.this ? nil    => n
              | c Cons => c.tail.count_n n+1


  # get the head of this list if it exists, nil if it does
  # not exist
  #
  public head option A
  =>
    list.this ? nil    => nil
              | c Cons => c.head


  # get the tail of this list if it exists, nil if it does
  # not exist or it is the empty list
  #
  public tail list A
  =>
    list.this ? nil    => nil
              | c Cons => c.tail


  # call f in order on all elements of this list
  #
  public redef for_each (f A -> unit) unit =>
    list.this ? nil    =>
              | c Cons => f c.head; c.tail.for_each f


  # get the tail of this list
  #
  # list must not be empty, causes precondition failure if debug is enabled.
  #
  force_tail
  pre
    debug: !is_empty
  =>
    list.this ? nil    => fuzion.std.panic "list.force_tail called on empty list"
              | c Cons => c.tail


  # get the head of this list
  #
  public redef first option A
  =>
    head


  # returns the list of all but the last element of this list
  #
  # list must not be empty, causes precondition failure if debug is enabled.
  #
  public init list A
    pre
      debug: !is_empty
  =>
    init nil


  # returns the list of all but the last element of this list
  #
  # list must not be empty, causes precondition failure if debug is enabled.
  #
  # helper feature for init to allow for tail recursion
  #
  init(res list A) list A
    pre
      debug: !is_empty
  =>
    list.this ? nil => fuzion.std.panic "list.init called on empty list"
              | c Cons =>
                c.tail ? nil => res
                       | Cons => c.tail.init (res.concat_list [c.head].as_list)


  # get the last element of this list
  #
  # This may take time in O(count), in particular, it may not terminate
  # for an infinite list.
  #
  public redef last option A =>
    tail ? nil    => head
         | Cons   => tail.last


  # collect the contents of this list into an array
  #
  public redef as_array array A =>
    (
      reduce (container.expanding_array A .empty) r,t->
        r.add t
    ).as_array


  # map the list to a new list applying function f to all elements
  #
  # This performs a lazy mapping, f is called only when the elements
  # are taken from the list.
  #
  public map_to_list(B type, f A -> B) list B =>
    match list.this
      nil    => nil
      c Cons =>
        (list B).of (f c.head) (c.tail.map_to_list f) c.finite


  # map the list to a new list applying function f to all elements
  # and flatten the result of f in the process
  #
  # This performs a lazy mapping, f is called only when the elements
  # are taken from the list.
  #
  public flat_map_to_list(B type, f A -> Sequence B) list B =>
    match list.this
      nil    => nil
      c Cons =>
        match (f c.head).as_list
          nil     => c.tail.flat_map_to_list f
          c2 Cons =>
            c2.head : c2.tail.concat_list (c.tail.flat_map_to_list f)


  # fold the elements of this list using the given monoid.
  #
  # e.g., to sum the elements of a list of i32, use l.fold i32.sum
  #
  public redef fold (m Monoid A) A => fold m.e m


  # fold the elements of this list using the given monoid and initial value
  #
  # Used to fold a list tail-recursively
  #
  public fold (s A, m Monoid A) A =>
    list.this ? nil    => s
              | c Cons => c.tail.fold (m.op s c.head) m


  # fold the elements of this non-empty list using the given function
  #
  # e.g., to find the minimum of a list of i32, use `l.fold1 (<=)`
  #
  public redef fold1 (f (A,A)->A) A =>
    list.this ? nil    => panic "list.fold1 called on empty list"
              | c Cons => c.tail.foldf c.head f


  # fold the elements of this list using the given function
  #
  # e.g., to find the product of a list of i32, use `s.foldf (*) 1`
  #
  public redef foldf (B type, e B, f (B,A)->B) B =>
    list.this ? nil    => e
              | c Cons => c.tail.foldf (f e c.head) f


  # fold the elements of this list using the given monoid right-to-left.
  #
  # e.g., to concat the elements of a list of String, use l.foldr String.concat
  #
  public redef foldr (m Monoid A) A => foldr m.e m


  # fold the elements of this list using the given monoid and initial value right-to-left.
  #
  # Used to fold a list tail-recursively
  #
  public redef foldr (s A, m Monoid A) A =>
    list.this ? nil    => s
              | c Cons => m.op c.head (c.tail.foldr s m)


  # fold the elements of this non-empty list using the given function right-to-left
  #
  # e.g., to concat the elements of a non-empty list of lists, use foldr1 (++)
  #
  public redef foldr1 (f (A,A)->A) A =>
    list.this ? nil    => panic "list.fold1 called on empty list"
              | c Cons => f c.head (c.tail.foldr1 f)


  # fold the elements of this list using the given function right-to-left.
  #
  # e.g., to concat the elements of a list of lists, use foldrf (++) []
  #
  public redef foldrf (B type, e B, f (A,B)->B) B =>
    list.this ? nil    => e
              | c Cons => f c.head (c.tail.foldrf e f)


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


  # map this list to a list that contains the result of folding
  # all prefixes using the given monoid and initial value
  #
  # Used to scan a list lazily
  #
  public scan_list (s A, m Monoid A) list A =>
    list.this ? nil    => nil
              | c Cons => acc := m.op s c.head
                          list acc (c.tail.scan_list acc m)


  # map this list to a list that contains the result of folding
  # all prefixes using the given function and initial value.
  #
  # e.g., for a list s of i32, s.scan (+) 0 creates a list of
  # partial sums (0..).map x->(s.take x).fold i32.sum
  #
  public redef scan (T type, a T, f (T,A)->T) Sequence T =>
    match head
      nil => a : nil
      x A => (a : (tail.scan T (f a x) f).as_list)


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


  # Lazily take the first n elements of a list, alternatively the whole list if it
  # is shorter than n, or the empty list if n <= 0
  #
  public redef take (I type : integer, n I) Sequence A
  =>
    take_list n.as_i32


  # Lazily take the first n elements of a list, alternatively the whole list if it
  # is shorter than n, or the empty list if n <= 0
  #
  take_list (n i32) list A
  =>
    if n ? 0
      nil
    else
      match list.this
        nil    => nil
        c Cons =>
          c.head : if n = 1 then nil else c.tail.take_list n-1


  # reverse the order of the elements in this list
  #
  public reverse_list list A =>
    reverse nil


  # recursively reverse the order of the elements in this list
  # and append the already reversed reversed_head
  #
  reverse (reversed_head list A) list A =>
    match list.this
      nil => reversed_head
      c Cons =>
        c.tail.reverse (
          _ : Cons A (list A) is
            public redef head A => c.head
            public redef tail list A => reversed_head
            public redef finite trit => list.this.finite)


  # create a string representation of this list including all the string
  # representations of its contents, separated by 'sep'.
  #
  public redef as_string (sep String) String =>
    String.join (map ($)) sep


  # add an element sep in front of every element of this list.
  #
  public prepend_to_all(sep A) list A =>
    prepend_to_all sep nil


  # add an element sep in front of every element of this list, helper to
  # allow tail recursion.
  #
  # if this list is the empty list, return the given result list res, recursively
  # call this feature on the tail of this list otherwise, feeding it with the
  # same separator sep but appending sep and the current element to res.
  #
  prepend_to_all(sep A, res list A) list A =>
    match head
      nil => res
      x A => tail.prepend_to_all sep (res.concat_list [sep, x].as_list)


  # add an element sep between every element of this list.
  #
  public intersperse(sep A) list A =>
    match head
      nil => nil
      x A => x : (tail.prepend_to_all sep)


  # List concatenation, O(count)
  #
  public concat_eagerly (t list A) list A =>
    list.this ? nil    => t
              | c Cons => cons A (list A) c.head (c.tail.concat_eagerly t)


  # Lazy list concatenation, O(1)
  # t is evaluated only when this list is exhausted
  #
  # This is useful when doing buffered reading from an input
  # source and the next buffer chunk, the tail should only
  # be created when actually necessary.
  #
  public concat_list (t Lazy (list A)) list A =>
    match list.this
      nil    => t()
      c Cons =>
        # tricky, Lazy wrapping a Lazy.
        # The expression following the colon
        # is a Lazy and t is also a Lazy.
        c.head : c.tail.concat_list t


  # check if predicate f holds for all elements
  #
  public redef infix ? (f A -> bool) bool =>
    match list.this
      c Cons => f c.head && (c.tail ? f)
      nil    => true



  # check if predicate f holds for at least one element
  #
  public redef infix ? (f A -> bool) bool =>
    match list.this
      c Cons => f c.head || (c.tail ? f)
      nil    => false



  # create a list from the tail of list.this dropping n elements (or fewer
  # if the list is shorter than n).
  #
  public redef drop (I type : integer, n I) Sequence A =>
    drop_list n.as_i32


  # create a list from the tail of list.this dropping n elements (or fewer
  # if the list is shorter than n).
  #
  drop_list (n i32) list A =>
    if n ? 0
      list.this
    else
      list.this ? nil    => nil
                | c Cons => c.tail.drop_list n-1


  # Lazily take the first elements of a list for which predicate 'p' holds.
  #
  public redef take_while (p A -> bool) Sequence A
  =>
    take_while_list p


  # Lazily take the first elements of a list for which predicate 'p' holds.
  #
  take_while_list (F type : A -> bool, p F) list A
  =>
    match list.this
      nil    => nil
      c Cons =>
        if p c.head
          c.head : c.tail.take_while_list p
        else
          nil


  # Lazily drop the first elements of a list for which predicate 'p' holds.
  #
  public redef drop_while (p A -> bool) Sequence A
  =>
    drop_while_list p


  # Lazily drop the first elements of a list for which predicate 'p' holds.
  #
  drop_while_list (F type : A -> bool, p F) list A =>
    match list.this
      nil    => nil
      c Cons =>
        if p c.head
          c.tail.drop_while_list p
        else
          c


  # Lazily filter the elements of a list.
  #
  # The result contains exactly those elements for which p
  # is true.
  #
  public redef filter (p A -> bool) Sequence A =>
    filter_list p


  # Lazily filter the elements of a list.
  #
  # The result contains exactly those elements for which p
  # is true.
  #
  filter_list (F type : A -> bool, p F) list A =>
    match drop_while_list (a -> !(p a))
      nil    => nil
      c Cons =>
        c.head : c.tail.filter_list p


  # create a list that repeats the current list indefinitely.  In case 'list.this'
  # is 'nil', returns 'nil'
  #
  public redef cycle Sequence A =>
    _ : Sequence A is
      public redef finite trit => trit.no
      public redef as_list list A => cycle_list


  # create a list that repeats the current list indefinitely.  In case 'list.this'
  # is 'nil', returns 'nil'
  #
  cycle_list list A =>
    match list.this
      nil    => nil
      c Cons =>
        cycle_cons (h Cons A (list A)) : Cons A (list A) is
          public redef head A => h.head
          public redef tail list A =>
            cycle_cons (h.tail ? nil    => c
                               | d Cons => d)
          public redef finite trit => trit.no
        cycle_cons c


  # create a lazy list of all the tails of this list, including the complete list
  # 'list.this' and the empty list 'nil'.
  #
  public redef tails list (list A) =>
    lazy_value => (list.this ? nil => nil | c Cons => c.tail.tails)
    list
      (list A)
      list.this
      lazy_value


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


  # create a new list from the result of applying 'f' to the
  # elements of this list and 'b' in order.
  #
  zip_list(U, V type, b Sequence U, f (A,U)->V) list V =>
    match list.this
      c1 Cons =>
        b.as_list ? c2 Cons =>
                      f c1.head c2.head : c1.tail.zip_list c2.tail f
                  | nil    => nil
      nil => nil


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


  # filter out consecutive duplicate elements and return result as a list.
  #
  # Keep the order of elements unchanged.
  #
  # ex.
  #
  #     [1,2,2,3,2,2,2,4].dedup_list = [1,2,3,2,4]
  #
  public dedup_list list A
    pre
      A : property.equatable
    =>
      match list.this
        nil    => nil
        c Cons => c.head : c.tail.drop_while_list (=c.head) .dedup_list


  # filter out consecutive duplicate elements using the
  # given relation and return result as a list.
  #
  # Keep the order of elements unchanged.
  #
  # ex.
  #
  #     [4,2,2,6,2,1,2,4].dedup_list (a,b -> a%2=b%2) = [4,1,2]
  #     [4,2,2,6,2,1,2,4].dedup_list (<=) = [4,2,1]
  #
  public dedup_list(F type : (A,A) -> bool, by F) list A
    pre
      A : property.equatable
    =>
      match list.this
        nil    => nil
        c Cons => c.head : c.tail.drop_while_list (x -> by c.head x) .dedup_list by


  # filter out duplicate elements and return result as a list.
  #
  # Keep the order of elements unchanged.
  #
  # Other languages call this 'distinct', e.g. Java, C# or Kotlin
  #
  # ex.
  #
  #     [4,1,2,2,3,2,2,2,4].unique_list = [4, 1, 2, 3]
  #
  public unique_list list A
    pre
      A : property.orderable
  =>
    unique_list2(l list A, existing container.Set A) list A =>
      match l
        nil    => nil
        c Cons => if existing.contains c.head then          unique_list2 c.tail  existing
                  else                             c.head : unique_list2 c.tail (existing.add c.head)
    unique_list2 list.this (container.ps_set A).empty



  # sliding window
  # blocks of size elements, each is offset by step elements to the previous one
  #
  # examples:
  # `(0..5).as_list.sliding 3`
  # =>  `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`
  #
  # `(0..9).as_list.sliding 3 2`
  # => `[[0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8]]`
  #
  public redef sliding (size i32, step i32) Sequence (Sequence A) =>
    window := take size
    if window.count = size
      window : (drop step).sliding size step .as_list
    else
      Sequence (Sequence A) .empty


  # create an empty list
  #
  public fixed type.empty list A =>
    nil


  # fmap lifts a function from A to B to a function from list A to list B
  #
  public type.fmap(B type, f A -> B) list A -> list B =>
    (.map_to_list B f)


  # monoid of lists with infix concatenation operation.
  #
  # NYI: Name should be `concat_monoid`, we use `list_concat_monoid`
  # to avoid clash with inherited `Sequence.concat_monoid`. Maybe
  # the inherited one should be renamed once renaming is supported.
  #
  public type.list_concat_monoid Monoid (list A) =>

    _ : Monoid (list A) is

      # associative operation
      #
      public redef infix ? (a, b list A) list A => a.concat_list b

      # identity element
      #
      public redef e list A =>
        nil


  # convenience routine to create a list from head h and lazy tail t.
  #
  # where f denotes if the list is finite:
  #
  # trit.yes       = known finite
  # trit.no        = known infinite
  # trit.unknown   = unknown
  #
  public type.of(h T, t Lazy (list T), f trit) list T =>
    _ : Cons T (list T) is
      public redef head T => h
      public redef tail list T => t
      public redef finite trit => f


  # convenience routine to create a known finite list from head h and lazy tail t.
  #
  public type.of_finite(h T, t Lazy (list T)) list T =>
    of h t trit.yes


  # convenience routine to create a known infinite list from head h and lazy tail t.
  #
  public type.of_infinite(h T, t Lazy (list T)) list T =>
    of h t trit.no



# convenience routine to create a list from head h and lazy tail t.
#
public list(T type, h T, t Lazy (list T)) list T =>
  (list T).of h t trit.unknown



# infix operator to create a list from head h and lazy tail t.
#
# This is convenient to append an element before a list as in
#
#     0 : [1,2,3,4].as_list
#
# or
#
#     0 : 1 : 2 : 3 : 4 : nil
#
# or to create lists by recursion, e.g., an endless list containing
# integer 1 repeatedly can be created as follows
#
#     ones => 1 : ones
#
public infix_right : (A type, h A, t Lazy (list A)) list A =>
  (list A).of h t trit.unknown


# infix operator to create a list from head h and a production
# function f
#
# This can be used, e.g., as follows:
#
# Ex1: the identity can be used to repeat the same element
#
#     1 :: x->x
#
# will create 1,1,1,1,...
#
# Ex2: To create a list of all integers, use
#
#     0 :: +1
#
# which will produce 0,1,2,3,4,5,...
#
# Ex3: The call
#
#     1 :: p->p+p
#
# will produce the powers of two: 1,2,4,8,16,32,...
#
public infix :: (A type, h A, f A->A) list A =>
  list h (f h :: f)