Compiled: Tue Dec 04 23:59:58 PST 2012 from source file: frege/prelude/PreludeList.fr
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, which has 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:
The functions words and lines take String arguments and return lists of String, whereas unwords and unlines take an instance of ListSource with String elements and return a single String.
This package 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 Empty.empty
A class for data types that can be viewed as list.
Such data types are instances of Empty and support ListLike.head, ListLike.tail, ListLike.length and concatenation (ListLike.++)
This class provides no means to construct a list.
concatenate two lists, strings or whatever
> empty ++ x == x && x ++ empty == x
Get the element at the head of a non empty list, otherwise undefined
computes the length of a list in a type dependend way
Get the tail elements. This is undefined if the list is empty.
A class for things we can make a list from
converts the value to a list
Concatenate two strings, uses Java's + operator
A polymorphic empty string.
This is the only string value whose type is not String that must ever exist.
The first element of a String or undefined if the string is empty.
The length of a String
true if and only if the length of the string is 0
The tail of a String or undefined if it is empty
Concatenation of 2 lists
the empty list
The first element of a list or undefined if it is empty.
Get the length of a list
true for the empty list, false otherwise
The tail of a list or undefined if it is empty
Singleton with element from Either.Right or empty list for Either.Left
Singleton with element from Maybe.Just or empty list for Maybe.Nothing
List of characters, computed lazily in contrast to unpacked
The list itself.
inherited from Ord.<
inherited from Ord.<=
Function generated for derived istance.
inherited from Ord.>
inherited from Ord.>=
inherited from Ord.compare
inherited from Ord.max
inherited from Ord.min
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.
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.
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.
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).
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.
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.
drop n xs returns what remains from /xs/ after the /n/ leading elements have been dropped. If /n/ is greater than the ListLike.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
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
e `elem` xs is true if and only if at least one of the elements of /xs/ equals /e/.
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 element with the property asked for is found. For example
filter (==true) (repeat false)
will loop forever, whereas
filter iseven (iterate succ 1n) where iseven n = n `band` 1n == 0n
will faithfully deliver the list of positive integers that are divisible by 2, one by one.
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.
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 strogly suggested.
This function exists merely for compatibility with Haskell.
foldl1 is a variant of fold that has no starting value argument and thus must be applied to nonempty lists only.
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 lazyness 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
intersperse a xs inserts /a/ between every two elements of /xs/
intersperse 0 (1..3) == [1,0,2,0,3]
iterate f a builds the infinite list [a, f a, f (f a), ...]
Returns the last element of a list by taking the ListLike.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.
The maximal value of a non empty list, same as (foldl1 Ord.max)
The minimal value of a non empty list, same as (foldl1 Ord.min)
opposite of elem
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.
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.
The product of the numbers in a list, same as (fold (Num.*) Num.one)
repeat a builds an infinite list where all elements are /a/.
reverses a list
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 follwoing property holds for all finite lists /xs/:
last (scanl f z xs) == fold f z xs
scanl1 is similar to scanl, but takes the ListLike.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.
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)
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.
strhead s n returns the initial portion of s with at most n characters. if s.ListLike.length is lower than n, only so much characters are returned.
The sum of the numbers in a list, same as (fold (Num.+) Num.zero)
take n xs returns the starting sequence of /xs/ with at most /n/ elements. If /n/ is greater than the ListLike.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
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]
Eagerly converts a String to a list.
unzip turns a list of tuples into a tuple of lists. It is the opposite of zip and the follwoing 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
unzip3 unzips a list of triples and returns a triple of lists.
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")]
zipWith f xs ys zips two lists with function /f/ instead of the standard (,) that is used by zip
zipWith3 /f/ zips 3 lists with function /f/ instead of the standard (,,) that is used by zip3