Karya, built on 2022-03-21T01:30:44 (patch 89d1651424c35e564138d93424a157ff87457245)

Util.Seq

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_snd :: (a -> k) -> [a] -> [(a, k)] 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_fst :: (a -> Maybe.Maybe a2) -> [(a, b)] -> [(a2, b)] Source #

Filter on the fst values returning Just.

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

Filter on the snd values returning Just.

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

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

map_head_tail :: (a -> b) -> (a -> b) -> [a] -> [b] Source #

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

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

scanl_on :: (accum -> key -> accum) -> (a -> key) -> accum -> [a] -> [(accum, a)] Source #

This is like scanl, but you can scan with a key function. E.g. to accumulate line lengths: scanl_on length (+) 0.

# 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 :: [a] -> Int -> 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. Different from List.sortOn, which is for an expensive 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

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

This is just List.groupBy except with a key function.

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

Like group_adjacent, but include the key.

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

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

## sort

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 List.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 ++ [Nothing]) but only traverses xs once.

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

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

Instances details
 Source # Instance detailsDefined in Util.Seq Methodsbimap :: (a -> b) -> (c -> d) -> Paired a c -> Paired b d #first :: (a -> b) -> Paired a c -> Paired b c #second :: (b -> c) -> Paired a b -> Paired a c # (Show a, Show b) => Show (Paired a b) Source # Instance detailsDefined in Util.Seq MethodsshowsPrec :: Int -> Paired a b -> ShowS #show :: Paired a b -> String #showList :: [Paired a b] -> ShowS # (Eq a, Eq b) => Eq (Paired a b) Source # Instance detailsDefined in Util.Seq Methods(==) :: Paired a b -> Paired a b -> Bool #(/=) :: Paired a b -> Paired a b -> Bool # (Pretty a, Pretty b) => Pretty (Paired a b) Source # Instance detailsDefined in Util.Pretty Methodspretty :: 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_fst :: [a] -> [b] -> [(Maybe.Maybe a, b)] Source #

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

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.

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

Perform a Meyes diff.

diff_either :: (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.

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

This is like diff, except that the index of each pair in the right list is included. So the index is where you should delete or add the element to turn as into bs:

• (i, Second b), i is the position of b in bs.
• (i, First a), i is where a was deleted from bs.

diff_index_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_on1 :: 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_sorted_on :: Ord.Ord k => (a -> k) -> (b -> k) -> [a] -> [b] -> [Paired a b] 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.

# partition

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

Like List.partition, but partition by two functions consecutively.

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

Partition and transform at the same time.

# 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. This is like a zip except for variable-length lists. Similar to zip, the result is trimmed to the length of the shortest row.

List.transpose is similar, but it skips missing elements, instead of truncating all to the shortest. Skipping means you lose what column the element came from.

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. Analogous to zip_padded.

## 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_before :: Ord.Ord key => (a -> key) -> key -> [a] -> [a] Source #

Drop until the last element before or equal to the given element.

takeWhileS :: state -> (state -> a -> Maybe.Maybe state) -> [a] -> [a] Source #

takeWhile with state.

## duplicates

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.

Arguments

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

Sort the input by the key, extract unique values, and also return the duplicates.

find_dups :: Ord.Ord k => (a -> k) -> [a] -> [(a, NonEmpty a)] Source #

Find duplicate values. There are always at least 2 of each output.

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.

## right variants

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

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

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

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

The same as List.dropWhileEnd except I also have all the other from-end variants.

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. List.stripPrefix is an alternate version.

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_before :: (a -> Bool) -> [a] -> [[a]] Source #

Split before places where the function matches.

> split_before (==1) [1, 2, 1]
[[], [1, 2], [1]]

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

Like split_before, but express the NonEmpty parts in the type.

> split_before_ne (==1) [1, 2, 1]
([], [1 :| [2], 1 :| []])

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

Split after places where the function matches.

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 => a -> [a] -> [[a]] Source #

Like split, but split on a single element.

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 #

Like List.mapAccumL, but monadic. Strict in the accumulator.