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)