inflist-0.0.1: An infinite list type and operations thereon.

Maintainerjameshfisher@gmail.com
Safe HaskellSafe

Data.InfList

Contents

Description

This module provides an infinite list type and operations thereon.

Haskell has two outstanding features:

  • laziness, which in particular allows infinite data structures;
  • a very strong type system.

In that light, it's a bit embarrassing that its default libraries do not allow one to express the infinitude of, say, a list. For example, repeat has type a → [a], when it of course should not return a finite list.

This module defines an infinite list data structure and provides all the standard list-manipulating functions that make sense on them. The advantages of using this over a standard list are:

See for comparison the List and List modules.

Synopsis

Data type

data InfList a Source

The infinite list data type. This is identical to the normal list data type with the sole exception that it lacks the [] constructor.

Constructors

a ::: (InfList a)

Cons an element onto an infinite list to yield another infinite list.

Instances

Functor InfList

fmap is the same for InfList as for lists.

Eq a => Eq (InfList a)

Be careful. Equality causes non-termination.

Ord a => Ord (InfList a)

Be careful. Equality causes non-termination.

Show a => Show (InfList a)

An InfList looks the same as a list, with InfList prepended.

Arbitrary a => Arbitrary (InfList a) 

Type synonyms

type Pred a = a -> BoolSource

A simple type synonym for predicates.

Infinite-list producer replacements

iterateSource

Arguments

:: (a -> a)

the element-generating function

-> a

the initial element

-> InfList a

the infinite list of elements

Repeatedly apply a generating function on an initial value, generating an infinite list.

repeatSource

Arguments

:: a

The list element

-> InfList a

the infinite list where each element is that element

Given a list element, use that as every element in an infinite list.

cycleSource

Arguments

:: [a]

A non-empty finite list

-> InfList a

The elements of that list repeated infinitely

Repeat the elements of a non-empty finite list.

Operations on InfList

Accessors

headSource

Arguments

:: InfList a

the list

-> a

its first element

Get the first element of a list. This is guaranteed to exist.

tailSource

Arguments

:: InfList a

the list

-> InfList a

its tail

Get the tail of a list. This is guaranteed to exist.

Conversion to and from lists

toListSource

Arguments

:: InfList a

the InfList

-> [a]

the normal infinite list

Convert an InfList to an infinite list. Use sparingly.

fromListSource

Arguments

:: [a]

an infinite list

-> InfList a

the corresponding InfList

Convert an infinite list to an InfList. Throws an error if the given list runs out of elements. Use sparingly.

Maps

mapSource

Arguments

:: (a -> b)

an element mapping function

-> InfList a

a list of elements

-> InfList b

the result of applying the function to each list element

Apply a function to each element of the list, yielding a new list of the results.

mapAccumLSource

Arguments

:: (acc -> a -> (acc, b))

The mapping/accumulating function

-> acc

The initial accumulator

-> InfList a

An infinite list

-> InfList b

The mapped list

Applies a function to each element of a list, passing an accumulating parameter from left to right, returning a new list. This is not quite the same as mapAccumL: there is no final accumulator returned.

Folds

foldrSource

Arguments

:: (a -> b -> b)

A replacement for the ::: constructor

-> InfList a

The InfList to replace it in

-> b 

Catamorphism. This is not the same as foldr on lists, as it contains no base value.

unfoldrSource

Arguments

:: (a -> (b, a))

The unfolding function

-> a

The seed value

-> InfList b

The unfolded list

Build a list from a seed value. The iterating function takes the seed value and produces the next element in the list along with a new seed value to use for the next element. Not the same as unfoldr.

Concatenating, interspersing, glueing

intersperseSource

Arguments

:: a

The element to place between

-> InfList a

The list to intersperse

-> InfList a

The interspersed list

Place a given element between every adjacent two elements of a given infinite list.

intercalateSource

Arguments

:: [a]

The separating list

-> InfList [a]

The infinite list to intercalate

-> InfList a

The infinite list intercalated with the separating list

Given an infinite list of finite lists, intersperse the infinite list with a given finite list, and concatenate it.

(+++)Source

Arguments

:: [a]

a finite list

-> InfList a

an infinite list

-> InfList a

the finite list prepended to the infinite list

Prepend a finite list to a infinite list yielding a new infinite list.

concatMapSource

Arguments

:: (a -> [b])

the element expanding function

-> InfList a

a list of those elements

-> InfList b

the concatenation of the expansion of each element

Expand all elements of an infinite list into finite lists and concatenate them.

concatSource

Arguments

:: InfList [a]

The infinite list of finite lists

-> InfList a

The concatenated list

Concatenate an infinite list of finite lists into an infinite list of elements. That is, remove one level of nesting.

Splitting

splitAtSource

Arguments

:: Int

a natural number

-> InfList a

an infinite list

-> ([a], InfList a)

the list split at that index

Given a natural number, get a two-tuple of the finite list of that many elements from the start of a given infinite list, and the infinite list that follows them.

spanSource

Arguments

:: Pred a

a predicate on list elements

-> InfList a

a list of those elements

-> ([a], InfList a)

the longest satisfying prefix, and the rest

Split an infinite list into a longest prefix such that all the elements of it satisfy a given predicate, and the rest of the list following them.

breakSource

Arguments

:: Pred a

a predicate on list elements

-> InfList a

a list of those elements

-> ([a], InfList a)

the longest non-satisfying prefix, and the rest

Split an infinite list into a longest prefix such that all the elements of it do not satisfy a given predicate, and the rest of the list following them.

groupBySource

Arguments

:: (a -> a -> Bool)

a binary predicate on elements

-> InfList a

an infinite list of that element type

-> InfList [a]

maximal-length finite lists satisfying the predicate

Given a predicate over two elements, split an infinite list of elements of that type into maximal-length finite lists where each adjacent pair of elements in each list satisfies the predicate in that order.

In practise, the predicate is associative and commutative, e.g. an equality relation, as used in the group function.

groupSource

Arguments

:: Eq a 
=> InfList a

The list of elements

-> InfList [a]

The list of groups of equal elements

Given an infinite list, split it into maximal-length finite lists where every element in each list is equal.

partitionSource

Arguments

:: Pred a

A predicate on elements

-> InfList a

An infinite list of those elements

-> (InfList a, InfList a)

Those elements satisfying and not satisfying the predicate, respectively

Given a predicate and an infinite list, return a pair of infinite lists of elements which do and do not satisfy the predicate, respectively.

Prefixes and suffixes

isPrefixOfSource

Arguments

:: Eq a 
=> [a]

A finite list

-> InfList a

An infinite list

-> Bool

Whether the finite list is a prefix of the infinite list

Is a given finite list a prefix of a given infinite list?

stripPrefixSource

Arguments

:: Eq a 
=> [a]

the potential prefix

-> InfList a

the list to check the prefix of

-> Maybe (InfList a)

the rest of the list

Given a potential prefix of an infinite list, if the infinite list has that prefix, return just the rest of the infinite list; otherwise, return Nothing.

initsSource

Arguments

:: InfList a

A list to take prefixes of

-> InfList [a]

A list of prefixes in ascending order of length

List the prefixes of an infinite list in ascending order of length.

tailsSource

Arguments

:: InfList a

A list to take tails of

-> InfList (InfList a)

A list of tails of that list

List the tails of an infinite list in ascending order of distance from the head of the list.

takeSource

Arguments

:: Int

a natural number

-> InfList a

an infinite list

-> [a]

that many elements from the start of the infinite list

Given a natural number, return that many elements from the start of an infinite list.

dropSource

Arguments

:: Int

a natural number

-> InfList a

an infinite list

-> InfList a

the rest of the list after dropping that many elements

Given a natural number, drop that many elements from the start of an infinite list.

takeWhileSource

Arguments

:: Pred a

a predicate on list elements

-> InfList a

an infinite list

-> [a]

the satisfying prefix of that list

The longest prefix of an infinite list such that all elements of that prefix satisfy a given predicate.

dropWhileSource

Arguments

:: Pred a

a predicate on list elements

-> InfList a

an infinite list

-> InfList a

the rest of the list after satisfying elements are dropped

Remove the longest prefix of an infinite list where all elements of that prefix satisfy a given predicate.

Zip functions

zipSource

Arguments

:: InfList a

The first list

-> InfList b

The second list

-> InfList (a, b)

The zipped list

Zip two infinite lists into an infinite list of two-tuples, where `(a,b)` in the nth tuple are the nth elements of the first and second list respectively.

zip3 :: InfList a -> InfList b -> InfList c -> InfList (a, b, c)Source

zipWithSource

Arguments

:: (a -> b -> c)

the combining function

-> InfList a

the first list

-> InfList b

the second list

-> InfList c

the result list

Zip two infinite lists into a third list where the nth element of the third list is the result of applying a given function to the nth elements of the first and second lists.

zipWith3 :: (a -> b -> c -> d) -> InfList a -> InfList b -> InfList c -> InfList dSource

unzipSource

Arguments

:: InfList (a, b)

The infinite list of tuples

-> (InfList a, InfList b)

The tuple of infinite lists

Reverse the operation of zip. That is, given an infinite list of two-tuples, return a two-tuple of infinite lists where the nth element of the first list in the result is the first element of the nth tuple of the first list, and correspondingly for the second list in the result tuple.

unzip3 :: InfList (a, b, c) -> (InfList a, InfList b, InfList c)Source

Dropping and deleting of elements

filterSource

Arguments

:: Pred a

a predicate on list elements

-> InfList a

the list of elements

-> InfList a

all elements of the list that satisfy the predicate

Select the elements of a list that satisfy a predicate.

deleteBySource

Arguments

:: Eq a 
=> Pred a

A predicate on list elements

-> InfList a

A list of those elements

-> InfList a

The same list minus the first element satisfying the predicate

Delete the first element satisfying a given predicate. Notice that this is not the same as deleteBy.

deleteSource

Arguments

:: Eq a 
=> a

An element to compare to

-> InfList a

A list

-> InfList a

The same list minus the first element equal to the given element

Delete the first element equal to a given element.

Index functions

(!!!)Source

Arguments

:: InfList a

An infinite list of elements

-> Int

An index into that list

-> a

The element at that index

Given a natural number, get that the element at that index of a given infinite list.

findIndicesSource

Arguments

:: Pred a

a predicate on list elements

-> InfList a

a list of those elements

-> InfList Int

a list of indices of satisfying elements

Get the indices into an infinite list where each element at that index satisfies a given predicate.

elemIndicesSource

Arguments

:: Eq a 
=> a

An element to compare to

-> InfList a

An infinite list of elements

-> InfList Int

The indices into that list where the element is equal to the given element

Get the indices into an infinite list where each element at that index is equal to the given element.