Sequence.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 Sequence
#
# Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------
# Sequence -- ancestor for features that can be converted to a 'list' or a
# 'stream'
#
# Sequences are empty, finite or infinite ordered collections of instances
# of a given type. Sequences may calculate elements lazily on demand.
#
# Sequence is a 'ref' type, i.e., different sub-features may be assigned
# to a field of type 'Sequence'.
#
# Heirs of Sequence must implement either 'as_list' or 'as_stream'. Failure
# to implement any of these results in an endless recursion when the Sequence
# is used.
#
public Sequence(public T type) ref is
# 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.
#
# Default implementation uses as_stream. Heirs must redefine at least
# one of as_list or as_stream.
#
public as_list list T => as_stream.as_list
# create a stream of T.
#
# A stream contains mutable state, so it cannot be reused or shared
# between threads.
#
# Default implementation uses as_list. Heirs must redefine at least
# one of as_list or as_stream.
#
public as_stream stream T => as_list.as_stream
# is this sequence known to be finite? For infinite sequences, features like
# count diverge.
#
public finite => false
# is this Sequence known to be array backed? If so, this means that operations
# like index[] are fast.
#
public is_array_backed => false
# is this Sequence empty?
#
public is_empty => as_list.is_empty
# count the number of elements in this Sequence. Note that this typically
# runs forever if executed on an endless list
#
# For lists that are not array backed, this might require time in O(count).
#
public count
pre
analysis: finite # in practice, we do not always have this information
=> (map i32 (_ -> 1)).fold i32.sum
# get the first element of this Sequence
#
# Sequence must not be empty, causes precondition failure if debug is enabled.
#
public first
pre
debug: !is_empty
=> as_list.head.get
# get the first element of this Sequence or default if sequence is empty
#
public first(default T)
=>
if is_empty then default else first
# get the last element of this Sequence
#
# Sequence 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 Sequence.
#
public last
pre
debug: !is_empty
=> as_list.last
# get the last element of this Sequence or default if sequence is empty
#
public last(default T)
=>
if is_empty then default else last
# collect the contents of this Sequence into an array
#
public as_array array T =>
as_list.as_array
# create an array backed version of this sequence in case this is not array
# backed. This will ensure that operations like index[] or drop perform
# in constant time.
#
# returns Sequence.this if is_array_backed.
#
public as_array_backed Sequence T
post
result.is_array_backed
=>
if is_array_backed
Sequence.this
else
as_array
# create a list and call 'for_each f' on it
#
public for_each(f T -> unit) unit => as_list.for_each f
# calls `f` for element in the Sequence.
#
# Unlike `for_each` this returns itself
# allowing easier composition with
# other Sequence features.
#
# example:
# [1,2,3,4,5]
# .filter is_prime
# .peek say
# .drop_while <10
#
public peek (f T -> unit) =>
as_list ? nil =>
| c Cons => f c.head; c.tail.peek f
as_list
# consume all elements of this Sequence by f. This is an infix operator alias
# for for_each.
#
# Ex.: To print all the elements of a list, you can use
#
# 1..10 ! say
#
public infix ! (f T -> unit) => for_each f
# apply 'f' to each element 'e' as long as 'f e'
#
public for_while(f T -> bool) unit =>
take_while f
.for_each _->unit
# create a new list that contains the first elements of
# this Sequence for which 'f e' is false
#
public before(f T -> bool) list T =>
take_while (x -> !(f x))
# filter elements using predicate f
# values for which f is false are dropped
#
public filter (f T -> bool) list T => as_list.filter f
# filter elements using predicate f, infix operator
# synonym of filter.
#
public infix |& (f T -> bool) => filter f
# filter elements using predicate f, infix operator
# synonym of filter.
#
# NYI: What is better, 'infix |&' or 'infix &', or something else?
#
public infix & (f T -> bool) => filter f
# check if predicate f holds for all elements
#
public infix ∀ (f T -> bool) bool => as_list ∀ f
# check if predicate f holds for at least one element
#
public infix ∃ (f T -> bool) bool => as_list ∃ f
# create a list that consists only of the first n elements of this
# Sequence, fewer if this Sequence has fewer elements
#
public take (n i32) => as_list.take n
# reverse the order of the elements in this Sequence
#
public reverse Sequence T => as_list.reverse_list
# create a list that consists of the elements of this Sequence except the first
# n elements
#
# NOTE: this may have performance in O(n) unless it is backed by an immutable array.
#
#
public drop (n i32) => as_list.drop n
# get a function that, given an index, returns the element at that index
#
public index [] () i32 -> T => n -> Sequence.this[n]
# create a slice from this Sequence that consists of the elements starting at index
# from (including) up to index to (excluding).
#
public slice(from, to i32) Sequence T =>
drop(from).take to-from
# create a tuple of two Sequences by splitting this at the given index, i.e.,
# a Sequence of length 'at' and one of length 'count-at'.
#
# at may be <= 0 or >= count, in which case the resulting tuple will be the
# (empty list, Sequence.this.as_list) or (Sequence.this.as_list, empty list), resp.
#
public split_at(at i32) => ((take at), (drop at))
# Lazily take the first elements of this Sequence for which predicate 'p' holds.
#
public take_while (p T -> bool) => as_list.take_while p
# Lazily drop the first elements of this Sequence for which predicate 'p' holds.
#
public drop_while (p T -> bool) => as_list.drop_while p
# create a Sequence that consists of all the elements of this Sequence followed
# by all the elements of s
#
public concat_sequences (s Sequence T) list T => as_list.concat s.as_list
# infix operand synonym for concat_sequences
#
public infix ++ (s Sequence T) => as_list ++ s.as_list
# create a list that repeats the current Sequence indefinitely. In case 'Sequence.this'
# is empty, returns 'nil'
#
public cycle list T => as_list.cycle
# create a lazy list of all the tails of this Sequence, including the complete Sequence
# as a list and the empty list 'nil'.
#
public tails list (list T) => as_list.tails
# create a string representation of this Sequence including all the string
# representations of its contents, separated by ',' and enclosed in '['
# and ']'.
#
# In case this Sequence is known to be `finite` or has at most (Sequence T).type
# .AS_STRING_NON_FINITE_MAX_ELEMENTS elements, all elements will be shown in the
# resulting string. Otherwise, only the first elements will be shown followed by
# ",…" as in "[1,2,3,4,5,6,7,8,9,10,…]".
#
# To force printing of all elements of a finite `Sequence` for which `finite` is
# false (which may be the case since a Sequence in general might not know that it
# if finite), you may use `as_string_all`.
#
public redef as_string =>
if finite
as_string_all
else
max := (Sequence T).AS_STRING_NON_FINITE_MAX_ELEMENTS
(zip i32 String /* NYI: BUG #2527: type inference not powerful enough to infer `i32` here */
0..max (v,n -> if n < max then $v else "…")).as_string_all
# create a string representation of this Sequence including all the string
# representations of its contents, separated by ", " and enclosed in '['
# and ']'.
#
# NOTE: In case this Sequence is not finite, this will attempt to create an
# infinitely long string resulting in failure due to resource exchaustion.
#
public as_string_all => "[{as_string ", "}]"
# create a string representation of this Sequence including all the string
# representations of its contents, separated by 'sep'.
#
# NOTE: In case this Sequence is not finite, this will attempt to create an
# infinitely long string resulting in failure due to resource exchaustion.
#
public as_string (sep String) => as_list.as_string sep
# call 'as_string' on the elements
#
public as_strings => map c->c.as_string
# map the Sequence to a new Sequence applying function f to all elements
#
# This performs a lazy mapping, f is called only when the elements
# in the resulting list are accessed.
#
public map(B type, f Unary B T) Sequence B =>
as_list.map_to_list f
# map the Sequence to a new Sequence applying function f to all elements
#
# This is an infix operator alias of map enabling piping code like
#
# l := 1..10 | *10 | 300-
#
# to obtain 290,280,270,...200
#
# Note that map and therefore also this operator is lazy, so
#
# _ := (1..10 | say)
#
# will not print anything while
#
# (1..10 | say).for_each _->unit
#
# will print the elements since `for_each` is not lazy.
#
public infix | (B type, f Unary B T) Sequence B => map f
# map each element of this Sequence to Sequence
# Then flatten the result by one level,
# essentially combining all the sequences.
#
public flat_map(B type, f T -> Sequence B) Sequence B =>
as_list.flat_map_to_list f
# Map this Sequence to f applied to neighboring pairs of values
# in this Sequence.
#
# In case this Sequence has less than two elements, the result will
# be the empty list.
#
# ex. to obtain a list of differences you, you may use `map_pairs (-)`:
#
# [2,3,5,7,11,13,17,19,23,29].map_pairs a,b->b-a
#
# results in `[1,2,2,4,2,4,2,4,6]`
#
public map_pairs(B type, f (T,T)->B) list B =>
zip (drop 1) f
# fold the elements of this Sequence using the given monoid.
#
# e.g., to sum the elements of a Sequence of i32, use s.fold i32.sum
#
public fold (m Monoid T) => as_list.fold m.e m
# fold the elements of this non-empty Sequence using the given function
#
# e.g., to find the minimum of a Sequence of i32, use `s.fold1 (<=)`
#
public fold1 (f (T,T)->T) T
pre
debug: !is_empty
=>
as_list.fold1 f
# fold the elements of this Sequence using the given function and initial
# value.
#
# In case this Sequence is empty, the result is `e`.
#
# e.g., to find the product of a Sequence of i32, use `s.foldf (*) 1`
#
public foldf (B type, f (B,T)->B, e B) B
=>
as_list.foldf_list 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 scan (m Monoid T) => as_list.scan m.e m
# reduce this Sequence to R with an initial value init
# and a reducing function f.
# the reduction is finished once f yields abort or
# if the end of the sequence is reached.
#
public reduce(R type, init R, f (R,T) -> R | abort R) R =>
match as_list
nil => init
c Cons =>
match f init c.head
a abort => a.val
r R => c.tail.reduce r f
# reduce this Sequence to `outcome R`
# with an initial value `init` and a reducing function `f`.
# the reduction is finished once `f` yields `abort` or
# if the end of the sequence is reached.
#
public reduce_or_error(R type, init R, f (R,T) -> R | abort (outcome R)) outcome R =>
match as_list
nil => init
c Cons =>
match f init c.head
a abort => a.val
r R => c.tail.reduce_or_error r f
# insert element v at position at
#
public insert(at i32, v T)
pre
debug: at ≥ 0
=>
take at ++ [v] ++ drop at
# sort this Sequence using the total order defined by less_or_equal
public sort(less_or_equal (T, T) -> bool) => container.sorted_array Sequence.this less_or_equal
# sort this Sequence using total order defined for 'f a[i]'
public sort_by(O type : property.orderable, f T->O) => sort (a, b -> f a ≤ f b)
# create a new list from the result of applying 'f' to the
# elements of this Sequence and 'b' in order.
#
public zip(U,V type, b Sequence U, f (T,U)->V) => as_list.zip0 b.as_list f
# create a new Sequence from the result of applying 'f' to the
# elements all combinations of elements of this Sequence and
# all elements of 'b' iterating of 'b' repeatedly as follows
#
# Sequence.this[0] , b[0]
# Sequence.this[0] , b[1]
# Sequence.this[0] , b[2]
# Sequence.this[0] , ...
# Sequence.this[0] , b.last
# Sequence.this[1] , b[0]
# Sequence.this[1] , b[1]
# Sequence.this[1] , ...
# ... , ...
# Sequence.this.last, b.last
#
public combine(U, V type, b Sequence U, f (T,U)->V) Sequence V =>
flat_map V x->(b.map y->(f x y))
# create a new Sequence from tuples of all combinations of elements
# of this Sequence and all elements of 'b' iterating of 'b' repeatedly
# as follows
#
# (Sequence.this[0] , b[0] )
# (Sequence.this[0] , b[1] )
# (Sequence.this[0] , b[2] )
# (Sequence.this[0] , ... )
# (Sequence.this[0] , b.last)
# (Sequence.this[1] , b[0] )
# (Sequence.this[1] , b[1] )
# (Sequence.this[1] , ... )
# (... , ... )
# (Sequence.this.last, b.last)
#
public pairs(U type, b Sequence U) Sequence ((T, U)) =>
combine b x,y->(x,y)
# takes a transducer xf, a reducer f and an initial value
# returns the result of applying the reducer xf f to the Sequence
public transduce(TA,U type, xf transducer TA U T, rf (TA,U) -> TA, init TA) TA =>
red := xf.call rf
for
res := init, red.call res el
el in Sequence.this do
else
res
# apply transducer to sequence, returning a sequence of results
#
# example usage:
# human(age i32) is
# ages := map (Sequence i32) human i32 (x -> x.age)
# gt_ten := filter (Sequence i32) i32 (x -> x > 10)
# xf := ages ∘ gt_ten
# say ([human(4), human(12), human(30)].into xf) # [12,30]
public into(TA type, xf transducer (Sequence TA) TA T) list TA =>
red := xf.call ((res,val) -> res ++ [val])
for
res (list TA) := (list TA).empty , (red.call res el).as_list
el in Sequence.this do
else
res
# the nth element in the sequence if it exists, wrapped in an option,
# nil otherwise.
#
public nth(n i32) option T
pre
debug: n ≥ 0
=>
match drop n
nil => nil
c Cons => c.head
# the nth element in the sequence, must exist
#
public index [] (i i32) T
pre
debug: 0 ≤ i
debug: finite: i < count
debug: !finite: !(drop i-1).is_empty
=>
(nth i).get
# adds the corresponding index to
# every element in the sequence
#
public indexed list (tuple i32 T) =>
indexed 0
# adds an index to every element
# in the sequence starting at start_idx
#
public indexed(I type : has_interval, start_idx I) list (tuple I T) =>
# NYI: This should work without the type hints again.
zip I (tuple I T) (start_idx..) (a,b -> (b, a))
# chop this Sequence into chunks of `chunk_size`.
# the last chunk may be smaller than `chunk_size`.
#
public chunk(chunk_size i32) list (list T)
pre chunk_size > 0
=>
if is_empty
nil
else
(take chunk_size).as_list : ((drop chunk_size).chunk chunk_size)
# monoid of Sequences with infix concatentation operation.
#
public type.concat_monoid : Monoid (Sequence T) is
# associative operation
#
infix ∙ (a, b Sequence T) Sequence T => a.concat_sequences b
# identity element
#
e Sequence T =>
(list T).empty
# Maximum number of elements shown for on a call to `as_string` for a non-finite
# Sequence.
#
public type.AS_STRING_NON_FINITE_MAX_ELEMENTS => 10
