Fuzion Logo
fuzion-lang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.

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
# 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_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
  =>
    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 ++ [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 =>
    lm : mutate is
      redef mpanic(msg String) => fuzion.std.panic msg
    lm ! ()->
      e := lm.env.new list.this
      array A count _->
        res := e.get.first.get
        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)
          redef head => f c.head
          redef 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 f
          c2 Cons =>
            ref : Cons B (list B)
              redef head => c2.head
              redef tail => (c2.tail ++ c.tail.flat_map_to_list f).as_list


  # 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) =>
    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) =>
    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`
  #
  public redef foldf (B type, f (B,A)->B, e B) =>
    list.this ? nil    => e
              | c Cons => c.tail.foldf f (f e c.head)


  # 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) => 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) =>
    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) =>
    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, f (A,B)->B, e B) =>
    list.this ? nil    => e
              | c Cons => f c.head (c.tail.foldrf f e)


  # 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)


  # 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, f Binary T T A, a T) Sequence T =>
    match head
      nil => a : nil
      x A => (a : (tail.scan T f (f a x)).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 (n i32) Sequence A
  =>
    take_list n


  # 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 =>
          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_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 =>
    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.
  #
  prepend_to_all(sep A, res list A) list A =>
    match head
      nil => res
      x A => tail.prepend_to_all sep (res ++ [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).as_list


  # 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 (n i32) Sequence A =>
    drop_list n


  # 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 (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_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 (p A -> bool) 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 (p A -> bool) list A =>
    match drop_while_list (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.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 =>
    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
          redef head => h.head
          redef 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))
      redef head => list.this
      redef tail =>
        list.this ? nil    => nil
                  | c Cons => c.tail.tails


  # 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 =>
                      zip_cons : Cons V (list V) is
                        redef head => f c1.head c2.head
                        redef tail => c1.tail.zip_list 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 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(by (A,A) -> bool) 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
    =>
      /* NYI: CLEANUP: #4628 the following code can be used once #4628 is fixed

        unique_list2(l list A, existing container.Set A) list A =>
          match list.this
            nil    => nil
            c Cons => if existing.contains c.head then          unique_list2 l  existing
                      else                             c.head : unique_list2 l (existing.add c.head)
        unique_list2 list.this (container.ps_set A).empty
      */

      # workaround for #4628 using new type parameter `X`:
      unique_list(X type : property.orderable, l list X, existing container.Set X) list X =>
        match l
          nil    => nil
          c Cons => if existing.contains c.head then          unique_list X c.tail  existing
                    else                             c.head : unique_list X c.tail (existing.add c.head)

      unique_list A 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 =>
    l -> l.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 =>

    ref : Monoid (list A)

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

      # identity element
      #
      redef e list A =>
        nil


  # equality
  #
  public fixed redef type.equality(a, b list A) => (Sequence A).type.equality a b


# 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)
    redef head => h
    redef 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)
last changed: 2025-01-30