/**
* This module contains basic functionality for manipulating lists.
*
*/
module collection/list/common
imports
collection/list/cons
collection/list/index
term/integer
strategies
/**
* Iterative loop over a list applying s to each element.
*
* @param Strategy to apply to every element (a -> _)
* @type List(a) -> List(a)
*/
list-loop(s) =
?xs; prim("SSL_list_loop", s | xs)
/**
* Iterative fold over a list applying s to each element and
* accumulator acc from left to right.
*
* @param Strategy applied for folding. The current
* intermediate result is a term argument. The next element
* of the list is the current term.
* @param Initial value for folding (type: c)
* @type List(a) -> c
*/
list-fold(s : c * a -> c | acc) =
?xs; prim("SSL_list_fold", s | acc, xs)
strategies
/** @internal */
Hd : [x | _] -> x
/** @internal */
Tl : [_ | l] -> l
/** @internal */
Last : [x] -> x
/**
* @internal
* @type a -> List(a)
*/
MkSingleton =
![<id>]
/**
* Splits a Cons into a tuple with head and tail.
*
* @type List(a) -> (a, List(a))
*/
split-Cons :
[x | xs] -> (x, xs)
/**
* Makes a Cons out of a tuple with head and tail. The
* tail must be a list, but may be the empty list.
*
* @type (a, List(a)) -> List(a)
*/
MkCons :
(x, xs) -> [x | xs]
strategies
/**
* Succeeds if the input term is a list.
*
* @type List(a) -> _
*/
is-list = ?[] + ?[_ | _]
/**
* Apply a strategy to each element of a list.
*
* @param s is applied to all elements: a -> b
* @type List(a) -> List(b)
* @inc map-test
*/
map(s) =
rec x([] + [s | x])
/** @internal */
map1(s) =
[s | id]; [id | try(map1(s))] <+ [id | map1(s)]
/**
* In reverse order, apply a strategy to each element of a list.
*
* @param s is applied to all elements: a -> b
* @type List(a) -> List(b)
*/
reverse-map(s) =
[id | reverse-map(s)]; [s | id] <+ []
/**
* @inc map
*
* @note list(s) is an alias for map
*/
list(s) =
map(s)
/**
* Apply a strategy to some elements in a list. The elements
* of the original list will be kept unchanged when the
* strategy s fails.
*
* @param s a -> b
* @type List(a) -> List(b)
*/
list-some(s) =
rec x([s| id] < [id| list(try(s))] + [id| x])
/**
* Returns the length of a list.
*
* @type List(a) -> Int
* @inc length-test
*/
length =
?t; prim("SSL_get_list_length", t)
/**
* Succeeds if the term is in the list.
*
* @type (a, List(a)) ->? List(a)
*/
elem =
?(x, <id>); fetch(?x)
/**
* Succeeds if the term is in the list, using the given
* strategy for determining equality.
*
* @param (a, a) ->? b
* @type (a, List(a)) ->? List(a or b)
*/
elem(eq) =
?(x, <id>); fetch(<eq> (x, <id>))
/**
* Find first list element for which s succeeds.
*
* @param a -> b
* @type List(a) -> List(a or b)
* @inc fetch-test
*/
fetch(s) =
rec x([s | id] <+ [id | x])
/**
* Return first list element for which s succeeds.
*
* @type List(a) -> a
* @inc fetch-elem-test
*/
fetch-elem(s) =
fetch(s; ?x); !x
/**
* Splits a list in two parts at the first point where s succeeds.
*
* The element to which s was applied is not part of the result. split-fetch
* fails if s cannot be applied to any of the elements.
*
* Examples:
* <split-fetch(\ 3 -> 6 \)> [1, 2, 3] => ([1,2], [])
* <split-fetch(\ 3 -> 6 \)> [2, 3, 4] => ([2], [4])
* <split-fetch(\ 3 -> 6 \)> [3, 4, 5] => ([], [4,5])
* not(<split-fetch(\ 3 -> 6 \)> [8, 7, 6])
*
* @param a ->? _
* @type List(a) -> (List(a), List(a))
* @inc split-fetch-test
*/
split-fetch(s) =
at-suffix([s|id];[id|?tl];![]); !(<id>, tl)
/**
* Splits a list in two parts at the point where s succeeds, keeping the
* element at which s succeeded.
*
* Unlike split-fetch, this strategy keeps the dividing element as part of
* the result as the second element in the triple: (before, split, after)
*
* split-fetch-keep fails if s cannot be applied to any of the elements.
*
* @param a -> b
* @type List(a) -> (List(a), b, List(a))
*/
split-fetch-keep(s) =
at-suffix([s|id];[?el|?tl];![]); !(<id>, el, tl)
/**
* Breaks a list into multiple parts (tokens).
*
* The term argument sep is a list of delimiters (elements that separate
* tokens from one another), which is used to split the list
* into multiple tokens. The result is a list of lists, i.e. a list
* of tokens.
*
* @param List of separator elements.
* @type List(a) -> List(List(a))
*/
list-tokenize(|sep) =
list-tokenize({c: ?c; <fetch(?c)> sep})
/**
* Breaks a list into multiple parts (tokens).
*
* The strategy argument sep is used to split the list. Wherever it
* succeeds, the original list is split, and the parts are returned
* as a list of lists, i.e. a list of tokens.
*
* @param s a -> fail?
* @type List(a) -> List(List(a))
*/
list-tokenize(sep) =
(split-fetch(sep) <+ !(<id>, []))
; ( \ ( [] , []) -> [] \
+ \ (l@[_ | _], []) -> [l] \
+ \ ( [] , l@[_ | _]) -> <list-tokenize(sep)> l \
+ \ (t@[_ | _], l@[_ | _]) -> [t | <list-tokenize(sep)> l] \
)
strategies
/**
* Apply a strategy to the tail of a list.
*
* @param is applied to the tail: List(a) -> List(b)
* @type List(a) -> List(a or b)
*/
at-tail(s) =
[id | s]
/**
* Apply s to the Nil of a list.
*
* @param is applied to Nil ([]) and must return a list: List(a) -> List(a)
* @type List(a) -> List(a)
*/
at-end(s) =
rec x([id | x] + []; s)
/**
* Apply a strategy to some suffix of a list.
*
* The longest suffix (that is, the first application in a list)
* is preferred.
*
* @param is applied to the suffix : List(a) -> b
* @type List(a) -> List(a or b)
*/
at-suffix(s) =
rec x(s <+ [id | x])
/**
* Apply a strategy to some suffix of a list.
*
* The shortest suffix (that is, the last application in a list)
* is preferred.
*
* @param is applied to the suffix : List(a) -> b
* @type List(a) -> List(a or b)
*/
at-suffix-rev(s) =
rec x([id | x] <+ s)
/**
* Apply s to the last Cons ([_]) of a list.
*
* @param Is applied to the [x] and must return a list: List(a) -> List(a)
* @type List(a) -> List(a)
*/
at-last(s) =
rec x([id]; s <+ [id | x])
/**
* Splits a list into a tuple of its init list and last element.
*
* Example:
* <split-init-last> [1, 2, 3, 4] => ([1, 2, 3], 4)
* <split-init-last> [1] => ([], 1)
*
* @type List(a) -> (List(a), a)
* @inc split-init-last
* @since 0.9.4
*/
split-init-last =
at-last(?[x]; ![]); !(<id>, x)
/**
* Applies s1 to all elements in a list, except the last, where
* s2 is applied.
*
* @param s1 a -> b
* @param s2 a -> b
* @type List(a) -> List(b)
*/
at-init(s1, s2) =
rec x([s2] <+ [s1 | x])
/**
* Applies a strategy to a list in bottom up order. That is to say,
* the strategy s will be applied to successively longer excerpts
* of the list, starting from the end.
*
* At the first invocation, s will be applied to the tail of the list,
* and is expected to return a new list. The last element of the list
* will then be added in front of this result, and s is applied to
* this. The recursion continues through all elements from last to
* first, each time on a longer list, hence "bottom up".
*
* Example: <listbu(![9 | <id>])> [1,2,3,4] => [9,1,9,2,9,3,9,4,9]
*
* @param s List(a) -> List(b)
* @type List(a) -> List(b)
*/
listbu(s) =
rec x(([] + [id| x]); s)
/**
* @inc listbu
*/
listbu1(s) =
[id| listbu1(s)]; try(s) <+ s
/**
* Applies a strategy to a list in top down order. That is to say,
* the strategy s will first be applied to the whole list, then
* successively shorter excerpts, all the way chopping of elements from
* the start of the list.
*
* At the first invocation, s will be applied to the whole list, and
* is expected to return a new list. The first element is chopped off
* this result, and s is applied again, until s has been applied to
* the empty list. The recursion continues through successively
* shorter list, hence "top down".
*
* @note The strategy s cannot result in a list which is longer than
* it is given, because that will result in non-termination.
*
* Example: <listtd(not(?[]) ; ![<sum>] <+ ![])> [1,2,3,4] => [10]
*
* @param s List(a) -> List(b)
* @type List(a) -> List(b)
*/
listtd(s) =
rec x(s; ([] + [id| x]))
/**
* Applies s in a top down then bottom up, i.e. down up, order. See
* listtd and listbu for a detailed description of each phase.
*
* @note As with listtd, the strategy s can never result in a list
* which is longer than given to it.
*
* @param s List(a) -> List(b)
* @type List(a) -> List(b)
*/
listdu(s) =
rec x(s; ([] + [id| x]); s)
/**
* Applies s1 in a top down order then s2 in a bottom up order. See
* listd and listbu for a detailed description of each phase.
*
* @note As with listtd, the strategy s2 can never result in a list
* which is longer than given to it.
*
* @param s1 List(a) -> List(b)
* @param s2 List(a) -> List(b)
* @type List(a) -> List(b)
*/
listdu2(s1, s2) =
rec x(s1; ([] + [id| x]); s2)
/** @internal */
RevInit : xs -> (xs, [])
/** @internal */
Rev : ([x| xs], ys) -> (xs, [x| ys])
/** @internal */
RevExit : ([], ys) -> ys
/**
* Reverses a list.
*
* @inc reverse-test
* @type List(a) -> List(a)
*/
reverse =
reverse-acc(id, ![])
/**
* Reverses a list and applies s to all the elements.
*
* @param a -> b
* @type List(a) -> List(b)
*/
reverse(s) =
reverse-acc(s, ![])
/** @internal */
reverse-acc(s, acc) :
[] -> <acc>()
/** @internal */
reverse-acc(s, acc) :
[x | xs] -> <{ys:where(![<s>x | <acc>] => ys); reverse-acc(s, !ys)}> xs
rules
/** @internal */
UptoInit : i -> (i, [])
/** @internal */
UptoExit : (i, xs) -> xs where <lt> (i, 0)
/** @internal */
UptoStep : (i, xs) -> (<subt> (i, 1), [i| xs])
strategies
/**
* Generates a sequence of numbers from 0 up to the given input
* integer, inclusive.
*
* See also range.
*
* @type Int -> List(Int)
*
* @inc upto-test
*/
upto =
UptoInit; rec x(UptoExit <+ UptoStep; x)
strategies
/**
* Concatenates all lists of a tuple.
*
* @type (List(a), List(a), ...) -> List(a)
* @inc conc-test
*/
conc =
\ (l1, l2) -> <at-end(!l2)> l1 \
<+ \ "" # (xs) -> <concat> xs \
/**
* Concatenates a list of lists into one list.
*
* Example: <concat> [[1,2],[3,4],[5,6]] => [1,2,3,4,5,6]
*
* @type List(List(a)) -> List(a)
* @inc concat-test
*/
concat =
rec x([] + \ [l | ls] -> <at-end(<x> ls)> l\ )
/**
* Concats two elements if both elements are lists. Otherwise, constructs
* a Conc term.
*
* Generic term construction is used to avoid infinite recursion: makeConc
* is used in the compilation of Conc itself.
*
* @type List(a) * List(b) -> List(a|b)
* @type a * b -> Conc(a,b)
*/
makeConc =
?(xs, ys)
; if <is-list> xs; <is-list> ys then conc else !"Conc"#([xs, ys]) end
strategies
/**
* Separates the elements of the list by the specified separator.
* The separate-by variant that uses a term argument is prefered.
*
* @type (sep, List(a)) -> List(a or sep)
*/
separate-by =
?(sep, <id>)
; separate-by(|sep)
/**
* Separates the elements of the list by the specified separator.
* The separate-by variant that uses a term argument is prefered.
*
* @param Strategy that results in a separator.
* @type List(a) -> List(a or sep)
*/
separate-by(sep) =
separate-by(|<sep> ())
/**
* Separates the elements of the list by the specified separator.
*
* @param Separator term
* @type List(a) -> List(a or sep)
*/
separate-by(|sep) =
[]
+ [id |
rec x(
[]
+ [id | x]
; ![sep | <id>]
)]
strategies
/**
* Transposes an n by m matrix. The matrix must be represented as
* a list of n elements, where each element is a list of length m.
* The element of the inner lists may be of any type.
*
* Example: <matrix-transpose> [[1,2],[3,4]] => [[1,3],[2,4]]
*
* @type List(List(a)) -> List(List(a))
*/
matrix-transpose =
map(?[]); ![]
+ map(split-Cons)
; unzip
; (id, matrix-transpose)
; MkCons
/**
* <for-each-pair(s)> (xs, ys) produces the list of pairs <s> (x,y).
* for each pair of x from xs and y from ys.
*
* @inc for-each-pair-test
*
* @type List(a) * List(b) -> List((a,b), ...)
*/
for-each-pair(s) =
?(xs, ys); <map(\ x -> <map(<s>(x,<id>))> ys \ )> xs
strategies
/**
* Succeeds if the first input term is a member of the second.
*
* @type a * List(a) -> a
*/
member = (?x, fetch(?x))
rules
/** @internal */
FoldR1 : [x, y] -> (x, y)
/** @internal */
FoldR : [x | xs] -> (x, xs)
/** @internal */
FoldL(s) : ([x | xs], y) -> (xs, <s> (x, y))
/** @internal */
lsplit(f, g) : x -> [<f> x, <g> x]
strategies
/**
* foldr, requires a list of length > 1.
*
* @param List(a) -> b
* @param (a, b) -> b
* @type List(a) -> b
* @internal
*/
foldr1(s1, s2) =
rec x([id]; s1 <+ FoldR; (id, x); s2)
/**
* foldr, requires a list of length > 1.
* The additional parameter strategy f is applied to each element just
* before each folding step.
*
* @param List(c) -> b
* @param (c, b) -> b
* @param a -> c
* @type List(a) -> b
* @internal
*/
foldr1(s1, s2, f) =
rec x([f]; s1 <+ FoldR; (f, x); s2)
/**
* foldr, requires a list of length > 1.
* Note that s maps (a, a) to a, only one type is involved.
*
* @param (a, a) -> a
* @type List(a) -> a
* @internal
*/
foldr1(s) =
rec x((FoldR1 <+ FoldR; (id, x)); s)
/**
* Right folds a list. That is, the strategy s2 is applied as a
* binary operator between all adjacent elements in the list.
* foldr starts by applying s2 to the last element in the list
* and the result of s1. s1 is therefore the starting point of
* the folding.
*
* Example: <foldr(!0, add)> [1,2,3,4] => 10
*
* @param [] -> b
* @param (a, b) -> b
* @type List(a) -> b
*/
foldr(s1, s2) =
[]; s1
+ \ [y|ys] -> <s2>(y, <foldr(s1, s2)> ys) \
/**
* Right folds a list. That is, the strategy s2 is applied as a
* binary operator between all adjacent elements in the list.
* foldr starts by applying s2 to the last element in the list
* and the result of s1. s1 is therefore the starting point of
* the folding.
*
* The additional parameter strategy f is applied to each element just
* before each folding step.
*
* Example: <foldr(!0, add, inc)> [1,2,3,4] => 14
*
* @param [] -> b
* @param (c, b) -> b
* @param a -> c
* @type List(a) -> b
*/
foldr(s1, s2, f) =
[]; s1 +
\ [y|ys] -> <s2> (<f> y, <foldr(s1, s2, f)> ys) \
/**
* Left folds a list. That is, the strategy sis applied as a
* binary operator between all adjacent elements in the list.
* foldr starts by applying s to b and the first element in
* the list. b is therefore the starting point of the folding.
*
* Example: <foldl(add)> ([1,2,3,4], 0)
*
* @param (a, b) -> b
* @type (List(a), b) -> b
*/
foldl(s) =
rec x( \ ([], y) -> y \ + FoldL(s); x)
/** @internal */
mapfoldr1(s1, s2, s3) =
rec x([id]; s1 <+ [s2|x]; \ [a|b]->(a,b)\; s3)
/**
* Transform the elements of a list into lists (map)
* and concatenate into a single list (concat).
*
* Note: equivalent to map(s); concat
*
* @param a -> List(b)
* @type List(a) -> List(b)
*/
mapconcat(s) =
foldr([], conc, s)
/**
* Returns the last element of a list.
*
* Fails if applied to the empty list.
*
* @type List(a) -> a
*/
last =
rec x(Last <+ Tl; x)
/**
* Returns a list with the first and the last element of
* the input list. For the empty list and the singleton
* list, this is equivalent to id.
*
* @type List(a) -> List(a)
*/
first-last =
[id | try(last; MkSingleton)] <+ []
/**
* Returns a list of all elements of a list, except the last.
*
* Fails if applied to the empty list.
*
* @inc init
* @inc empty init
*
* @type List(a) -> List(a)
*/
init =
at-last(Tl)
/**
* @inc split-init-last
* @note Alias for split-init-last.
*/
split-last =
split-init-last
/**
* Makes n copies of a term into a list of duplicates. The
* first input term is the integer n, the second is the term
* to duplicate.
*
* @inc copy-test
*
* Example: <copy> (3, "foo") => ["foo", "foo", "foo"]
*
* @type Int * a -> List(a)
*/
copy =
for(\ (n,t) -> (n,t,[]) \
,\ (0,t,ts) -> ts \
,\ (n,t,ts) -> (<subt>(n,1), t, [t|ts]) where <geq>(n,1) \ )
/**
* Makes n copies of a term into a list of duplicates, applying
* the strategy s to every copy. The first input term is the
* integer n, the second is the term to duplicate.
*
* Example: <copy(\ "foo" -> "bar" \)> (3, "foo") => ["bar","bar,"bar"]
*
* @param s a -> b
* @type Int * a -> List(n)
*/
copy(s) =
for(\ (n,t) -> (n,t,[]) \
,\ (0,t,ts) -> ts \
,\ (n,t,ts) -> (<subt>(n,1), t, [<s> t|ts]) where <geq>(n,1) \ )
/** @internal */
thread-map(s) :
([], t) -> ([], t)
/**
* Applies s to each element in the list, keeping along a separate
* context term.
*
* For each element in the list, a tuple (a, b) is constructed and
* given to s. From the result, (a', b'), a' goes to the final list
* returned by this strategy, and b' becomes the new b as s is
* applied to the next element.
*
* Example: <thread-map(add ; !(<id>, <id>))> ([1,2,3,4], 1) => ([2,4,7,11],11)
*
* @param s a * b -> a' * b'
* @type List(a) * b -> List(a') * b'
*/
thread-map(s) :
([x | xs], t) -> ([y | ys], t'')
where <s> (x, t) => (y, t')
; <thread-map(s)> (xs, t') => (ys, t'')
/**
* Numbers each element in a list successively with an
* integer, starting at 0. The result is a list of pairs,
* (elem, num) where elem is the original element and num
* is its associated number. s is applied to each pair
* before inserting it into the list
*
* Example: <number(id)> ["a","b","c"] => [("a",0),("b",1),("c",2)]
*
* @inc number-test
*
* @param s a * Int -> a' * Int
* @type List(a) -> List((a,n),...)
*/
number(s) =
!(<id>, 0); thread-map(!(<s>,<Snd;inc>)); ?(<id>,_)
/**
* Take elements from the start of a list while s succeeds.
* Each element of the list is tested against s, starting at
* the head of the list. For as long as s succeeds, the elements
* are accumulated in a list, which is returned as s fails, or
* the end of the list is reached. The actual term returned by
* s is ignored.
*
* Example: <take-while(?2 ; !3)> [2,2,3] => [2,2]
*
* @param s a -> _
* @type List(a) -> List(a)
*/
take-while(s) =
at-suffix([] + ([not(s)|id];![]))
/**
* Take elements from the start of a list until s succeeds.
* Each element of the list is tested against s, starting at
* the head of the list. For as long as s does not succeed, the
* elements are accumulated in a list, which is returned at
* the instant s fails. The actual term returned by s is
* ignored. If s never succeeds, the entire list is returned.
*
* Example: <take-until(?2; !3)> [3,3,2,4] => [3,3]
*
* @param s a -> _
* @type List(a) -> List(a)
*/
take-until(s) =
at-suffix([] + ([s|id];![]))
/**
* Take the first n elements of a list, given by isn. The
* strategy argument isn must produce an integer, which
* gives the length of the sublist to return. If there are
* not enough elements, this strategy fails.
*
* @param isn _ -> Int
* @type List(a) -> List(a)
*/
take(isn) =
take(|<isn>)
/**
* Returns the first n elements of a list, fails
* if list has fewer than n elements.
*
* @param n The number of elements to take.
* @type List(a) -> List(a)
*/
take(|n) =
if <eq>(n,0) then
![]
else
![<Hd> | <Tl; take(|<subt>(n,1))>]
end
/**
* Returns the n first elements after s has been applied to them.
* With the exception of side effects, takemap(s|n) is equal to
* take(|n); map(s). The difference when considering side-effects
* is that s is applied while taking elements, so if s has a
* side-effect these will be performed, even if take fails.
*
* @param n - The number of elements to retrieve
* @param s a -> b
* @type List(a) -> List(b)
*/
takemap(s|n) =
if <eq>(n,0) then
![]
else
![<Hd; s> | <Tl; takemap(s|<subt>(n,1))>]
end
/**
* Drops elements from the start of a list while s succeeds. The
* first element at which s fails and all following it will be
* returned.
*
* Example: <drop-while(?2)> [2,2,3,4] => [3,4]
*
* @param s a -> _
* @type List(a) -> List(a)
*/
drop-while(s) =
at-suffix(([] + [not(s)|id]);?xs); !xs
/**
* Drops elements from the start of a list until s succeeds. The
* first element at which s succeeds and all following it will be
* returned.
*
* Example: <drop-until(?3)> [2,2,3,4] => [3,4]
*
* @param s a -> _
* @type List(a) -> List(a)
*/
drop-until(s) =
at-suffix(([] + [s|id]);?xs); !xs
/**
* Drops the first n elements from a list. If the list has
* fewer than n elements, the strategy fails.
*
* @param n - the number of elements to drop
* @type List(a) -> List(a)
*/
drop(|n) =
if <eq>(n,0) then
id
else
Tl; drop(|<subt>(n,1))
end
/**
* Splits a list after n elements and applies strategy s to the
* first sublist. The second sublist is left untouched.
* Disregarding side-effects, splitmap is equal to
* !(<take(|n); map(s)>, <drop(|n)>). If side-effects are
* considered, note that application of s happens while
* traversing and splitting.
*
* @param s a -> b
* @param n - the number of elements to apply s to, from the start
* @type List(a) -> (List(b), List(a))
*/
splitmap(s|n) =
if <eq>(n,0) then
!([], <id>)
else
where(Hd; s => x)
; where(Tl; splitmap(s|<subt>(n,1)) => (xs, ys))
; !([x | xs], ys)
end
/**
* @inc split-fetch
* @note Alias for split-fetch/1
*/
split-at(s) =
split-fetch(s)
/**
* Splits a list in two, with the second part containing the last
* n elements and and first part containing all elements except the
* last n.
*
* @type List(a) -> (List(a), List(a))
* @param n - the number of elements to split at (counting from the back)
*/
back-split-at(|n) =
foldr(!(([], []), 0)
, {x, l, r, m :
?(x, ((l, r), m))
; if <lt>(m, n)
then
!((l, [x | r]), <inc>m)
else
!(([x | l], r), m)
end})
; ?(<id>, _)
/**
* Drops a number of terms from the front of a list.
*
* The number is specified by the strategy argument, which should
* produce an integer.
*
* @type List(a) -> List(a)
* @param _ -> Int
*/
drop(isn) =
where(isn => n)
; nzip0(id)
; drop-until(?(n,_))
; map(Snd)
/**
* Splits the list in two sublists, containing elements from 0 to
* n and from n onwards.
*
* Example: <split-at(|4)>[1,2,3,4,5,6,7,8,9] => ([1,2,3,4], [5,6,7,8,9])
*
* @type List(a) -> (List(a), List(a))
*/
split-at(|n) =
at-index-tail(?tail; ![] | n)
; !(<id>, tail)
strategies
/**
* Trim elements from the end of a list
*
* Removes the longest sublist from the end of a list, for which
* all elements satisfy the strategy s.
*
* @type List(a) -> List(a)
* @param should succeed for all elements that have to be trimmed.
* @since 0.9.5
* @inc trim-test
*/
rtrim(s) =
![()|<id>] // Add dummy element, or at-suffix-rev will fail at empty lists
; at-suffix-rev(
where( not(?[]) // This only succeeds if we're not at list-end
; not([s|id])) // and s fails at the head of the current suffix
; ![<Hd>]) // s failed, no further trimming.
; Tl // Strip off dummy head element.
/**
* Trim elements from the start of a list.
*
* Removes the longest sublist from the start of a list, for which
* all elements satisfy the strategy s.
*
* @type List(a) -> List(a)
* @param should succeed for all elements that have to be trimmed.
* @since 0.9.5
* @inc trim-test
* @note Alias for drop-while
*/
ltrim(s) = drop-while(s)
/**
* Trim elements from both start and end of a list.
*
* Removest the longest sublist from both start and end of a
* list for which all elements satisfy s.
*
* @type List(a) -> List(a)
* @param s a -> -
* @since 0.9.5
* @inc trim-test
*/
trim(s) = ltrim(s); rtrim(s)
strategies
/**
* Completely flattens a list and its sublists to a single list.
*
* See list-misc-test for examples.
*
* @type List(rec x(a or List(x))) -> List(a)
* @inc flatten-test
*/
flatten-list =
foldr(![], (is-list, id) < conc + MkCons, is-list < flatten-list + id)
/**
* Eliminates all elements at the end of the two lists that are equal.
* Only works correctly on lists of equal length!
*
* Example: <eliminate-common-suffix>([1,3,4], [1,2,4]) => ([1,3], [1,2])
*
* @type (List(a), List(a)) -> (List(a), List(a))
*/
eliminate-common-suffix =
?([x | xs], [y | ys])
; <eliminate-common-suffix>(xs, ys)
; if ?([], []); <eq>(x, y)
then !([], [])
else (![x | <id>], ![y | <id>])
end
<+ !([], [])
/**
* Returns the common prefix of two lists.
*
* Examples:
* <common-prefix>([1,2,3], [1,2,4,5]) => [1,2]
* <common-prefix>([1,2,3], [2,3,4]) => []
*
* @type (List(a), List(a)) -> List(a)
*/
common-prefix =
?([x | xs], [x | ys])
; ![x | <common-prefix>(xs, ys)]
<+ ![]
strategies
strategies
/**
* Returns a list of combinations by choosing one element from every
* list, in every possible combination.
*
* Examples:
*
* $ <list-combinations> [[1, 2]]
* [[1],[2]]
*
* $ <list-combinations> [[1, 2], []]
* []
*
* $ <list-combinations> [[1, 2], ["a", "b"]]
* [[1,"a"],[2,"a"],[1,"b"],[2,"b"]]
*
* $ <list-combinations> []
* [[]]
*
* @type List(List(a)) -> List(List(a))
*/
list-combinations =
let step = fail
<+ \ [] -> [[]] \
<+ \ [[] | _] -> [] \
<+ {xs :
?[xs | <step>]
; map-intermediate(|xs)
}
map-intermediate(|xs) = fail
<+ \ [] -> [] \
<+ {intermediate, tail, tail' :
?[intermediate | tail]
; tail' := <map-intermediate(|xs)> tail
; <map-xs(|intermediate, tail')> xs
}
/**
* This is just a foldr, but Stratego does not support
* specialization of map-xs to an intermediate without
* introducing tuples, which means that we cannot
* use a generic fold.
*/
map-xs(|intermediate, tail) = fail
<+ \ [] -> tail \
<+ {x:
?[x | <id>]
; map-xs(|intermediate, tail)
; ![[x | intermediate] | <id>]
}
in step
end