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)