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'
#
# 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 'as_list'.
#
public Sequence(public T type) ref : property.equatable is
# create a list from this Sequence.
#
# A list is immutable, so it can be reused and shared between threads.
#
# Heirs must provide an implementation of as_list.
#
public as_list list T => abstract
# is this sequence known to be finite? For infinite sequences, features like
# count diverge.
#
# TRUE = known finite
# FALSE = known infinite
# nil = unknown
#
public finite trit => nil
# 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 != trit.no # in practice, we do not always have this information
=> (map i32 (_ -> 1)).fold i32.sum
# count the number of elements in this Sequence that match the
# given predicate. Note that this typically
# runs forever if executed on an endless list.
#
public count(f T->bool) =>
(filter f).count
# get the first element of this Sequence
#
public first
=> as_list.first
# get the first element of this Sequence or default if sequence is empty
#
public first(default T)
=>
first.val default
# get the last element of this Sequence
#
# This may take time in O(count), in particular, it may not terminate
# for an infinite Sequence.
#
public last
=> as_list.last
# get the last element of this Sequence or default if sequence is empty
#
public last(default T)
=>
last.val default
# collect the contents of this Sequence into an array
#
public as_array array T =>
if is_array_backed
array count (i -> Sequence.this[i])
else
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
debug: 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) Sequence T =>
take_while (x -> !(f x))
# filter elements using predicate f
# values for which f is false are dropped
#
public filter (f T -> bool) Sequence 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) Sequence T => 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) Sequence T => 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
pre
debug: from ≥ 0
debug: to = 0 || is_valid_index to-1
debug: from <= to
=>
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) Sequence T => as_list.take_while p
# Lazily drop the first elements of this Sequence for which predicate 'p' holds.
#
public drop_while (p T -> bool) Sequence T => 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 (s Sequence T) Sequence T => as_list.concat_list s.as_list
# infix operand synonym for concat
#
public infix ++ (s Sequence T) => concat s
# create a list that repeats the current Sequence indefinitely. In case 'Sequence.this'
# is empty, returns 'nil'
#
public cycle Sequence 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 = trit.yes
as_string_all
else
max0 := (Sequence T).AS_STRING_NON_FINITE_MAX_ELEMENTS
(zip 0..max0 (v,n -> if n < max0 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 exhaustion.
#
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 exhaustion.
#
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) Sequence 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 f e
# 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 foldr (m Monoid T) => as_list.foldr 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 foldr (s T, m Monoid T) => as_list.foldr m.e 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 foldr1 (f (T,T)->T) => as_list.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 foldrf (B type, f (T,B)->B, e B) => as_list.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 scan (m Monoid T) => as_list.scan m.e m
# map this Sequence to a list that contains the result of folding
# all prefixes using the given function and initial value.
#
# e.g., for a Sequence s of i32, s.scan (+) 0 creates a list of
# partial sums (0..).map x->(s.take x).fold i32.sum
#
public scan (R type, f Binary R R T, a R) Sequence R => as_list.scan R f a
# 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 order defined by less_or_equal
#
public sort_by(less_or_equal (T, T) -> bool) => container.sorted_array Sequence.this less_or_equal
# sort this Sequence
#
public sort
pre
T : property.orderable
post
result.map_pairs (<=)
.reduce true (&&)
=>
sort_by (<=)
# 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) Sequence V => as_list.zip b 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 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) Sequence 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.
#
# Complexity: if Sequence is array backed O(1) otherwise O(n)
#
public nth(n i32) option T
pre
debug: n ≥ 0
=>
if is_array_backed
if (is_valid_index n) then Sequence.this[n] else nil
else
(drop n).first
# check if argument is a valid index in this sequence.
#
# Note that this may have a performance in O(i) unless this
# Sequence is_array_backed.
#
public is_valid_index(i i32) =>
(0 ≤ i && (if is_array_backed then i ≤ count
else !(drop i-1).is_empty))
# the nth element in the sequence, must exist
#
public index [] (i i32) T
pre
debug: is_valid_index(i)
=>
(nth i).get
# adds the corresponding index to
# every element in the sequence
#
public indexed Sequence (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) Sequence (tuple I T) =>
zip (start_idx..) (a,b -> (b, a))
# convenience feature to work around type inference issues
# NYI remove when type inference gets better
public as_seq Sequence T =>
Sequence.this
# chop this Sequence into chunks of `chunk_size`.
# the last chunk may be smaller than `chunk_size`.
#
public chunk(chunk_size i32) Sequence (Sequence T)
pre debug: chunk_size > 0
=>
if is_empty
(Sequence (Sequence T)).empty
else
(take chunk_size) : ((drop chunk_size).chunk chunk_size).as_list
# chop this Sequence into tuples of size 2. In case
# the number of elements is not a multiple of 2,
# the last count % 2 elements will be dropped silently.
#
# ex.
#
# [1,2,3,4,5].tuples produces [(1,2),(3,4)]
#
public as_tuples Sequence (T, T)
=>
h := take 2
t := drop 2
if h.count < 2
(Sequence (T,T)).empty
else
h.as_tuple : t.as_tuples.as_list
# chop this Sequence into tuples of size 3. In case
# the number of elements is not a multiple of 3,
# the last count % 3 elements will be dropped silently.
#
# ex.
#
# [1,2,3,4,5,6,7].tuples3 produces [(1,2,3),(4,5,6)]
#
public as_3tuples Sequence (T, T, T)
=>
h := take 3
t := drop 3
if h.count < 3
(Sequence (T,T,T)).empty
else
h.as_3tuple : t.as_3tuples.as_list
# chop this Sequence into tuples of size 4. In case
# the number of elements is not a multiple of 4,
# the last count % 4 elements will be dropped silently.
#
# ex.
#
# [1,2,3,4,5].tuples4 produces [(1,2,3,4)]
#
public as_4tuples Sequence (T, T, T, T)
=>
h := take 4
t := drop 4
if h.count < 4
(Sequence (T,T,T,T)).empty
else
h.as_4tuple : t.as_4tuples.as_list
# chop this Sequence into tuples of size 5. In case
# the number of elements is not a multiple of 5,
# the last count % 5 elements will be dropped silently.
#
# ex.
#
# [1,2,3,4,5,6].tuples5 produces [(1,2,3,4,5)]
#
public as_5tuples Sequence (T, T, T, T, T)
=>
h := take 5
t := drop 5
if h.count < 5
(Sequence (T,T,T,T,T)).empty
else
h.as_5tuple : t.as_5tuples.as_list
# chop this Sequence into tuples of size 6. In case
# the number of elements is not a multiple of 6,
# the last count % 6 elements will be dropped silently.
#
# ex.
#
# [1,2,3,4,5,6,7].tuples6 produces [(1,2,3,4,5,6)]
#
public as_6tuples Sequence (T,T, T, T, T, T)
=>
h := take 6
t := drop 6
if h.count < 6
(Sequence (T,T,T,T,T,T)).empty
else
h.as_6tuple : t.as_6tuples.as_list
# convert a Sequence's head into a 2-tuple.
#
# ex.
#
# [1,2,3,4,5].as_tuple produces (1,2)
# [1,2].as_tuple produces (1,2)
# [1].as_tuple breaks the pre condition
# [].as_tuple breaks the pre condition
#
public as_tuple() (T, T)
pre
debug: take 2 .count = 2
=>
match as_list
c1 Cons =>
match c1.tail
c2 Cons => (c1.head, c2.head)
nil => panic "as_tuple called on single element Sequence"
nil => panic "as_tuple called on empty Sequence"
# convert a Sequence's head into a 3-tuple.
#
# ex.
#
# [1,2,3,4,5].as_3tuple produces (1,2,3)
# [1,2,3].as_3tuple produces (1,2,3)
# [1,2].as_3tuple breaks the pre condition
# [1].as_3tuple breaks the pre condition
# [].as_3tuple breaks the pre condition
#
public as_3tuple() (T, T, T)
pre
debug: take 3 .count = 3
=>
r option (T, T, T) := match as_list
c1 Cons =>
match c1.tail
c2 Cons =>
match c2.tail
c3 Cons => (c1.head, c2.head, c3.head)
nil => nil
nil => nil
nil => nil
r.val
# convert a Sequence's head into a 4-tuple.
#
# ex.
#
# [1,2,3,4,5].as_4tuple produces (1,2,3,4)
# [1,2,3,4].as_4tuple produces (1,2,3,4)
# [1,2,3].as_4tuple breaks the pre condition
# [1,2].as_4tuple breaks the pre condition
# [1].as_4tuple breaks the pre condition
# [].as_4tuple breaks the pre condition
#
public as_4tuple() (T, T, T, T)
pre
debug: take 4 .count = 4
=>
r option (T, T, T, T) := match as_list
c1 Cons =>
match c1.tail
c2 Cons =>
match c2.tail
c3 Cons =>
match c3.tail
c4 Cons => (c1.head, c2.head, c3.head, c4.head)
nil => nil
nil => nil
nil => nil
nil => nil
r.val
# convert a Sequence's head into a 5-tuple.
#
# ex.
#
# [1,2,3,4,5,6].as_5tuple produces (1,2,3,4,5)
# [1,2,3,4,5].as_5tuple produces (1,2,3,4,5)
# [1,2,3,4].as_5tuple breaks the pre condition
# [1,2,3].as_5tuple breaks the pre condition
# ...
# [].as_5tuple breaks the pre condition
#
public as_5tuple() (T, T, T, T, T)
pre
debug: take 5 .count = 5
=>
r option (T, T, T, T, T) := match as_list
c1 Cons =>
match c1.tail
c2 Cons =>
match c2.tail
c3 Cons =>
match c3.tail
c4 Cons =>
match c4.tail
c5 Cons => (c1.head, c2.head, c3.head, c4.head, c5.head)
nil => nil
nil => nil
nil => nil
nil => nil
nil => nil
r.val
# convert a Sequence's head into a 6-tuple.
#
# ex.
#
# [1,2,3,4,5,6,7].as_6tuple produces (1,2,3,4,5,6)
# [1,2,3,4,5,6].as_6tuple produces (1,2,3,4,5,6)
# [1,2,3,4,5].as_6tuple breaks the pre condition
# [1,2,3,4].as_6tuple breaks the pre condition
# ...
# [].as_6tuple breaks the pre condition
#
public as_6tuple() (T, T, T, T, T, T)
pre
debug: take 6 .count = 6
=>
r option (T, T, T, T, T, T) := match as_list
c1 Cons =>
match c1.tail
c2 Cons =>
match c2.tail
c3 Cons =>
match c3.tail
c4 Cons =>
match c4.tail
c5 Cons =>
match c5.tail
c6 Cons => (c1.head, c2.head, c3.head, c4.head, c5.head, c6.head)
nil => nil
nil => nil
nil => nil
nil => nil
nil => nil
nil => nil
r.val
# does this sequence start with l?
#
public starts_with(l Sequence T) bool
pre
T : property.equatable
=>
match l.as_list
nil => true
c1 Cons =>
match as_list
nil => false
c2 Cons => c2.head = c1.head && c2.tail.starts_with c1.tail # tail recursion
# determine the index of element x within this list. 0 if x is at the
# head of the list, 1 if it comes directly after head, etc. nil if x is
# not in the list.
#
public index_of(x T)
pre
T : property.equatable
=>
find [x]
# does the Sequence contain element x?
#
public contains(x T)
pre
T : property.equatable
=>
(find [x]).exists
# get the index of pattern within this Sequence or nil if it does not exist
#
# uses the Knuth-Morris-Pratt algorithm
# port of racket code from this paper:
# https://www.cambridge.org/core/services/aop-cambridge-core/content/view/8EFA77D663D585B68630E372BCE1EBA4/S0956796824000017a.pdf/knuth-morris-pratt-illustrated.pdf
#
# worst-case performance: O( seq_length ) + O( pattern_length )
# worst-case space complexity: O( pattern_length )
#
public find(pattern Sequence T) option i32
pre
T : property.equatable
=>
find_lm ! ()->
make(t Sequence T, r option (Node T)) =>
n option (Node T) =>
if t.is_empty then nil else make (t.drop 1) (step r t[0])
r_star =>
if t.is_empty
r
else if is_match r t[0]
r.get.rest
else
r
Node t (once find_lm (option (Node T)) ()->n) r_star
init := make pattern nil
step(acc option (Node T), x T) =>
match acc
nil => init
n Node => if is_match acc x then n.next.get else step n.rest x
is_done (option (Node T))->bool => (acc)->
match acc
nil => false
n Node => n.top.is_empty
is_match(acc option (Node T), x T) =>
match acc
nil => false
n Node => !n.top.is_empty && n.top[0] = x
fold_until(acc option (Node T), step (option (Node T), T)->option (Node T), data Sequence T) option i32 =>
if is_done acc
Sequence.this.count - data.count - pattern.count
else if data.is_empty
nil
else
acc_star =>
fold_until.this.step acc data[0]
fold_until acc_star fold_until.this.step (data.drop 1)
fold_until init step Sequence.this
# replace all occurrences of old by new
#
public replace(old, new Sequence T)
pre
T : property.equatable
=>
nil_list list T := nil
replace old new nil_list Sequence.this nil
# replace the first n occurrences of old by new
#
public replace (old, new Sequence T, n u64)
pre
T : property.equatable
=>
nil_list list T := nil
replace old new nil_list Sequence.this n
# tail recursive helper for the replace features
#
replace(old, new,
already_replaced, # the head part with old already replaced by new
to_be_replaced Sequence T, # the tail that still needs to be searched for old
limit option u64
)
pre
T : property.equatable
=>
match to_be_replaced.find old
nil => already_replaced ++ to_be_replaced
n i32 =>
if limit = 0
already_replaced ++ to_be_replaced
else
a := already_replaced ++ (to_be_replaced.take n) ++ new
b := to_be_replaced.drop (n + old.count)
replace old new a b (limit >>= (l -> l - 1))
# get the number of matches of l
#
public count_matches_overlapping(l Sequence T) i32
pre
T : property.equatable
=>
tails
.filter (.starts_with l)
.count
# get the number of non-overlapping matches of l within this
#
public count_matches(l Sequence T) i32
pre
T : property.equatable
=>
match as_list
nil => 0
c1 Cons => if starts_with l then 1 + (drop l.count).count_matches l
else c1.tail.count_matches l
# split sequence at s, if there is no limit, otherwise if limit is an integer n,
# for at most n occurrences of s
#
# if split_after is true, all but the last element of the resulting list include
# the separator
#
# helper feature which unifies the code of the different split features in one
#
module split0(s Sequence T, limit option u32, split_after bool) list (Sequence T)
pre
T : property.equatable
debug: !s.is_empty
debug: match limit
nil => true
n u32 => n > 0
=>
match (find s)
nil => (id (Sequence T) Sequence.this) : nil # NYI: With better type propagation, this could be `Sequence.this : nil` or `[Sequence.this].as_list`
idx i32 =>
ref : Cons (Sequence T) (list (Sequence T))
redef head Sequence T := take (if split_after then idx + s.count else idx)
redef tail =>
rest := drop (idx + s.count)
match limit
nil => rest.split0 s nil split_after
n u32 =>
if n > 1
rest.split0 s (n - 1) split_after
else
res Sequence T := rest
res : nil
# filter out consecutive duplicate elements.
#
# Keep the order of elements unchanged.
#
# ex.
# [1,2,2,3,2,2,2,4].dedup = [1,2,3,2,4]
#
public dedup Sequence T
pre
T : property.equatable
=>
as_list.dedup_list
# filter out consecutive duplicate elements using the
# given relation.
#
# Keep the order of elements unchanged.
#
# ex.
# [4,2,2,6,2,1,2,4].dedup (a,b -> a%2=b%2) = [4,1,2]
# [4,2,2,6,2,1,2,4].dedup (<=) = [4,2,1]
#
public dedup(by (T,T) -> bool) Sequence T
pre
T : property.equatable
=>
as_list.dedup_list by
# filter out duplicate elements.
#
# Keep the order of elements unchanged.
#
# Other languages call this 'distinct', (eg., Java, C# or Kotlin)
# or `nub` (Haskell).
#
# ex.
# [4,1,2,2,3,2,2,2,4].unique = [4, 1, 2, 3]
#
public unique Sequence T
pre
T : property.orderable
=>
as_list.unique_list
# the arithmetic mean of the sequence
# https://en.wikipedia.org/wiki/Arithmetic_mean
public average option T
pre
T : numeric
=>
if is_empty
nil
else
cnt := (map _->T.one).fold T.sum
sum := fold T.sum
sum / cnt
# the variance of the sequence
# https://en.wikipedia.org/wiki/Variance
public variance option T
pre
T : numeric
=>
average.bind T avg->
cnt := (map (_ -> T.one )).fold T.sum
sum := (map (x -> (x - avg)**T.two)).fold T.sum
sum / cnt
# minimum value in the sequence
public min option T
pre
T : property.orderable
=>
match first
nil => nil
v T => reduce v ((r,t) -> if r ≤ t then r else t)
# maximum value in the sequence
public max option T
pre
T : property.orderable
=>
match first
nil => nil
v T => reduce v ((r,t) -> if r ≤ t then t else r)
# the median of the sequence
# https://en.wikipedia.org/wiki/Median
public median option T
pre
T : numeric
=>
if is_empty
nil
else
sorted := sort
if sorted.length % 2 = 1
sorted[sorted.length / 2]
else
(sorted[(sorted.length / 2) - 1] + sorted[(sorted.length / 2)]) / (T.two)
# the standard deviation of the sequence
# https://en.wikipedia.org/wiki/Standard_deviation
public std_dev
pre
T : float
=>
variance.map x->x.sqrt
# the euclidean norm of this sequence
# i.e. the square of the sum of squares of this sequence
#
public euclidean_norm
pre
T : float
=>
((map x->x**T.two).fold T.sum).sqrt
# sliding window with step size one
# blocks of size elements, each is offset by one element to the previous one
#
# example:
# `(0..5).sliding 3`
# => `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`
#
public sliding (size i32) =>
sliding size 1
# sliding window
# blocks of size elements, each is offset by step elements to the previous one
#
# examples:
# `(0..5).sliding 3 1`
# => `[[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]`
#
# `(0..9).sliding 3 2`
# => `[[0, 1, 2], [2, 3, 4], [4, 5, 6], [6, 7, 8]]`
#
public sliding (size i32, step i32) Sequence (Sequence T)
pre
debug: size > 0
debug: step > 0
=>
as_list.sliding size step
# group elements using key_f and reduce elements within a group using reduce_f
# in contrast to the more general version, values in the resulting map must have the same type as in the input
#
# example: sum even and odd numbers individually
#
# (0..10).group_reduce String (x -> x%%2 ? "even" : "odd") (+)
#
# => {(even => 30), (odd => 25)}
#
public group_reduce (
# type of the keys
K type : property.orderable,
# function to generate the key
key_f Unary K T,
# function to reduce the elements
reduce_f Binary T T T) container.Map K T
=>
group_map_reduce K T key_f id reduce_f
# group elements using key_f and
# reduce elements within a group by first applying f and then using reduce_f to reduce
#
# example: count occurrences of letters, numbers and other characters
#
# values array codepoint := ["A", "1", "b", "?", "X", "4"]
#
# classify (c codepoint) String => c.is_ascii_letter ? "letter" : c.is_ascii_digit ? "digit" : "other"
#
# values.group_map_reduce String i32 classify (_->1) (+)
#
# => {(digit => 2), (letter => 3), (other => 1)}
#
public group_map_reduce (
# type of the keys
K type : property.orderable,
# type of the values in the result
B type,
# function to generate the keys
key_f Unary K T,
# function applied to elements before they are reduce
f Unary B T,
# function to reduce elements
reduce_f Binary B B B) container.Map K B
=>
M : mutate is
M ! ()->
res := (container.mutable_tree_map M K B).empty
for_each x->
key := key_f x
match res[key]
nil => res.put key (f x)
y B => res.put key (reduce_f y (f x))
res.as_map
# group the elements of this sequence by a key of type and applies function f to all elements
#
# example: group characters by category and add underscores around each character
#
# values array codepoint := ["A", "1", "b", "?", "X", "4"]
#
# classify (c codepoint) String => c.is_ascii_letter ? "letter" : c.is_ascii_digit ? "digit" : "other"
#
# values.group_map String String classify (x->"_{x}_")
#
# => {(digit => [_1_, _4_]), (letter => [_A_, _b_, _X_]), (other => [_?_])}
#
public group_map (
# type of the keys
K type : property.orderable,
# type of the values in the result
B type,
# function to generate the keys
key_f Unary K T,
# function applied to each element
f Unary B T) container.Map K (Sequence B)
=>
M : mutate is
M ! ()->
res := (container.mutable_tree_map M K (Sequence B)).empty
for_each x->
key := key_f x
match res[key]
nil => res.put key [(f x)]
y Sequence B => res.put key (y ++ [(f x)])
res.as_map
# create an empty Sequence
#
public fixed type.empty Sequence T =>
(list T).type.empty
# monoid of Sequences with infix concatenation operation.
#
public type.concat_monoid =>
ref : Monoid (Sequence T)
# associative operation
#
redef infix ∙ (a, b Sequence T) Sequence T => a.concat b
# identity element
#
redef 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
# Sequence is equatable only if T is
#
public redef type.is_equatable => T : property.equatable
# equality
#
public fixed redef type.equality(a, b Sequence T) =>
equality0(a1, b1 Sequence (T2 : property.equatable)) =>
(a1.zip b1 x,y->x=y) ∀ id
if T : property.equatable
if a.finite=trit.yes && b.finite=trit.yes
a.count = b.count && equality0 a b
else if a.finite=trit.yes
a.count = (b.take (a.count+1)).count && equality0 a b
else if b.finite=trit.yes
b.count = (a.take (b.count+1)).count && equality0 a b
else
equality0 a b &&
{zip_count := (a.zip b x,y->unit).count
(a.drop zip_count).is_empty && (b.drop zip_count).is_empty}
else
panic "***"
# helper features for knuth morris pratt algorithm
#
find_lm : mutate is
Node(T type, top Sequence T, next once find_lm (option (Node T)), rest option (Node T)) ref is
