Module Prelude.PreludeList

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:

ListEmpty
provides ListEmpty.null to test for empty containers and ListEmpty.empty to create one.
ListSemigroup
introduces the ListSemigroup.++ operator.
ListMonoid
is the union of the previous two.
ListView
provides ListView.length, and introduces ListView.uncons, a safe operation to split a list-view into ListView.head and ListView.tail.
ListSource
is the type class for types that can be converted to lists (ListSource.toList). There are instances for String, Maybe, Either and arrays.

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.

Imports

Table of Content

Definitions

class ListEmpty α

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

Known Instances

StringJ, []

Member Functions

emptyListEmpty α ⇒ α β

the empty container

nullListEmpty α ⇒ α β → Bool

true if and only if the container is ListEmpty.empty

class (ListSemigroup α, ListEmpty α) ⇒ ListMonoid α

A class for types that support the (++) operator.

Known Instances

[], StringJ

Member Functions

concatListMonoid α ⇒ [α β] → α β

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.

class ListSemigroup α

A class for types that support ListMonoid.concat

Known Instances

[], StringJ

Member Functions

++ListSemigroup α ⇒ α β → α β → α β
infixr  13

concatenate two lists, strings or whatever

 empty ++ x == x && x ++ empty == x   
class (ListSource c, ListEmpty c) ⇒ ListView c

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.

Known Instances

StringJ, []

Member Functions

dropListView c ⇒ Int → c e → c e

drop a number of initial elements

headListView c ⇒ c e → e

The first element of a list-view, or undefined if ListEmpty.empty

lengthListView c ⇒ c e → Int

computes the length of the container in a type dependent way

tailListView c ⇒ c e → c e

The tail of a list-view, or undefined if ListEmpty.empty

takeListView c ⇒ Int → c e → c e

take a number of initial elements

toListListView c ⇒ c β → [β]

converts a list-view to a list

unconsListView c ⇒ c e → Maybe (e, c e)

split the input stream in head and tail

class ListSource α

A class of things we can make a list from

Known Instances

StringJ, [], Maybe, Either

Member Functions

toListListSource α ⇒ α β → [β]

converts the value to a list

unpackedString → [Char]

Eagerly converts a String to a 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.

strheadStringJ αIntStringJ α

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[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.

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.

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.

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.

concatMapListMonoid γ ⇒ (α→γ β) → [α] → γ β

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

cycle[α] → [α]

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

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/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.

foldl ∷ (α→β→α) → α → [β] → α

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

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.

sumNum α ⇒ [α] → α

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

productNum α ⇒ [α] → α

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

minimumOrd α ⇒ [α] → α

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

maximumOrd α ⇒ [α] → α

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

foldl1 ∷ (α→α→α) → [α] → α

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

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 following 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 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 ∷ (α → β → β) → β → [α] → [β]

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.

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

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   
last[α] → α

Returns the last element of a list by taking the ListView.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.

reverse[α] → [α]

reverses a list

splitAtListView β ⇒ 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.

chunkedInt[α] → [[α]]

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 ∷ (α→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]
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
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)
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).

elemEq α ⇒ α → [α]Bool
infix  9

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

notElemEq α ⇒ α → [α]Bool
infix  9

opposite of elem

repeat ∷ α → [α]

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

replicateInt → α → [α]
iterate ∷ (α→α) → α → [α]

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

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")]
unzip[(β, α)] → ([β], [α])

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 ∷ (β→α→γ) → [β][α] → [γ]

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

zip3[β][α][γ] → [(β, α, γ)]

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

unzip3[(β, α, γ)] → ([β], [α], [γ])

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

zipWith3 ∷ (γ→α→β→δ) → [γ][α][β] → [δ]

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

intersperse ∷ α → [α] → [α]

intersperse a xs inserts a between every two elements of xs

 intersperse 0 (1..3) == [1,0,2,0,3]

Instances

instance ListMonoid StringJ

Member Functions

++StringJ aStringJ aStringJ a
pure native +
infixr  13

Concatenate two strings, uses Java's + operator

concat[StringJ α]StringJ α

inherited from ListMonoid.concat

instance ListMonoid []

Member Functions

++[α] → [α] → [α]
infixr  13

Concatenation of two lists

concat[[α]] → [α]

inherited from ListMonoid.concat

instance ListSource (Either α)

Member Functions

toList(α | β) → [β]

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

instance ListSource Maybe

Member Functions

toListMaybe α → [α]

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

instance ListSource []

Member Functions

toList[α] → [α]

The list itself.

instance ListView StringJ

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

Member Functions

dropIntStringJ αStringJ α
emptyStringJ α
pure native frege.runtime.Runtime.emptyString

A polymorphic empty string.

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

headStringJ α → α

inherited from ListView.head

lengthStringJ aInt
pure native length

The length of a String

nullStringJ αBool

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

tailStringJ αStringJ α

inherited from ListView.tail

takeIntStringJ αStringJ α
toListStringJ α → [α]

inherited from ListView.toList

unconsStringJ αMaybe (α, StringJ α)
instance ListView []

Member Functions

dropInt → [α] → [α]

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
empty ∷ [α]

the empty list

head[α] → α

warning: head may fail

length[α]Int

Get the length of a list

null[α]Bool

true for the empty list, false otherwise

tail[α] → [α]

warning: tail may fail

takeInt → [α] → [α]

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
uncons[α]Maybe (α, [α])

Access head and tail

instance Ord a ⇒ Ord [a]

Member Functions

<Ord α ⇒ [α][α]Bool
infix  9

inherited from Ord.<

<=Ord α ⇒ [α][α]Bool
infix  9

inherited from Ord.<=

<=>Ord α ⇒ [α][α]Ordering
infix  8

Function generated for derived instance.

>Ord α ⇒ [α][α]Bool
infix  9

inherited from Ord.>

>=Ord α ⇒ [α][α]Bool
infix  9

inherited from Ord.>=

compareOrd α ⇒ [α][α]Ordering
infix  8

inherited from Ord.compare

maxOrd α ⇒ [α][α] → [α]

inherited from Ord.max

minOrd α ⇒ [α][α] → [α]

inherited from Ord.min

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 α → IntStringJ α

strhead

StringJ α → Maybe (α, StringJ α)

ListView_StringJ.uncons

StringJ α → StringJ α

ListView_StringJ.tail

StringJ α → [α]

ListView_StringJ.toList

StringJ α → Bool

ListView_StringJ.null

StringJ α → α

ListView_StringJ.head

[StringJ α] → StringJ α

ListMonoid_StringJ.concat

[[α]] → [α]

ListMonoid_[].concat

[α] → [α] → [α]

ListMonoid_[].++

[α] → Maybe (α, [α])

ListView_[].uncons

[α] → [α]

cycle, init, reverse, ListSource_[].toList, ListView_[].tail

[α] → Bool

ListView_[].null

[α] → Int

ListView_[].length

[α] → α

last, ListView_[].head

IntStringJ α → StringJ α

ListView_StringJ.drop, ListView_StringJ.take

Int → [α] → [[α]]

chunked

Int → [α] → [α]

ListView_[].take, ListView_[].drop

Int → α → [α]

replicate

α → [α] → [α]

intersperse

α → [α]

repeat

Eq α ⇒ α → [α] → Bool

elem, notElem

Num α ⇒ [α] → α

product, sum

Ord α ⇒ [α] → [α] → [α]

Ord_[].min, Ord_[].max

Ord α ⇒ [α] → [α] → Bool

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

Ord α ⇒ [α] → [α] → Ordering

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

Ord α ⇒ [α] → α

maximum, minimum

StringJ α

ListView_StringJ.empty

[α]

ListView_[].empty

(α → β → β) → β → [α] → [β]

scanr

(α→β→α) → α → [β] → α

fold, foldl

(α→β→β) → β → [α] → β

foldr, foldrs

(β→α→β) → β → [α] → [β]

scanl

(β→α) → [β] → [α]

map

(α | β) → [β]

ListSource_Either.toList

[(β, α)] → ([β], [α])

unzip

[β] → [α] → [(β, α)]

zip

ListEmpty α ⇒ α β → Bool

ListEmpty.null

ListMonoid α ⇒ [α β] → α β

ListMonoid.concat

ListSemigroup α ⇒ α β → α β → α β

ListSemigroup.++

ListSource α ⇒ α β → [β]

ListSource.toList

ListView c ⇒ c e → Maybe (e, c e)

ListView.uncons

ListView c ⇒ c e → c e

ListView.tail

ListView c ⇒ c e → Int

ListView.length

ListView c ⇒ c e → e

ListView.head

ListView c ⇒ c β → [β]

ListView.toList

ListView c ⇒ Int → c e → c e

ListView.take, ListView.drop

ListView β ⇒ Int → β α → (β α, β α)

splitAt

ListEmpty α ⇒ α β

ListEmpty.empty

(β→α→γ) → [β] → [α] → [γ]

zipWith

[(β, α, γ)] → ([β], [α], [γ])

unzip3

[β] → [α] → [γ] → [(β, α, γ)]

zip3

ListMonoid γ ⇒ (α→γ β) → [α] → γ β

concatMap

(γ→α→β→δ) → [γ] → [α] → [β] → [δ]

zipWith3

Valid HTML 4.01 Strict