This package provides common list functions for the Frege language.
It contains all functions described in chapter 20 "Data.List" of the Haskell 2010 Language Report. Where possible, the code has been ported from public Haskell source code (http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.html).
The maximumBy function takes a comparison function and a list and returns the greatest element of the list by the comparison function. The list must be finite and non-empty.
The minimumBy function takes a comparison function and a list and returns the least element of the list by the comparison function. The list must be finite and non-empty.
The unfoldr function is a dual to foldr: while foldr reduces a list to a summary value, unfoldr builds a list from a seed value. The function takes the element and returns Maybe.Nothing if it is done producing the list or returns Maybe.Just (a,b), in which case, a is a prepended to the list and b is used as the next element in a recursive call. For example,
iterate f == unfoldr (\x -> Just (x, f x))
In some cases, unfoldr can undo a foldr operation:
unfoldr f' (foldr f z xs) == xs
if the following holds:
f' (f x y) = Just (x,y) f' z = Nothing
A simple use of unfoldr:
unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10 [10,9,8,7,6,5,4,3,2,1]
The inits function returns all initial segments of the argument, shortest first. For example,
inits "abc" == ["","a","ab","abc"]
The tails function returns all final segments of the argument, longest first. For example,
tails "abc" == ["abc", "bc", "c",""]
takeUntil p xs is the same as takeWhile (not • p) xs
dropUntil p xs is the same as dropWhile (not • p) xs
Consequently, for all lists /xs/
takeUntil p xs ++ dropUntil p xs == xs
group xs returns a list of sub-lists made of adjacent equal elements in xs. All sublist are not empty and their concatenation yields again xs.
groupBy f xs groups by function f instead of (==) that is used by group
elemBy f is a more general version of elem that uses /f/ instead of Eq.==.
See also: using
lookup a key in an association list
delete x removes the first occurrence of x from its list argument. For example,
delete ’a’ "banana" == "bnana"
It is a special case of deleteBy, which allows the programmer to supply their own equality test.
The deleteBy function behaves like delete, but takes a user-supplied equality predicate.
The deleteFirstsBy function takes a predicate and two lists and returns the first list with the first occurrence of each element of the second list removed.
The non-overloaded version of insert.
The \\ function is list difference (non-associative). In the result of xs \\ ys, the first occurrence of each element of ys in turn (if any) has been removed from xs. Thus
(xs ++ ys) \\ xs == ys.
It is a special case of deleteFirstsBy, which allows the programmer to supply their own equality test.
The union function returns the list union of the two lists. For example,
"dog" `union` "cow" == "dogcw"
Duplicates, and elements of the first list, are removed from the the second list, but if the first list contains duplicates, so will the result.
It is a special case of unionBy, which allows the programmer to supply their own equality test.
The unionBy function is the non-overloaded version of union.
The intersect function takes the list intersection of two lists. For example,
[1,2,3,4] `intersect` [2,4,6,8] == [2,4]
If the first list contains duplicates, so will the result.
[1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]
It is a special case of intersectBy, which allows the programmer to supply their own equality test.
The intersectBy function is the non-overloaded version of intersect.
unique removes duplicate elements from an unsorted list, which may or may not be faster than using (uniq • sort)
This function is known as nub in Haskell and Prelude provides this as alias.
However, the following holds
sort (unique xs) == uniq (sort xs)
Alias for unique
Alias for uniqueBy
uniqueBy f is a more general form of unique, but uses f instead of Eq.== to decide whether equal elements are contained in the list.
The following holds:
sortBy (comparing f) (uniqueBy (using f) xs) == uniqBy (using f) (sortBy (comparing f) xs)
uniq removes adjacent equal elements from a list
uniq [1, 2, 2, 3, 2] = [1, 2, 3, 2]
This is most useful on sorted lists to remove duplicates. For unsorted lists use unique
uniqBy f is a variant of uniq that uses f instead of Eq.==. In the result, there are no two adjacent elements x and y where the relation y `f` x holds.
This is most useful on sorted lists with projection functions that compare parts of the value for equality. See also using.
uniqBy (using fst) [(1, 1), (2, 2), (2, 3), (3, 4), (2, 5)] = uniqBy (\a\b -> fst a == fst b) [(1, 1), (2, 2), (2, 3), (3, 4), (2, 5)] = [(1, 1), (2, 2), (3, 4), (2, 5)]
The example shows that the first of adjacent, equal comparing elements is retained.
partitioned p xs splits xs in 2 lists and returns them as a tuple (xs1, xs2), such that xs1 contains all elements of xs that satisfy predicate p and xs2 contains those that do not.
The order of the elements of xs is reversed in the results. The argument must be finite, it is processed in a tail recursive loop.
See also partition, which is lazy and works on infinite lists, but may be slower on finite lists because it processes the argument twice.
The following is true for all finite lists xs
let ps = partitionR p xs
in all p (fst ps)
&& (not • any p) (snd ps)
&& length (fst ps) + length (snd ps) == length xs
&& all (`elem` xs) (fst ps)
&& all (`elem` xs) (snd ps)
&& all (\x -> x `elem` fst ps || x `elem` snd ps) xs
A variant of partition that satisfies the Haskell 2010 specification. When the order of the results is irrelevant or one actually wants the results reversed, consider the more efficient partitioned.
intercalate xs xss is equivalent to concat (intersperse xs xss)
unzip4 unzips a list of quadrupels and returns a quadrupel of lists.
zipWith4 /f/ zips 4 lists with function /f/ instead of the standard (,,,) that is used by zip4
unzip5 unzips a list of quintuples and returns a quintuple of lists.
zipWith5 /f/ zips 5 lists with function /f/ instead of the standard (,,,,) that is used by zip5
unzip6 unzips a list of sextuples and returns a sextuple of lists.
zipWith6 /f/ zips 6 lists with function /f/ instead of the standard (,,,,,) that is used by zip6
unzip7 unzips a list of septuples and returns a septuple of lists.
zipWith7 /f/ zips 7 lists with function /f/ instead of the standard (,,,,,,) that is used by zip7
sortBy f xs is a stable sort (merge sort), it uses /f/ to decide the order of elements. If a `f` b is Ordering.Lt or Eq, then /a/ comes before /b/, otherwise /b/ comes before /a/.
see also comparing, descending
Merge two lists, taking elements from the left as long as they are not Ordering.Gt (according to the passed comparison function) than the head element from the right.
Makes most sense when the lists are sorted by the same criteria.
Standard sort uses operator Ord.<=> and demands that the type of the list elements is an instance of Ord
The transpose function transposes the rows and columns of its argument.
For example,
transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
The subsequences function returns the list of all subsequences of the argument.
subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
The nonEmptySubsequences function returns the list of all subsequences of the argument, except for the empty list.
nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
The permutations function returns the list of all permutations of the argument.
permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
The mapAccumL function behaves like a combination of map and fold; it applies a function to each element of a list, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new list.
The mapAccumR function behaves like a combination of map and foldr; it applies a function to each element of a list, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new list.
The stripPrefix function drops the given prefix from a list. It returns Maybe.Nothing if the list did not start with the prefix given, or Maybe.Just the list after the prefix, if it does.
stripPrefix "foo" "foobar" -> Just "bar" stripPrefix "foo" "foo" -> Just "" stripPrefix "foo" "barfoo" -> Nothing stripPrefix "foo" "barfoobaz" -> Nothing
The isPrefixOf function takes two lists and returns true iff the first list is a prefix of the second.
The isSuffixOf function takes two lists and returns true iff the first list is a suffix of the second. Both lists must be finite.
The isInfixOf function takes two lists and returns true iff the first list is contained, wholly and intact, anywhere within the second.
Example:
isInfixOf "Haskell" "I really like Haskell." == true isInfixOf "Ial" "I really like Haskell." == false
The elemIndex function returns the index of the first element in the given list which is equal (by Eq.==) to the query element, or Maybe.Nothing if there is no such element.
The elemIndices function extends elemIndex, by returning the indices of all elements equal to the query element, in ascending order.
The find function takes a predicate and a list and returns the first element in the list matching the predicate, or Maybe.Nothing if there is no such element.
The findIndex function takes a predicate and a list and returns the index of the first element in the list satisfying the predicate, or Maybe.Nothing if there is no such element.
The findIndices function extends findIndex, by returning the indices of all elements satisfying the predicate, in ascending order.
The genericLength function is an overloaded version of ListView.length. In particular, instead of returning an Int, it returns any type which is an instance of Num. It is, however, less efficient than ListView.length.
The genericTake function is an overloaded version of ListView.take, which accepts any Integral value as the number of elements to take.
The genericDrop function is an overloaded version of ListView.drop, which accepts any Integral value as the number of elements to drop.
The genericSplitAt function is an overloaded version of splitAt, which accepts any Integral value as the position at which to split.
The genericIndex function is an overloaded version of !!, which accepts any Integral value as the index.
The genericReplicate function is an overloaded version of replicate, which accepts any Integral value as the number of repetitions to make.
inits, nonEmptySubsequences, permutations, subsequences, tails