Module

Data.SortedArray

Package: purescript-sorted-arrays
Repository: vladciobanu/purescript-sorted-arrays

SortedArray is a newtype wrapper on top of Array. You can construct a SortedArray by using the sort function provided in this module. The main benefit is being able to binary search through the array through elemIndex, elemLastIndex, findIndex, findLastIndex and filter.

A large number of functions from Data.Array were ported over since they just work. However, a few do not make sense (for example, insert at index). A few others take a SortedArray but must return an Array and are convenience functions for unwrapping and then applying the operation on the underlying Array.

SortedArray has the following instances: Eq, Eq1, Ord, Ord1 Foldable, Show, Semigroup and Monoid.

Please note that there is no Functor instance but there is a map function that returns an Array b.

#SortedArray Source

newtype SortedArray a

You can create SortedArrays by using the sort functions. You can get the underlying Array using unSortedArray.

Instances

(Ord a) => Semigroup (SortedArray a)
Comparison is done using <=, so the operation is left-biased with regards to EQ. This also means that the operation is commutative up to EQ.
(Ord a) => Monoid (SortedArray a)
(Eq a) => Eq (SortedArray a)
Eq1 SortedArray
(Ord a) => Ord (SortedArray a)
Ord1 SortedArray
Foldable SortedArray
(Show a) => Show (SortedArray a)

#unSortedArray Source

unSortedArray :: forall a. SortedArray a -> Array a

Unwraps to the inner Array.

#fromFoldable Source

fromFoldable :: forall a f. Foldable f => Ord a => f a -> SortedArray a

Unfold and sort a Foldable structure to a SortedArray.

#singleton Source

singleton :: forall a. a -> SortedArray a

Creates a singleton array which is by definition sorted.

#range Source

range :: Int -> Int -> SortedArray Int

Creates an array containing a range of integers, including the bounds.

#(..) Source

Operator alias for Data.SortedArray.range (non-associative / precedence 8)

Infix synonym for range.

#replicate Source

replicate :: forall a. Int -> a -> SortedArray a

Create a SortedArray with n copies of a value.

#null Source

null :: forall a. SortedArray a -> Boolean

Tests whether the array is empty.

#length Source

length :: forall a. SortedArray a -> Int

Gets the length of the array.

#cons Source

cons :: forall a. a -> SortedArray a -> Array a

Convenience function for adding an item at the beginning of the sorted array. The result is a plain Array. Use insert if you need the result to also be a SortedArray.

#(:) Source

Operator alias for Data.SortedArray.cons (non-associative / precedence 8)

Infix synonym for cons.

#snoc Source

snoc :: forall a. SortedArray a -> a -> Array a

Flipped version of cons.

#insert Source

insert :: forall a. Ord a => a -> SortedArray a -> SortedArray a

Insert an item in the sorted array. The array remains sorted. The item goes in the first position it can (so if they are duplicates, it will be the first item in that particular EQ group).

#head Source

head :: forall a. SortedArray a -> Maybe a

Gets the first item of the array, or Nothing if the array is empty.

#last Source

last :: forall a. SortedArray a -> Maybe a

Gets the last item of the array, or Nothing if the array is empty.

#tail Source

tail :: forall a. SortedArray a -> Maybe (SortedArray a)

Gets the rest of the array (all except the first item), or Nothing if the array is empty.

#init Source

init :: forall a. SortedArray a -> Maybe (SortedArray a)

Gets all the items in the array except the last item, or Nothing if the array is empty.

#uncons Source

uncons :: forall a. SortedArray a -> Maybe { head :: a, tail :: SortedArray a }

Deconstructs the array to a head and tail, or returns Nothing if the array is empty.

#unsnoc Source

unsnoc :: forall a. SortedArray a -> Maybe { init :: SortedArray a, last :: a }

Flipped version of uncons.

#index Source

index :: forall a. SortedArray a -> Int -> Maybe a

Gets the item at the specified index, or Nothing if it is out of bounds.

#(!!) Source

Operator alias for Data.SortedArray.index (non-associative / precedence 8)

Infix synonym for index.

#elemIndex Source

elemIndex :: forall a. Ord a => a -> SortedArray a -> Maybe Int

Finds the first index of the first occurrence of the provided item. Uses binary search.

#elemLastIndex Source

elemLastIndex :: forall a. Ord a => a -> SortedArray a -> Maybe Int

Finds the last index of the first occurrence of the provided item. Uses binary search.

#findIndex Source

findIndex :: forall a. Ord a => a -> SortedArray a -> Maybe Int

Finds the first index for which the provided compare function tests equal (EQ). Uses binary search.

#findLastIndex Source

findLastIndex :: forall a. Ord a => a -> SortedArray a -> Maybe Int

Finds the last index for which the provided compare function tests equal (EQ). Uses binary search.

#delete Source

delete :: forall a. Ord a => a -> SortedArray a -> SortedArray a

#deleteAt Source

deleteAt :: forall a. Int -> SortedArray a -> Maybe (SortedArray a)

Deletes item at index.

#filter Source

filter :: forall a. Ord a => a -> SortedArray a -> SortedArray a

Returns all items for which the provided compare function tests equal ('EQ'). Uses binary search.

#partition Source

partition :: forall a. (a -> Boolean) -> SortedArray a -> { no :: SortedArray a, yes :: SortedArray a }

Splits the array in two arrays depending on whether they test true or false for the provided predicate. Ordering is retained, so both arrays are still sorted.

#map Source

map :: forall b a. (a -> b) -> SortedArray a -> Array b

Functor-like convenience function, equivalent to unwrapping and applying the Array map.

#mapWithIndex Source

mapWithIndex :: forall b a. (Int -> a -> b) -> SortedArray a -> Array b

Apply function to each element, supplying a zero-based index. Result is a regular Array.

#sort Source

sort :: forall a. Ord a => Array a -> SortedArray a

Sort an array and wrap it as a SortedArray.

#slice Source

slice :: forall a. Int -> Int -> SortedArray a -> SortedArray a

Extracts a subarray by a start and end index.

#take Source

take :: forall a. Int -> SortedArray a -> SortedArray a

Creates a new array by taking the first n elements of the array.

#takeEnd Source

takeEnd :: forall a. Int -> SortedArray a -> SortedArray a

Creates a new array by taking the last n elements of the array.

#takeWhile Source

takeWhile :: forall a. (a -> Boolean) -> SortedArray a -> SortedArray a

Creates a new array by taking the longest subarray of items that satisfy the specified predicate.

#drop Source

drop :: forall a. Int -> SortedArray a -> SortedArray a

Creates a new array by skipping the first n elements of the array.

#dropEnd Source

dropEnd :: forall a. Int -> SortedArray a -> SortedArray a

Creates a new array by skipping the last n elements of the array.

#dropWhile Source

dropWhile :: forall a. (a -> Boolean) -> SortedArray a -> SortedArray a

Creates a new array by skipping the longest subarray of items that satisfy the specified predicate.

#span Source

span :: forall a. (a -> Boolean) -> SortedArray a -> { init :: SortedArray a, rest :: SortedArray a }

Splits an array into the longest initial subarray of elements that satisfy the specified predicate and the remaining elements.

#nub Source

nub :: forall a. Ord a => SortedArray a -> SortedArray a

Creates a new array that contains no duplicates.

#nubBy Source

nubBy :: forall a. (a -> a -> Ordering) -> SortedArray a -> SortedArray a

Creates a new array that contains no duplicates by using the specified equivalence relation.

Modules: Data.SortedArray