Compiled: Wed Dec 05 00:00:55 PST 2012 from source file: ./frege/data/List.fr
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 \\ 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.
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.
dropUntil p xs is the same as dropWhile (not • p) xs
Consequently, for all lists /xs/
takeUntil p xs ++ dropUntil p xs == xs
elemBy f is a more general version of elem that uses /f/ instead of Ord.==.
See also: using
The elemIndex function returns the index of the first element in the given list which is equal (by Ord.==) 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 genericDrop function is an overloaded version of drop, which accepts any Integral value as the number of elements to drop.
The genericIndex function is an overloaded version of Prelude.!!, which accepts any Integral value as the index.
The genericLength function is an overloaded version of ListLike.length. In particular, instead of returning an Int, it returns any type which is an instance of Num. It is, however, less efficient than ListLike.length.
The genericReplicate function is an overloaded version of replicate, which accepts any Integral value as the number of repetitions to make.
The genericSplitAt function is an overloaded version of splitAt, which accepts any Integral value as the position at which to split.
The genericTake function is an overloaded version of take, which accepts any Integral value as the number of elements to take.
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
The inits function returns all initial segments of the argument, shortest first. For example,
inits "abc" == ["","a","ab","abc"]
The non-overloaded version of insert.
intercalate xs xss is equivalent to concat (intersperse xs xss)
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.
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 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.
lookup a key in an association list
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 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 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"]
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.
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 follwoing 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
The permutations function returns the list of all permutations of the argument.
permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
Standard sort uses operator Ord.<= and demands that the type of the list elements is an instance of Ord
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
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 subsequences function returns the list of all subsequences of the argument.
subsequences "abc" == ["","a","b","ab","c","ac","bc","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
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 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 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.
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 Ord.==. 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.
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 follwoing holds
sort (unique xs) == uniq (sort xs)
uniqueBy f is a more general form of unique, but uses f instead of Ord.== 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)
unzip4 unzips a list of quadrupels and returns a quadrupel of lists.
unzip5 unzips a list of quintupels and returns a quintupel of lists.
unzip6 unzips a list of sextupels and returns a sextupel of lists.
unzip7 unzips a list of septupels and returns a septupel of lists.
zipWith4 /f/ zips 4 lists with function /f/ instead of the standard (,,,) that is used by zip4
zipWith5 /f/ zips 5 lists with function /f/ instead of the standard (,,,,) that is used by zip5
zipWith6 /f/ zips 6 lists with function /f/ instead of the standard (,,,,,) that is used by zip6
zipWith7 /f/ zips 7 lists with function /f/ instead of the standard (,,,,,,) that is used by zip7
inits, nonEmptySubsequences, permutations, subsequences, tails