Package frege.prelude.PreludeList

Compiled: Tue Dec 04 23:59:58 PST 2012 from source file: frege/prelude/PreludeList.fr

Package Documentation

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:

Empty
provides Empty.null to test for empty containers and Empty.empty to create one.
ListLike
provides ListLike.length, ListLike.head, ListLike.tail and ListLike.++
ListSource
is the type class for types that can be converted to lists (ListSource.toList). There are instances for String, Maybe, Either and arrays.

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.

Table of Content

Imports

Classes

class Empty c

A class for containers/collections that have an empty value.

Known Instances

[], StringJ

Member Functions

empty :: Empty c => c e

the empty container

null :: Empty c => c e -> Bool

true if and only if the container is Empty.empty

class ListLike Empty list => list

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.

Known Instances

[], StringJ

Member Functions

++ :: ListLike list => list e -> list e -> list e

concatenate two lists, strings or whatever

> empty ++ x == x && x ++ empty == x

head :: ListLike list => list elem -> elem

Get the element at the head of a non empty list, otherwise undefined

length :: ListLike list => list elem -> Int

computes the length of a list in a type dependend way

tail :: ListLike list => list elem -> list elem

Get the tail elements. This is undefined if the list is empty.

class ListSource t

A class for things we can make a list from

Known Instances

StringJ, [], Either, Maybe

Member Functions

toList :: ListSource t => t e -> [e]

converts the value to a list

Instances

instance ListLike StringJ

Member Functions

++ :: StringJ a -> StringJ a -> StringJ a
pure native +

Concatenate two strings, uses Java's + operator

empty :: StringJ α
pure native frege.RT.emptyString

A polymorphic empty string.

This is the only string value whose type is not String that must ever exist.

head :: StringJ α -> α

The first element of a String or undefined if the string is empty.

length :: StringJ a -> Int
pure native length

The length of a String

null :: StringJ α -> Bool

true if and only if the length of the string is 0

tail :: StringJ α -> StringJ α

The tail of a String or undefined if it is empty

instance ListLike []

Member Functions

++ :: [α] -> [α] -> [α]

Concatenation of 2 lists

empty :: [α]

the empty list

head :: [α] -> α

The first element of a list or undefined if it is empty.

length :: [α] -> Int

Get the length of a list

null :: [α] -> Bool

true for the empty list, false otherwise

tail :: [α] -> [α]

The tail of a list or undefined if it is empty

instance ListSource Either l

Member Functions

toList :: Either α β -> [β]

Singleton with element from Either.Right or empty list for Either.Left

instance ListSource Maybe

Member Functions

toList :: Maybe α -> [α]

Singleton with element from Maybe.Just or empty list for Maybe.Nothing

instance ListSource StringJ

Member Functions

toList :: StringJ α -> [α]

List of characters, computed lazily in contrast to unpacked

instance ListSource []

Member Functions

toList :: [α] -> [α]

The list itself.

instance Ord Ord a => [a]

Member Functions

< :: Ord α => [α] -> [α] -> Bool

inherited from Ord.<

<= :: Ord α => [α] -> [α] -> Bool

inherited from Ord.<=

<=> :: Ord α => [α] -> [α] -> Ordering

Function generated for derived istance.

> :: Ord α => [α] -> [α] -> Bool

inherited from Ord.>

>= :: Ord α => [α] -> [α] -> Bool

inherited from Ord.>=

compare :: Ord α => [α] -> [α] -> Ordering

inherited from Ord.compare

max :: Ord α => [α] -> [α] -> [α]

inherited from Ord.max

min :: Ord α => [α] -> [α] -> [α]

inherited from Ord.min

Functions and Values

all :: (α->Bool) -> [α] -> Bool

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 :: [Bool] -> Bool

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 :: (α->Bool) -> [α] -> Bool

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 :: (α->Bool) -> [α] -> ([α], [α])

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 :: ListLike α => [α β] -> α β

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.

concatMap :: ListLike β => (γ->β α) -> [γ] -> β α

Map a function over a list and concatenate the list or string results.

cycle :: [a] -> [a]

cycle xs builds a value that is an infinite repetition of /xs/, which must not be empty.

drop :: Int -> [α] -> [α]

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 :: (α->Bool) -> [α] -> [α]

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
elem :: Eq α => α -> [α] -> Bool

e `elem` xs is true if and only if at least one of the elements of /xs/ equals /e/.

filter :: (α->Bool) -> [α] -> [α]

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 :: (α->β->α) -> α -> [β] -> α

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 :: (α->β->α) -> α -> [β] -> α

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 :: (α->α->α) -> [α] -> α

foldl1 is a variant of fold that has no starting value argument and thus must be applied to nonempty lists only.

foldr :: (α->β->β) -> β -> [α] -> β

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 :: (α->α->α) -> [α] -> α

foldr1 is a variant of foldr that has no starting argument, and thus must be applied to a non-empty list

foldrs :: (α->β->β) -> β -> [α] -> β

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
init :: [α] -> [α]

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 :: α -> [α] -> [α]

intersperse a xs inserts /a/ between every two elements of /xs/

 intersperse 0 (1..3) == [1,0,2,0,3]
iterate :: (α->α) -> α -> [α]

iterate f a builds the infinite list [a, f a, f (f a), ...]

last :: [α] -> α

Returns the last element of a list by taking the ListLike.head of the reversed list.

See also init

map :: (α->β) -> [α] -> [β]

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.

maximum :: Ord α => [α] -> α

The maximal value of a non empty list, same as (foldl1 Ord.max)

minimum :: Ord α => [α] -> α

The minimal value of a non empty list, same as (foldl1 Ord.min)

notElem :: Eq α => α -> [α] -> Bool

opposite of elem

or :: [Bool] -> Bool

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.

packed :: [Char] -> String

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.

product :: Num α => [α] -> α

The product of the numbers in a list, same as (fold (Num.*) Num.one)

repeat :: α -> [α]

repeat a builds an infinite list where all elements are /a/.

replicate :: Int -> α -> [α]
reverse :: [α] -> [α]

reverses a list

scanl :: (α->β->α) -> α -> [β] -> [α]

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

In contrast to fold, scanl can operate on infinite lists.

scanl1 :: (α->α->α) -> [α] -> [α]

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 :: (α->β->β) -> β -> [α] -> [β]

scanr is the right-to-left dual of scanl.

Note that

> head (scanr f z xs) == foldr f z xs.

scanr1 :: (α->α->α) -> [α] -> [α]

scanr1 is a variant of scanr that has no starting value argument.

span :: (α->Bool) -> [α] -> ([α], [α])

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 :: Int -> [α] -> ([α], [α])

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 :: StringJ α -> Int -> StringJ α

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.

sum :: Num α => [α] -> α

The sum of the numbers in a list, same as (fold (Num.+) Num.zero)

take :: Int -> [α] -> [α]

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 :: (α->Bool) -> [α] -> [α]

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]
unpacked :: String -> [Char]

Eagerly converts a String to a list.

unzip :: [(α, β)] -> ([α], [β])

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 :: [(β, α, γ)] -> ([β], [α], [γ])

unzip3 unzips a list of triples and returns a triple of lists.

zip :: [α] -> [β] -> [(α, β)]

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")]
zip3 :: [β] -> [α] -> [γ] -> [(β, α, γ)]

zip3 zips 3 lists in the same way as zip does it.

zipWith :: (α->γ->β) -> [α] -> [γ] -> [β]

zipWith f xs ys zips two lists with function /f/ instead of the standard (,) that is used by zip

zipWith3 :: (β->α->δ->γ) -> [β] -> [α] -> [δ] -> [γ]

zipWith3 /f/ zips 3 lists with function /f/ instead of the standard (,,) that is used by zip3

Functions and Values by Type

String -> [Char]

unpacked

[Bool] -> Bool

and, or

[Char] -> String

packed

(α->α->α) -> [α] -> [α]

scanl1, scanr1

(α->α->α) -> [α] -> α

foldl1, foldr1

(α->Bool) -> [α] -> ([α], [α])

break, span

(α->Bool) -> [α] -> [α]

dropWhile, filter, takeWhile

(α->Bool) -> [α] -> Bool

all, any

(α->α) -> α -> [α]

iterate

Maybe α -> [α]

ListSource_Maybe.toList

StringJ α -> Int -> StringJ α

strhead

StringJ α -> StringJ α

ListLike_StringJ.tail

StringJ α -> [α]

ListSource_StringJ.toList

StringJ α -> Bool

ListLike_StringJ.null

StringJ α -> α

ListLike_StringJ.head

[a] -> [a]

cycle

[α] -> [α] -> [α]

ListLike_[].++

[α] -> [α]

init, reverse, ListLike_[].tail, ListSource_[].toList

[α] -> Bool

ListLike_[].null

[α] -> Int

ListLike_[].length

[α] -> α

last, ListLike_[].head

Int -> [α] -> ([α], [α])

splitAt

Int -> [α] -> [α]

drop, take

Int -> α -> [α]

replicate

α -> [α] -> [α]

intersperse

α -> [α]

repeat

Eq α => α -> [α] -> Bool

elem, notElem

Num α => [α] -> α

product, sum

Ord α => [α] -> [α] -> [α]

Ord_[].max, Ord_[].min

Ord α => [α] -> [α] -> Bool

Ord_[].>, Ord_[].<=, Ord_[].<, Ord_[].>=

Ord α => [α] -> [α] -> Ordering

Ord_[].<=>, Ord_[].compare

Ord α => [α] -> α

maximum, minimum

StringJ α

ListLike_StringJ.empty

[α]

ListLike_[].empty

(α->β->α) -> α -> [β] -> [α]

scanl

(α->β->α) -> α -> [β] -> α

fold, foldl

(α->β->β) -> β -> [α] -> [β]

scanr

(α->β->β) -> β -> [α] -> β

foldr, foldrs

(α->β) -> [α] -> [β]

map

Either α β -> [β]

ListSource_Either.toList

[(α, β)] -> ([α], [β])

unzip

[α] -> [β] -> [(α, β)]

zip

Empty c => c e -> Bool

Empty.null

ListLike list => list e -> list e -> list e

ListLike.++

ListLike list => list elem -> list elem

ListLike.tail

ListLike list => list elem -> Int

ListLike.length

ListLike list => list elem -> elem

ListLike.head

ListLike α => [α β] -> α β

concat

ListSource t => t e -> [e]

ListSource.toList

Empty c => c e

Empty.empty

(α->γ->β) -> [α] -> [γ] -> [β]

zipWith

[(β, α, γ)] -> ([β], [α], [γ])

unzip3

[β] -> [α] -> [γ] -> [(β, α, γ)]

zip3

ListLike β => (γ->β α) -> [γ] -> β α

concatMap

(β->α->δ->γ) -> [β] -> [α] -> [δ] -> [γ]

zipWith3

Valid HTML 4.01 Strict