This package provides common list functions for the Frege language.
It contains all functions described in section 9.1 of the Haskell 2010 Language Report, except for lookup and !!. These functions have been moved to frege.data.List (the equivalent of Haskell's Data.List).
In addition to the common list functions, three type classes capture common properties of types that are like ordinary lists:
This module is implementation specific insofar as the compiler may assume that certain items are defined here in a certain way. Changes may thus lead to compiler crashes or java code that will be rejected by the java compiler.
In particular, desugared list comprehensions will reference ListSource.toList.
This package is implicitly imported.
A class for containers/collections that have an empty value.
the empty container
true if and only if the container is ListEmpty.empty
A class for types that support the (++) operator.
ListMonoid.concat concatenates the subitems of the argument which is a list of list or a list of strings.
It is ok if the argument is an infinite list or any of the sublists is infinite. In either case, the result will also be infinite.
A class for types that support ListMonoid.concat
concatenate two lists, strings or whatever
empty ++ x == x && x ++ empty == x
A class for things we can view as a list
Such data types are instances of ListMonoid and support ListView.head, ListView.tail, ListView.length and concatenation (ListSemigroup.++)
This class provides no means to construct a list.
drop a number of initial elements
The first element of a list-view, or undefined if ListEmpty.empty
computes the length of the container in a type dependent way
The tail of a list-view, or undefined if ListEmpty.empty
take a number of initial elements
converts a list-view to a list
split the input stream in head and tail
A class of things we can make a list from
converts the value to a list
Eagerly converts a String to a list.
convert a list of characters to a string
packed ['a', 'b', 'c' ] == "abc"
Not very efficient, may be replaced by a java function that does it with a string buffer later.
strhead s n returns the initial portion of s with at most n characters. if s.ListView.length is lower than n, only so much characters are returned.
and returns the conjunction of a Boolean list. For the result to be true, the list must be finite; false, however, results from a false value at a finite index of a finite or infinite list.
or returns the disjunction of a Boolean list. For the result to be false, the list must be finite; true, however, results from a true value at a finite index of a finite or infinite list.
any p xs tells if any element of xs has property p. This is equivalent to
fold (||) false (map p xs)
except that any stops at the first element that has property p.
Note that, according to the identity above, any p [] is always false.
all p xs tells if all elements of xs have property p. This is equivalent to
fold (&&) true (map p xs)
except that all stops at the first element that hasn't property p.
Note that, according to the identity above, all p [] is always true.
Map a function over a list and concatenate the list or string results.
cycle xs builds a value that is an infinite repetition of xs, which must not be empty.
filter p xs returns the list of elements x from xs where (p x) holds.
filter will not stop to evaluate its argument list until the first/next element with the property asked for is found. For example
filter (==true) (repeat false)
will loop forever, whereas
filter even [1..]
will faithfully deliver the list of positive integers that are divisible by 2, one by one.
warning: It is strongly advised to use fold instead - beware of stack overflow!
foldl, applied to a binary operator, a starting value (typically the left identity of the operator), and a list, reduces the list using the binary operator, from left to right:
fold f z [x1, x2, ..., xn] = (((z `f` x1) `f` x2) `f` ...) `f` xn
Because the operator is applied lazily, foldl typically builds up large thunks which, when finally evaluated, may overflow the stack space. Therefore, the use of fold instead of foldl is strongly suggested.
This function exists merely for compatibility with Haskell.
fold, applied to a binary operator, a starting value (typically the left identity of the operator), and a list, reduces the list using the binary operator, from left to right:
fold f z [x1, x2, ..., xn] = (((z `f` x1) `f` x2) `f` ...) `f` xn
fold runs in constant stack space, but consumes the entire list before returning a result, so it must not be applied to infinite lists.
This function is known as foldl' in Haskell where there is a bias in favour of using foldr.
In the environment of the JVM stack space is precious, hence one should prefer fold when one has the choice.
fold is strict in the accumulator, hence in every recursion the intermediate result is evaluated, thus preventing build up of possibly huge thunks that result in stack overflows on evaluation.
The sum of the numbers in a list, same as (fold (Num.+) Num.zero)
The product of the numbers in a list, same as (fold (Num.*) Num.one)
The minimal value of a non empty list, same as (foldl1 Ord.min)
The maximal value of a non empty list, same as (foldl1 Ord.max)
foldl1 is a variant of fold that has no starting value argument and thus must be applied to nonempty lists only.
scanl is similar to fold but returns a list of successive reduced values from the left:
scanl f z [x1, x2, ...] = [z, z `f` x1, (z `f` x1) `f` x2, ... ]
The following property holds for all finite lists xs:
last (scanl f z xs) == fold f z xs
scanl1 is similar to scanl, but takes the ListView.head of the list as starting element and is thus only applicable to non-empty lists.
scanl1 f [x1, x2, ...] = [x1, x1 `f` x2, (x1 `f` x2) `f` ...]
scanr is the right-to-left dual of scanl.
Note that
head (scanr f z xs) == foldr f z xs.
scanr1 is a variant of scanr that has no starting value argument.
Fold over a list from right to left.
foldr f a (x1:x2:x3:[])
is the same as
x1 `f` (x2 `f` (x3 `f` a))
Note that, if f is strict in the second argument, foldr f will need stack space proportional to the length of the list. But if f is lazy in it's second argument, foldr works on infinite lists.
If f is commutative, the list finite and laziness not an issue, fold may be the better choice since it runs with constant stack space. Otherwise, if f is not commutative, foldrs will trade time and heap space for stack space by folding the flipped f over the reversed list.
foldr1 is a variant of foldr that has no starting argument, and thus must be applied to a non-empty list
This function may be used in place of
foldr f z xs
if f is strict in its right operand and xs is a finite list, in cases where foldr exceeds the stack size, which is usually quite limited in the JVM.
foldrs will need extra CPU cycles and maybe (temporary) heap space for reverse-ing its list argument, before folding the flipped f over it.
If f is commutative, you may simply use fold instead.
The following property holds for all finite lists xs:
foldr f z xs == foldrs f z xs
Returns all but the last element from a list.
The following property holds for all non-empty finite lists /xs/:
init xs ++ [last xs] == xs
Returns the last element of a list by taking the ListView.head of the reversed list.
See also init
map f xs applies f to each element of xs and builds a new list from the results.
Usage of map is safe on infinite lists, it delivers the result list one by one as it is demanded.
reverses a list
splitAt n xs returns a tuple where first element is xs prefix of length n and the second element is the remainder of the list.
chunked n xs makes a list of chunks of xs with size n
n must be positive, otherwise an infinite list of [] is returned.
The following should hold:
n > 0 ==> concat (chunked n xs) == xs
takeWhile p xs takes leading elements from /xs/ while they satisfy the predicate /p/.
Example:
takeWhile (<7) [1,2,3,9,4] == [1,2,3]
dropWhile p xs drops leading elements from xs that satisfy the predicate p.
The following holds for all lists xs
takeWhile p xs ++ dropWhile p xs == xs
span p xs returns a tuple whose first element is the longest prefix of xs elements that satisfy p and whose second element is the remainder of the list.
span p xs == (takeWhile p xs, dropWhile p xs)
break, applied to a predicate /p/ and a list /xs/, returns a tuple where the first element is the longest prefix (possibly empty) of /xs/ elements that do not satisfy /p/ and the second element is the remainder of the list.
break p is equivalent to span (not • p).
e `elem` xs is true if and only if at least one of the elements of xs equals e.
opposite of elem
repeat a builds an infinite list where all elements are a.
iterate f a builds the infinite list [a, f a, f (f a), ...]
zip as bs builds a list of tuples of corresponding elements of /as/ and /bs/. Trailing elements of the longer list are ignored.
zip (1,2,3) "ab" = [(1, "a"), (2, "b")]
unzip turns a list of tuples into a tuple of lists. It is the opposite of zip and the following holds for genuine lists
(curry zip @ unzip) xs == xs
But note that
(unzip @ curry zip) (as, bs) == (as,bs)
will only hold if length as == length bs
zipWith f xs ys zips two lists with function f instead of the standard (,) that is used by zip
unzip3 unzips a list of triples and returns a triple of lists.
zipWith3 f zips 3 lists with function f instead of the standard (,,) that is used by zip3
intersperse a xs inserts a between every two elements of xs
intersperse 0 (1..3) == [1,0,2,0,3]
xs !! n is the element with index n of the list xs, where the head element of a list has index 0.
Concatenate two strings, uses Java's + operator
inherited from ListMonoid.concat
Concatenation of two lists
inherited from ListMonoid.concat
Singleton with element from Either.Right or empty list for Either.Left
Singleton with element from Maybe.Just or empty list for Maybe.Nothing
The list itself.
String viewed as list of Chars.
List functions on Strings can get quite expensive when the JVM implements substring via copying.
Consider StringIterator for an alternative
A polymorphic empty string.
This is the only string value whose type is not String that must ever exist.
inherited from ListView.head
The length of a String
true if and only if the length of the string is 0
inherited from ListView.tail
inherited from ListView.toList
drop n xs returns what remains from /xs/ after the /n/ leading elements have been dropped. If /n/ is greater than the ListView.length of /xs/, the result is the empty list.
For negative /n/, the result is undefined.
The following property holds for all lists /xs/ and non negative /n/:
take n xs ++ drop n xs == xs
the empty list
warning: head may fail
Get the length of a list
true for the empty list, false otherwise
warning: tail may fail
take n xs returns the starting sequence of xs with at most n elements. If n is greater than the ListView.length of xs, the result is xs.
For negative n, the result is undefined.
The following property holds for all lists xs and non negative n:
take n xs ++ drop n xs == xs
Access head and tail
inherited from Ord.<
inherited from Ord.<=
Function generated for derived instance.
inherited from Ord.>
inherited from Ord.>=
inherited from Ord.compare
inherited from Ord.max
inherited from Ord.min