Karya, built on Mon Jul 24 11:39:07 PDT 2017 (patch 33511aca01257b76b88de7c7a2763b7a965c084e)

Safe HaskellNone

Util.Seq

Contents

Synopsis

Documentation

type NonNull a = [a] Source #

This is just a list, but is documentation that a return value will never be null, or an argument should never be null. This is for cases where NonEmpty is too annoying to work with.

enumeration

enumerate :: [a] -> [(Int, a)] Source #

range :: (Num a, Ord.Ord a) => a -> a -> a -> [a] Source #

Enumerate an inclusive range. Uses multiplication instead of successive addition to avoid loss of precision.

Also it doesn't require an Enum instance.

range' :: (Num a, Ord.Ord a) => a -> a -> a -> [a] Source #

Enumerate a half-open range.

range_end :: (Num a, Ord.Ord a) => a -> a -> a -> [a] Source #

Like range, but always includes the end, even if it doesn't line up on a step.

range_ :: Num a => a -> a -> [a] Source #

Infinite range.

transformation

key_on :: (a -> k) -> [a] -> [(k, a)] Source #

key_on_just :: (a -> Maybe.Maybe k) -> [a] -> [(k, a)] Source #

first_last :: (a -> a) -> (a -> a) -> [a] -> [a] Source #

Apply a function to the first and last elements. Middle elements are unchanged. A null or singleton list is also unchanged.

map_maybe_snd :: (b -> Maybe.Maybe b') -> [(a, b)] -> [(a, b')] Source #

Filter on the snd values returning Just.

map_head :: (a -> a) -> [a] -> [a] Source #

map_tail :: (a -> a) -> [a] -> [a] Source #

map_init :: (a -> a) -> [a] -> [a] Source #

map_last :: (a -> a) -> [a] -> [a] Source #

permutations

cartesian :: [[a]] -> [[a]] Source #

The cartesian product of a list of lists. E.g. [[1, 2], [3, 4]] -> [[1, 3], [1, 4], [2, 3], [2, 4]].

indexing lists

at :: (Num i, Ord.Ord i) => [a] -> i -> Maybe.Maybe a Source #

Get xs !! n, but return Nothing if the index is out of range.

insert_at :: Int -> a -> [a] -> [a] Source #

Insert x into xs at index i. If i is out of range, insert at the beginning or end of the list.

remove_at :: Int -> [a] -> [a] Source #

Remove the element at the given index. Do nothing if the index is out of range.

take_at :: Int -> [a] -> Maybe.Maybe (a, [a]) Source #

Like remove_at but return the removed element as well.

modify_at :: Int -> (a -> a) -> [a] -> [a] Source #

Modify element at an index by applying a function to it. If the index is out of range, nothing happens.

find_modify :: (a -> Bool) -> (a -> a) -> [a] -> Maybe.Maybe [a] Source #

Find an element, then change it. Return Nothing if the element wasn't found.

update_at :: a -> Int -> (Maybe.Maybe a -> a) -> [a] -> [a] Source #

Similar to modify_at, but will insert an element for an out of range positive index. The list will be extended with deflt, and the modify function passed a Nothing.

move :: Int -> Int -> [a] -> Maybe.Maybe [a] Source #

Move an element from one index to another, or Nothing if the from index was out of range.

min / max

min_on :: Ord.Ord k => (a -> k) -> a -> a -> a Source #

max_on :: Ord.Ord k => (a -> k) -> a -> a -> a Source #

minimum_on :: Ord.Ord k => (a -> k) -> [a] -> Maybe.Maybe a Source #

maximum_on :: Ord.Ord k => (a -> k) -> [a] -> Maybe.Maybe a Source #

ordered lists

insert_on :: Ord.Ord k => (a -> k) -> a -> [a] -> [a] Source #

sort_on :: Ord.Ord k => (a -> k) -> [a] -> [a] Source #

Stable sort on a cheap key function.

reverse_sort_on :: Ord.Ord b => (a -> b) -> [a] -> [a] Source #

Like sort_on, but sort highest-to-lowest.

merge :: Ord.Ord a => [a] -> [a] -> [a] Source #

Merge sorted lists. If two elements compare equal, the one from the left list comes first.

merge_by :: (a -> a -> Ord.Ordering) -> [a] -> [a] -> [a] Source #

merge_on :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [a] Source #

merge_lists :: Ord.Ord k => (a -> k) -> [[a]] -> [a] Source #

merge_asc_lists :: Ord.Ord k => (a -> k) -> [[a]] -> [a] Source #

If the heads of the sublists are also sorted I can be lazy in the list of sublists too. This version is optimized for minimal overlap.

grouping

adjacent

group_adjacent :: Eq key => (a -> key) -> [a] -> [NonNull a] Source #

This is just groupBy except with a key function.

sort

keyed_group_sort Source #

Arguments

:: Ord.Ord key 
=> (a -> key) 
-> [a] 
-> [(key, NonNull a)]

Sorted by key. The NonNull group is in the same order as the input.

Group the unsorted list into (key x, xs) where all xs compare equal after key is applied to them.

group_fst :: Ord.Ord a => [(a, b)] -> [(a, NonNull b)] Source #

Similar to keyed_group_sort, but key on the fst element, and strip the key out of the groups.

group_snd :: Ord.Ord b => [(a, b)] -> [(NonNull a, b)] Source #

Like group_fst, but group on the snd element.

group_sort :: Ord.Ord key => (a -> key) -> [a] -> [NonNull a] Source #

Like groupBy, but the list doesn't need to be sorted, and use a key function instead of equality. The list is sorted by the key, and the groups appear in their original order in the input list.

stable

group_stable_with :: (a -> a -> Bool) -> [a] -> [NonEmpty a] Source #

Group each element with all the other elements that compare equal to it. The heads of the groups appear in their original order.

group_stable :: Eq key => (a -> key) -> [a] -> [NonEmpty a] Source #

group_stable_with but with a key function.

keyed_group_stable :: Eq key => (a -> key) -> [a] -> [(key, [a])] Source #

zipping

zip_next :: [a] -> [(a, Maybe.Maybe a)] Source #

Pair each element with the following element. The last element is paired with Nothing. Like zip xs (drop 1 xs ++ f (last xs)) but only traverses xs once.

zip_prev :: [a] -> [(Maybe.Maybe a, a)] Source #

zip_neighbors :: [a] -> [(Maybe.Maybe a, a, Maybe.Maybe a)] Source #

Like zip_next but with both preceding and following elements.

zip_remainder :: [a] -> [b] -> ([(a, b)], Either.Either [a] [b]) Source #

This is like zip, but it returns the remainder of the longer argument instead of discarding it.

data Paired a b Source #

Constructors

First !a 
Second !b 
Both !a !b 

Instances

(Eq b, Eq a) => Eq (Paired a b) # 

Methods

(==) :: Paired a b -> Paired a b -> Bool #

(/=) :: Paired a b -> Paired a b -> Bool #

(Show b, Show a) => Show (Paired a b) # 

Methods

showsPrec :: Int -> Paired a b -> ShowS #

show :: Paired a b -> String #

showList :: [Paired a b] -> ShowS #

(Pretty a, Pretty b) => Pretty (Paired a b) # 

Methods

pretty :: Paired a b -> Text Source #

format :: Paired a b -> Doc Source #

formatList :: [Paired a b] -> Doc Source #

partition_paired :: [Paired a b] -> ([a], [b]) Source #

zip_padded :: [a] -> [b] -> [Paired a b] Source #

Like zip, but emit Firsts or Seconds if the list lengths are unequal.

zip_padded_snd :: [a] -> [b] -> [(a, Maybe.Maybe b)] Source #

Like zip, but the second list is padded with Nothings.

zipper :: [a] -> [a] -> [([a], [a])] Source #

Return the reversed inits paired with the tails. This is like a zipper moving focus along the input list.

equal_pairs :: (a -> b -> Bool) -> [a] -> [b] -> [Paired a b] Source #

Pair a elements up with b elements. If they are equal according to the function, they'll both be Both in the result. If an a is deleted going from a to b, it will be First, and Second for b.

Kind of like an edit distance, or a diff.

indexed_pairs :: (a -> b -> Bool) -> [a] -> [b] -> [(Int, Paired a b)] Source #

This is like equal_pairs, except that the index of each pair in the right list is included. In other words, given (i, Second y), i is the position of y in the b list. Given (i, First x), i is where x was deleted from the b list.

indexed_pairs_on :: Eq k => (a -> k) -> [a] -> [a] -> [(Int, Paired a a)] Source #

pair_sorted :: Ord.Ord k => [(k, a)] -> [(k, b)] -> [(k, Paired a b)] Source #

Pair up two lists of sorted pairs by their first element.

pair_sorted_on :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [Paired a a] Source #

Like pair_sorted, but use a key function, and omit the extracted key.

pair_on :: Ord.Ord k => (a -> k) -> (b -> k) -> [a] -> [b] -> [Paired a b] Source #

Sort the lists on with the key functions, then pair them up.

pair_on1 :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [Paired a a] Source #

Like pair_on, but when the lists have the same type.

diff :: (a -> b -> Bool) -> [a] -> [b] -> [Either.Either a b] Source #

Left if the val was in the left list but not the right, Right for the converse.

partition

partition2 :: (a -> Bool) -> (a -> Bool) -> [a] -> ([a], [a], [a]) Source #

Like partition, but partition by two functions consecutively.

partition_with :: (a -> Maybe.Maybe b) -> [a] -> ([b], [a]) Source #

sublists

chunked :: Int -> [a] -> [[a]] Source #

Split into groups of a certain size.

rotate :: [[a]] -> [[a]] Source #

Take a list of rows to a list of columns. Similar to zip, the result is trimmed to the length of the shortest row.

rotate2 :: [[a]] -> [[Maybe.Maybe a]] Source #

Similar to rotate, except that the result is the length of the longest row and missing columns are Nothing.

extracting sublists

head :: [a] -> Maybe.Maybe a Source #

Total variants of unsafe list operations.

last :: [a] -> Maybe.Maybe a Source #

Total variants of unsafe list operations.

tail :: [a] -> Maybe.Maybe [a] Source #

drop_dups :: Eq k => (a -> k) -> [a] -> [a] Source #

Drop adjacent elts if they are equal after applying the key function. The first elt is kept.

drop_with :: (a -> a -> Bool) -> [a] -> [a] Source #

Filter out elts when the predicate is true for adjacent elts. The first elt is kept, and the later ones are dropped. This is like drop_dups except it can compare two elements. E.g. drop_with (>=) will ensure the sequence is increasing.

partition_dups Source #

Arguments

:: Ord.Ord k 
=> (a -> k) 
-> [a] 
-> ([a], [(a, NonNull a)])

([unique], [(used_for_unique, [dups])])

Like drop_dups, but return the dropped values.

drop_initial_dups :: Eq k => (a -> k) -> [a] -> [a] Source #

Like drop_dups, but keep the last adjacent equal elt instead of the first.

unique :: Ord.Ord a => [a] -> [a] Source #

unique_on :: Ord.Ord k => (a -> k) -> [a] -> [a] Source #

This is like drop_dups, except that it's not limited to just adjacent elts. The output list is in the same order as the input.

unique_sort :: Ord.Ord a => [a] -> [a] Source #

Like unique, but sort the list, and should be more efficient.

rtake :: Int -> [a] -> [a] Source #

rtake_while :: (a -> Bool) -> [a] -> [a] Source #

rdrop :: Int -> [a] -> [a] Source #

rdrop_while :: (a -> Bool) -> [a] -> [a] Source #

drop_prefix :: Eq a => [a] -> [a] -> ([a], Bool) Source #

If the list doesn't have the given prefix, return the original list and False. Otherwise, strip it off and return True.

drop_suffix :: Eq a => [a] -> [a] -> ([a], Bool) Source #

span and break

break_tails :: ([a] -> Bool) -> [a] -> ([a], [a]) Source #

Like break, but the called function has access to the entire tail.

span_end :: (a -> Bool) -> [a] -> ([a], [a]) Source #

span from the end of the list.

span_while :: (a -> Maybe.Maybe b) -> [a] -> ([b], [a]) Source #

Like span, but it can transform the spanned sublist.

span_end_while :: (a -> Maybe.Maybe b) -> [a] -> ([a], [b]) Source #

span_while from the end of the list.

viewr :: [a] -> Maybe.Maybe ([a], a) Source #

List initial and final element, if any.

ne_viewr :: NonEmpty a -> ([a], a) Source #

split and join

split_with :: (a -> Bool) -> [a] -> [[a]] Source #

Split xs before places where f matches.

split_with (==1) [1,2,1]
--> [[], [1, 2], [1]]

split :: Eq a => NonNull a -> [a] -> NonNull [a] Source #

Split xs on sep, dropping sep from the result.

split_null :: Eq a => NonNull a -> [a] -> [[a]] Source #

Like split, but it returns [] if the input was null.

split1 :: Eq a => NonNull a -> [a] -> ([a], [a]) Source #

Like split, but only split once.

join :: Monoid a => a -> [a] -> a Source #

Interspense a separator and concat.

join2 :: (Monoid a, Eq a) => a -> a -> a -> a Source #

Binary join, but the separator is only used if both joinees are non-empty.

split_between :: (a -> a -> Bool) -> [a] -> [[a]] Source #

Split the list on the points where the given function returns true.

This is similar to groupBy, except this is defined to compare adjacent elements. groupBy actually compares to the first element of each group. E.g. you can't group numeric runs with groupBy (a b -> b > a+1).

break_between :: (a -> a -> Bool) -> [a] -> ([a], [a]) Source #

replace

replace :: Eq a => [a] -> [a] -> [a] -> [a] Source #

Replace sublist from with to in the given list.

replace1 :: Eq a => a -> [a] -> [a] -> [a] Source #

Replace occurrances of an element with zero or more other elements.

search

count :: Foldable t => (a -> Bool) -> t a -> Int Source #

monadic

mapAccumLM :: Monad m => (state -> x -> m (state, y)) -> state -> [x] -> m (state, [y]) Source #

Like mapAccumL, but monadic.