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.
# Compared to a stream, a list may require more (heap) allocation.
#
#
#
public list(public A type) : choice nil (Cons A (list A)), Sequence A is
# NYI: #530 (review comment): The following should work but causes an error:
# list(A type) : nil | Cons A (list A), Sequence A is


  # 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.this


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


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


  # count the elements of this list starting at n.
  # carries n around to make this tail-recursive
  #
  private count (n i32) i32 =>
    list.this ? nil    => n
              | c Cons => c.tail.count 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
  #
  # list must not be empty, causes precondition failure if debug is enabled.
  #
  public redef first
  pre
    debug: !is_empty
  => head.get


  # 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
  #
  private 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 ++ [c.head])


  # get the last element of this list
  #
  # list 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 list.
  #
  public redef last A
    pre
      debug: !is_empty
  =>
    force_tail ? nil    => first
               | c Cons => force_tail.last


  # collect the contents of this list into an array
  #
  public redef as_array array A =>
    lm : mutate is
      redef mpanic(msg String) => fuzion.std.panic msg
    lm.go ()->
      e := lm.env.new list.this
      array A count _->
        res := e.get.first
        e <- e.get.force_tail
        res


  # 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 =>
        ref : Cons B (list B)
        // Cons B (list B) with    # NYI: better syntax for anonymous feature
          head => f c.head
          tail => c.tail.map_to_list f


  # 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 B f
          c2 Cons =>
            ref : Cons B (list B)
            // Cons B (list B) with    # NYI: better syntax for anonymous feature
              head => c2.head
              tail => c2.tail ++ c.tail.flat_map_to_list B 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) => 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
  pre
    debug: !is_empty
  => (list.this ? nil    => panic "list.fold1 called on empty list"
                | c Cons => c.tail.foldf f c.head)


  # 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`
  #
  # NYI: #2319: rename as `foldf` as soon as redefinition of feature with
  # type parameters works
  #
  public foldf_list (B type, f (B,A)->B, e B) B
  =>  (list.this ? nil    => e
                 | c Cons => c.tail.foldf f (f e c.head))



  # 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 redef scan (m Monoid A) => scan m.e m


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


  # 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 (n i32) list A
  =>
    if n ≤ 0
      nil
    else
      match list.this
        _ nil  => nil
        c Cons =>
          ref : Cons A (list A)   # NYI: indentation syntax for anonymous not supported
            redef head => c.head
            redef tail => if n = 1 then nil else c.tail.take 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 =>
    list.this ? nil    => reversed_head
              | c Cons => c.tail.reverse (cons c.head reversed_head)


  # 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.join (map String x->x.as_string) 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.
  #
  private prepend_to_all(sep A, res list A) list A =>
    match head
      nil => res
      x A => tail.prepend_to_all sep (res ++ [sep, x])


  # 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 (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 t


  # infix operand synonym for concat
  #
  public redef infix ++ (t Sequence A) => concat t.as_list



  # 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 (n i32) list A =>
    if n ≤ 0
      list.this
    else
      list.this ? nil    => nil
                | c Cons => c.tail.drop n-1


  # Lazily take the first elements of a list for which predicate 'p' holds.
  #
  public redef take_while (p A -> bool) list A
  =>
    match list.this
      _ nil  => nil
      c Cons =>
        if p c.head
          ref : Cons A (list A)   # NYI: indentation syntax for anonymous not supported
            redef head => c.head
            redef tail => c.tail.take_while p
        else
          nil


  # Lazily drop the first elements of a list for which predicate 'p' holds.
  #
  public redef drop_while (p A -> bool) list A
  =>
    match list.this
      _ nil  => nil
      c Cons =>
        if p c.head
          c.tail.drop_while 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) list A =>
    filter0 p


  private filter0 (p A -> bool) list A =>
    match drop_while (a -> !(p a))
      _ nil  => nil
      c Cons => ref : Cons A (list A)   # NYI: indentation syntax for anonymous not supported
                  redef head => c.head
                  redef tail => c.tail.filter0 p


  # create a list that repeats the current list indefinitely.  In case 'list.this'
  # is 'nil', returns 'nil'
  #
  public redef cycle list A =>
    match list.this
      nil    => nil
      c Cons =>
        cycle_cons (h Cons A (list A)) : Cons A (list A) is
          head => h.head
          tail list A =>
            cycle_cons (h.tail ? nil    => c
                               | d Cons => d)
        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) =>
    ref : Cons (list A) (list (list A))
      head => list.this
      tail => (list.this ? nil    => nil
                         | c Cons => c.tail.tails)

  # create stream from this list
  #
  # In contrast to list's immutable Cons cells, a stream instance is mutable, i.e,
  # it cannot be shared with threads or used in pure functions
  #
  public redef as_stream ref : stream A is
    cur := list.this
    public redef has_next => (cur ? Cons => true
                                  | nil  => false)
    public redef next =>
      res := cur.head.get
      set cur := cur.force_tail
      res


  # create a new list from the result of applying 'f' to the
  # elements of this list and 'b' in order.
  #
  public zip0(U, V type, b list U, f (A,U)->V) list V =>
    list.this ? c1 Cons => (b ? c2 Cons =>
                                  zip_cons : Cons V (list V) is
                                    head => f c1.head c2.head
                                    tail => c1.tail.zip0 U V c2.tail f
                                  zip_cons
                              | 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) =>
    flat_map V x->(b.map y->(f x y))


  # create an empty list
  #
  public 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 =>
    l -> l.map_to_list B f


  # monoid of lists with infix concatentation 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 renmaing is supported.
  #
  public type.list_concat_monoid : Monoid (list A) is

    # associative operation
    #
    infix ∙ (a, b list A) list A => a.concat b

    # identity element
    #
    e list A =>
      nil


# 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 =>
  ref : Cons T (list T)
    head => h
    tail => t


# 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 to create lists by recursion, e.g., a an endless list containing
# integer 1 repeatedly is
#
#   ones => 1 : ones
#
public infix : (A type, h A, t Lazy (list A)) =>
  list h t


# 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) =>
  h : (f h :: f)