Copyright | (c) Brett Wines 2014 |
---|---|
License | BSD-style |
Maintainer | bgwines@cs.stanford.edu |
Stability | experimental |
Portability | portable |
Safe Haskell | None |
Language | Haskell98 |
Assorted functions on lists.
- partition_with_block_size :: Int -> [a] -> [[a]]
- partition_into_k :: Int -> [a] -> [[a]]
- powerpartition :: [a] -> [[[a]]]
- uniqueify :: Ord a => [a] -> [a]
- pairify :: [a] -> [(a, a)]
- decyclify :: Eq a => [a] -> [a]
- shuffle :: forall a. Eq a => [a] -> Integer -> [a]
- powerset :: [a] -> [[a]]
- permutations :: [a] -> [[a]]
- subsets_of_size :: [a] -> Integer -> [[a]]
- subsets_of_size_with_replacement :: Integer -> [a] -> [[a]]
- cycles :: Eq a => [a] -> [[a]]
- has_cycles :: Eq a => [a] -> Bool
- diff_infinite :: Ord a => [a] -> [a] -> [a]
- merge :: Ord a => [a] -> [a] -> [a]
- merge_by :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a]
- zip_while :: (a -> b -> Bool) -> [a] -> [b] -> [(a, b)]
- remove_at_index :: Integer -> [a] -> [a]
- subseq :: Integer -> Integer -> [a] -> [a]
- take_while_keep_last :: (a -> Bool) -> [a] -> [a]
- take_while_and_rest :: (a -> Bool) -> [a] -> ([a], [a])
- find_and_rest :: (a -> Bool) -> [a] -> Maybe (a, [a])
- subsequences :: [a] -> [[a]]
- contiguous_subsequences :: [a] -> [[a]]
- contiguous_subsequences_of_length :: Show a => Integer -> [a] -> [[a]]
- is_sorted :: Ord a => [a] -> Bool
- mergesort :: Ord a => [a] -> [a]
- is_palindrome :: Eq e => [e] -> Bool
- contains_duplicates :: forall a. Ord a => [a] -> Bool
- bsearch :: (Integer -> Ordering) -> Maybe Integer
- bsearch_1st_geq :: (Integer -> Ordering) -> Maybe Integer
- elem_counts :: Ord a => [a] -> [(a, Integer)]
- running_bests :: forall a. Ord a => [a] -> [a]
- running_bests_by :: forall a. Ord a => (a -> a -> Ordering) -> [a] -> [a]
- (<$*>) :: Applicative f => (a -> a -> b) -> f a -> f b
- ($$) :: (a -> a -> b) -> a -> b
- interleave :: [a] -> [a] -> [a]
- passing_index_elems :: (Int -> Bool) -> [a] -> [a]
- count :: (a -> Bool) -> [a] -> Integer
- map_keep :: (a -> b) -> [a] -> [(a, b)]
- maximum_with_index :: Ord a => [a] -> (a, Integer)
- minimum_with_index :: Ord a => [a] -> (a, Integer)
- maxima_by :: (a -> a -> Ordering) -> [a] -> [a]
- minima_by :: (a -> a -> Ordering) -> [a] -> [a]
- length' :: [a] -> Integer
- drop' :: Integer -> [a] -> [a]
- take' :: Integer -> [a] -> [a]
- cons :: a -> [a] -> [a]
- snoc :: a -> [a] -> [a]
- map_fst :: (a -> c) -> (a, b) -> (c, b)
- map_snd :: (b -> c) -> (a, b) -> (a, c)
- map_pair :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)
- map_pair_same :: (a -> b) -> (a, a) -> (b, b)
- map_triple :: (a -> d) -> (b -> e) -> (c -> f) -> (a, b, c) -> (d, e, f)
- zip_with_pair :: (a -> c -> e) -> (b -> d -> f) -> (a, b) -> (c, d) -> (e, f)
- zip_with_pair_same :: (a -> b -> c) -> (a, a) -> (b, b) -> (c, c)
- fst3 :: (a, b, c) -> a
- snd3 :: (a, b, c) -> b
- trd3 :: (a, b, c) -> c
- pair_op :: (a -> b -> c) -> (a, b) -> c
- triple_op :: (a -> b -> c -> d) -> (a, b, c) -> d
Partitioning
partition_with_block_size :: Int -> [a] -> [[a]] Source
O(n) Partitions the given list into blocks of the specified length. Truncation behaves as follows:
partition_with_block_size 3 [1..10] == [[1,2,3],[4,5,6],[7,8,9],[10]]
partition_into_k :: Int -> [a] -> [[a]] Source
O(n) Partitions the given list into k blocks. Truncation behavior is best described by example:
partition_into_k 3 [1..9] == [[1,2,3],[4,5,6],[7,8,9]] partition_into_k 3 [1..10] == [[1,2,3,4],[5,6,7,8],[9,10]] partition_into_k 3 [1..11] == [[1,2,3,4],[5,6,7,8],[9,10,11]] partition_into_k 3 [1..12] == [[1,2,3,4],[5,6,7,8],[9,10,11,12]] partition_into_k 3 [1..13] == [[1,2,3,4,5],[6,7,8,9,10],[11,12,13]]
powerpartition :: [a] -> [[[a]]] Source
O(B(n)), where B(n) is the n^th Bell number. Computes all partitions of the given list. For example,
powerpartition [1..3] == [[[1],[2],[3]], [[1,2],[3]], [[2],[1,3]], [[1],[2,3]], [[1,2,3]]]
List transformations
pairify :: [a] -> [(a, a)] Source
O(n) Zips the list up into pairs. For example,
pairify [1..6] == [(1,2), (3,4), (5,6)] pairify [1..5] == [(1,2), (3,4)]
decyclify :: Eq a => [a] -> [a] Source
O(l m), where l is the cycle length and m is the index of the start of the cycle. If the list contains no cycles, then the runtime is O(n).
NOTE: this function will only find cycles in a list can be the output of an iterated function -- that is, no element may be succeeded by two separate elements (e.g. [2,3,2,4]).
shuffle :: forall a. Eq a => [a] -> Integer -> [a] Source
O(n log(n)) Shuffles the given list. The second parameter is the seed for the random number generator that backs the shuffle.
Permutations, combinations, and cycles
permutations :: [a] -> [[a]] Source
O(n!) Computes all permutations of the given list.
subsets_of_size :: [a] -> Integer -> [[a]] Source
O(2^k) Generates all subsets of the given list of size k.
subsets_of_size_with_replacement :: Integer -> [a] -> [[a]] Source
O(n^m) Computes all sets comprised of elements in the given list, where the elements may be used multiple times, where n
is the size of the given list and m
is the size of the sets to generate. For example,
subsets_of_size_with_replacement 3 [1,2] == [[1,1,1],[2,1,1],[1,2,1],[2,2,1],[1,1,2],[2,1,2],[1,2,2],[2,2,2]]
cycles :: Eq a => [a] -> [[a]] Source
O(n) Generates all cycles of a given list. For example,
cycles [1..3] == [[2,3,1],[3,1,2],[1,2,3]]
has_cycles :: Eq a => [a] -> Bool Source
O(l m), where l is the cycle length and m is the index of the start of the cycle. If the list contains no cycles, then the runtime is O(n).
Operations with two lists
diff_infinite :: Ord a => [a] -> [a] -> [a] Source
Given two infinite sorted lists, generates a list of elements in the first but not the second. Implementation from http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell).
merge_by :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a] Source
O(max(n, m)) Merges the two given sorted lists of respective lengths n and m, comparing elements in between the two lists with the given comparator function.
zip_while :: (a -> b -> Bool) -> [a] -> [b] -> [(a, b)] Source
O(min(n, m)) Zips the two given lists of respective lengths n and m as long as the pairs satisfy the given predicate function.
Sublists
remove_at_index :: Integer -> [a] -> [a] Source
O(n) Removes an element at the specified index in the given list.
subseq :: Integer -> Integer -> [a] -> [a] Source
O(n) Returns the subsequence of the given length at starting at index i of length m. For example,
subseq 4 5 [1..20] == [5,6,7,8,9]
take_while_keep_last :: (a -> Bool) -> [a] -> [a] Source
(O(n)) Identical to takeWhile
, but also contains the first element to satisfy the given predicate function. For example:
take_while_keep_last (<3) [1..] == [1,2,3]
take_while_and_rest :: (a -> Bool) -> [a] -> ([a], [a]) Source
(O(n)) Returns a pair where the first element is identical to what takeWhile
returns and the second element is the rest of the list
take_while_and_rest (<3) [1..10] == ([1,2],[3,4,5,6,7,8,9,10])
find_and_rest :: (a -> Bool) -> [a] -> Maybe (a, [a]) Source
O(n) Like Data.List.Find
, but returns a Maybe 2-tuple, instead, where the second element of the pair is the elements in the list after the first element of the pair.
(find_and_rest ((==) 3) [1..10]) == Just (3, [4..10])
subsequences :: [a] -> [[a]] Source
(O(2^n)) Returns all subsequences (contiguous and noncontiguous)
contiguous_subsequences :: [a] -> [[a]] Source
(O(n^2)) Returns all contiguous subsequences.
contiguous_subsequences_of_length :: Show a => Integer -> [a] -> [[a]] Source
O(n) Retuns all contiguous subsequences of the given length. E.g.:
contiguous_subsequences_of_length 3 "1234567890"
- "123","234","345","456","567","678","789","890"
Sorting
Predicates
is_palindrome :: Eq e => [e] -> Bool Source
O(n) Returns whether the given list is a palindrome.
contains_duplicates :: forall a. Ord a => [a] -> Bool Source
O(n log(n)) Returns whether the given list contains any element more than once.
Assorted functions
bsearch :: (Integer -> Ordering) -> Maybe Integer Source
O(f log k), where k is the returnvalue, and f is the runtime of the input function on the lowest power of 2 above the returnvalue.
bsearch_1st_geq :: (Integer -> Ordering) -> Maybe Integer Source
O(f log k), where k is the returnvalue, and f is the runtime of the input function on the lowest power of 2 above the returnvalue.
elem_counts :: Ord a => [a] -> [(a, Integer)] Source
O(nlog(n)) Counts the number of time each element appears in the given list. For example:
elem_counts [1,2,1,4] == [(1,2),(2,1),(4,1)]
running_bests :: forall a. Ord a => [a] -> [a] Source
O(n) Returns the noncontiguous sublist of elements greater than all previous elements. For example:
running_bests [1,3,2,4,6,5] == [1,3,4,6]
running_bests_by :: forall a. Ord a => (a -> a -> Ordering) -> [a] -> [a] Source
O(n) Returns the noncontiguous sublist of elements greater than all previous elements, where "greater" is determined by the provided comparison function. For example:
running_bests_by (Data.Ord.comparing length) [[1],[3,3,3],[2,2]] == [[1],[3,3,3]]
(<$*>) :: Applicative f => (a -> a -> b) -> f a -> f b Source
Shorthand for applicative functors:
f <$*> l = f <$> l <*> l
($$) :: (a -> a -> b) -> a -> b Source
Shorthand for applying the same parameter twice.
f $$ x = f x x
interleave :: [a] -> [a] -> [a] Source
O(min(n, m)) Interleaves elements from the two given lists of respective lengths n
and m
in an alternating fashion. For example:
interleave [1,3,5,7] [2,4,6,8] == [1,2,3,4,5,6,7,8]
interleave [1,3,5,7] [2,4,6] == [1,2,3,4,5,6,7]
interleave [1,3,5] [2,4,6,8] == [1,2,3,4,5,6,8]
passing_index_elems :: (Int -> Bool) -> [a] -> [a] Source
O(nf) Filters a list of length n
leaving elemnts the indices of which satisfy the given predicate function, which has runtime f
.
count :: (a -> Bool) -> [a] -> Integer Source
O(n) counts the number of elements in a list that satisfy a given predicate function.
map_keep :: (a -> b) -> [a] -> [(a, b)] Source
O(n) Maps the given function over the list while keeping the original list. For example:
map_keep chr [97..100] == [(97,'a'),(98,'b'),(99,'c'),(100,'d')]
maximum_with_index :: Ord a => [a] -> (a, Integer) Source
O(n) Finds the maximum element of the given list and returns a pair of it and the index at which it occurs (if the maximum element occurs multiple times, behavior is identical to that of maximumBy
). The list must be finite and non-empty.
minimum_with_index :: Ord a => [a] -> (a, Integer) Source
O(n) Finds the minimum element of the given list and returns a pair of it and the index at which it occurs (if the minimum element occurs multiple times, behavior is identical to that of minimumBy
). The list must be finite and non-empty.
maxima_by :: (a -> a -> Ordering) -> [a] -> [a] Source
O(n) Finds all maxima of the given list by the given comparator function. For example, > maxima_by (Data.Ord.comparing length) [[1,2], [1], [3,3], [2]] [[1,2], [3,3]]
minima_by :: (a -> a -> Ordering) -> [a] -> [a] Source
O(n) Finds all minima of the given list by the given comparator function. For example, > minima_by (Data.Ord.comparing length) [[1,2], [1], [3,3,3], [2]] [[1], [2]]
Tuples
map_fst :: (a -> c) -> (a, b) -> (c, b) Source
Applies the given function to the first element of the tuple.
map_snd :: (b -> c) -> (a, b) -> (a, c) Source
Applies the given function to the second element of the tuple.
map_pair :: (a -> c) -> (b -> d) -> (a, b) -> (c, d) Source
Applies the given two functions to the respective first and second elements of the tuple.
map_pair_same :: (a -> b) -> (a, a) -> (b, b) Source
Applies the given function to the first and second elements of the tuple.
map_triple :: (a -> d) -> (b -> e) -> (c -> f) -> (a, b, c) -> (d, e, f) Source
Applies the given three functions to the respective first, second, and third elements of the tuple.
zip_with_pair :: (a -> c -> e) -> (b -> d -> f) -> (a, b) -> (c, d) -> (e, f) Source
Applies the given function to respectively the first and second elements of the two tuple. For example,
zip_with_pair (*) (^) (2,3) (5,4) == (10,27)
zip_with_pair_same :: (a -> b -> c) -> (a, a) -> (b, b) -> (c, c) Source
Like zip_with_pair
, but re-using the same function.