Fuzion Logo
flang.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 infitie 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.
#
#
#
list(A type) : choice<nil, Cons<A, list<A>>>, Sequence<A> is
# list<A> : nil | Cons<A, list<A>> is   -- NYI: sum type syntax
# list<A> : nil | Cons A, list A is     -- NYI: sum type syntax, optional '<', '>'
# list A : nil | Cons A, list A is      -- NYI: sum type syntax, optional '<', '>' (2x)


  # 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.
  #
  redef asList list<A> is list.this


  # is this list empty?
  #
  redef isEmpty => list.this ? nil  => true
                             | Cons => false


  # count the elements of this list
  #
  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 is
    list.this ? nil    => n
              | c Cons => c.tail.count n+1


  # get the head of this list if it exists
  #
  head option<A>
  is
    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
  #
  tail list<A>
  is
    list.this ? nil    => nil
              | c Cons => c.tail


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


  # get the head of this list, panic if list is empty
  #
  forceHead
    pre
      debug: !isEmpty
    => list.this ? nil    => fuzion.std.panic "list.forceHead called on empty list"
                 | c Cons => c.head


  # get the tail of this list, panic if list is empty
  #
  forceTail
    pre
      debug: !isEmpty
    => list.this ? nil    => fuzion.std.panic "list.forceTail called on empty list"
                 | c Cons => c.tail


  # get the head of this list, panic if list is empty
  #
  redef first
    pre
      debug: !isEmpty
    => forceHead


  # get the last element of this list, panic if list is empty
  #
  # This may take time in O(count), in particular, it may not terminate
  # for an infinite list.
  #
  redef last A
    pre
      debug: !isEmpty
  is
    forceTail ? nil    => first
              | c Cons => forceTail.last


  # 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.
  #
  map<B>(f A -> B) list<B> is
    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 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.
  #
  flatMap<B>(f A -> Sequence<B>) list<B> is
    match list.this
      _ nil  => nil
      c Cons =>
        match (f c.head).asList
          _ nil => nil
          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.flatMap<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
  #
  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
  #
  fold (s A, m Monoid<A>) A is list.this ? nil    => s
                                         | c Cons => c.tail.fold (m.op s c.head) 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
  #
  redef take (n i32) list<A>
  is
    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
  #
  reverse list<A> is
    reverse nil


  # recursively reverse the order of the elements in this list
  # and append the already reversed reversedHead
  #
  reverse (reversedHead list<A>) list<A> is
    list.this ? nil    => reversedHead
              | c Cons => c.tail.reverse (cons c.head reversedHead)


  # create a string representation of this list including all the string
  # representations of its contents, separated by ',' and enclosed in '['
  # and ']'.
  #
  redef asString =>
    "[{list.this.asString ","}]"


  # create a string representation of this list including all the string
  # representations of its contents, separated by 'sep'.
  #
  redef asString (sep string) =>
    "{map<string>(x -> x.asString).fold (strings.concat sep)}"


  # List concatenation, O(count)
  #
  concatEagerly (t list<A>) list<A> is
    list.this ? nil    => t
              | c Cons => cons<A, list<A>> c.head (c.tail.concat t)


  # Lazy list concatenation, O(1)
  #
  concat (t list<A>) list<A> is
    match list.this
      _ nil => t
      c Cons =>
        match t
          nil => list.this
          c2 Cons =>
            ref : Cons<A, list<A>>
              head => c.head
              tail => c.tail.concat t

  # infix operand synonyme for concat
  #
  redef infix ++ (t Sequence<A>) => concat t.asList


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


  # create a slice from this list that consists of the elements starting at index
  # 'from' (including) up to index 'to' (excluding).
  #
  redef slice(from, to i32) => drop(from).take to-from


  # Lazily take the first elements of a list for which predicate 'p' holds.
  #
  redef takeWhile (p A -> bool) list<A>
  is
    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.takeWhile p
        else
          nil


  # Lazily drop the first elements of a list for which predicate 'p' holds.
  #
  redef dropWhile (p A -> bool) list<A>
  is
    match list.this
      _ nil  => nil
      c Cons =>
        if p c.head
          c.tail.dropWhile p
        else
          c


  # Lazily filter the elements of a list.
  #
  redef filter (p A -> bool) Sequence<A> is
    filter0 p


  private filter0 (p A -> bool) list<A> is
    match dropWhile (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'
  #
  redef cycle list<A> is
    match list.this
      nil    => nil
      c Cons =>
        cycleCons (h Cons<A, list<A>>) : Cons<A, list<A>> is
          head => h.head
          tail list<A> is
            cycleCons (h.tail ? nil    => c
                              | d Cons => d)
        cycleCons c


  # create a lazy list of all the tails of this list, including the complete list
  # 'list.this' and the empty list 'nil'.
  #
  redef tails list<list<A>> is
    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
  #
  redef asStream ref : stream<A> is
    cur := list.this
    redef hasNext => cur ? Cons => true
                         | nil  => false
    redef next =>
      res := cur.forceHead
      set cur := cur.forceTail
      res


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


# lists -- unit type defining features related to list but not requiring an
# instance
#
#
lists is


  # create an empty list
  #
  empty<A> list<A> is
    nil


  # fmap lifts a function from A to B to a function from list<A> to list<B>
  #
  fmap<A, B> (f A -> B) list<A> -> list<B> is
    l -> l.map<B> f


  # monoid of lists with infix concatentation operation.
  #
  concatMonoid<A> : Monoid<list<A>> is

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

    # equality
    #
    redef infix == (a, b list<A>) =>
      fuzion.std.panic "NYI: lists.concatMonoid.infix ==, requires A : hasEquals"

    # identity element
    #
    e list<A> is
      nil


# convenience routine to create a list from head h and lazy tail t.
#
list<T> (h T, t () -> list<T>) list<T> is
  ref : Cons<T,list<T>>
    head => h
    tail => t()