Data.List.HT

Improved standard functions

inits :: [a] -> [[a]]

This function is lazier than the one suggested in the Haskell 98 report. It is inits undefined = [] : undefined, in contrast to Data.List.inits undefined = undefined.

tails :: [a] -> [[a]]

This function is lazier than the one suggested in the Haskell 98 report. It is tails undefined = ([] : undefined) : undefined, in contrast to Data.List.tails undefined = undefined.

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

This function compares adjacent elements of a list. If two adjacent elements satisfy a relation then they are put into the same sublist. Example:

>>> groupBy (<) "abcdebcdef"
["abcde","bcdef"]

In contrast to that groupBy compares the head of each sublist with each candidate for this sublist. This yields

>>> List.groupBy (<) "abcdebcdef"
["abcdebcdef"]

The second b is compared with the leading a. Thus it is put into the same sublist as a.

The sublists are never empty. Thus the more precise result type would be [(a,[a])].

group :: Eq a => [a] -> [[a]]

unzip :: [(a, b)] -> ([a], [b])

Like standard unzip but more lazy. It is Data.List.unzip undefined == undefined, but unzip undefined == (undefined, undefined).

partition :: (a -> Bool) -> [a] -> ([a], [a])

partition of GHC 6.2.1 fails on infinite lists. But this one does not.

span :: (a -> Bool) -> [a] -> ([a], [a])

It is Data.List.span f undefined = undefined, whereas span f undefined = (undefined, undefined).

break :: (a -> Bool) -> [a] -> ([a], [a])

It is Data.List.span f undefined = undefined, whereas span f undefined = (undefined, undefined).

Split

chop :: (a -> Bool) -> [a] -> [[a]]

Split the list at the occurrences of a separator into sub-lists. Remove the separators. This is somehow a generalization of lines and words. But note the differences:

>>> words "a  a"
["a","a"]
>>> chop (' '==) "a  a"
["a","","a"]

>>> lines "a\n\na"
["a","","a"]
>>> chop ('\n'==) "a\n\na"
["a","","a"]

>>> lines "a\n"
["a"]
>>> chop ('\n'==) "a\n"
["a",""]

breakAfter :: (a -> Bool) -> [a] -> ([a], [a])

Like break, but splits after the matching element.

forAllPredicates $ \p xs -> uncurry (++) (breakAfter p xs) == xs

takeUntil :: (a -> Bool) -> [a] -> [a]

Take all elements until one matches. The matching element is returned, too. This is the key difference to takeWhile (not . p). It holds:

forAllPredicates $ \p xs -> takeUntil p xs == fst (breakAfter p xs)

segmentAfter :: (a -> Bool) -> [a] -> [[a]]

Split the list after each occurence of a terminator. Keep the terminator. There is always a list for the part after the last terminator. It may be empty. See package non-empty for more precise result type.

forAllPredicates $ \p xs -> concat (segmentAfter p xs) == xs

forAllPredicates $ \p xs -> length (filter p xs) == length (tail (segmentAfter p xs))

forAllPredicates $ \p -> all (p . last) . init . segmentAfter p

forAllPredicates $ \p -> all (all (not . p) . init) . init . segmentAfter p

This test captures both infinitely many groups and infinitely big groups:

forAllPredicates $ \p x -> flip seq True . (!!100) . concat . segmentAfter p . cycle . (x:)

segmentBefore :: (a -> Bool) -> [a] -> [[a]]

Split the list before each occurence of a leading character. Keep these characters. There is always a list for the part before the first leading character. It may be empty. See package non-empty for more precise result type.

>>> segmentBefore isUpper "AbcdXyz"
["","Abcd","Xyz"]
>>> segmentBefore isUpper "kAbcdXYZ"
["k","Abcd","X","Y","Z"]

forAllPredicates $ \p xs -> concat (segmentBefore p xs) == xs

forAllPredicates $ \p xs -> length (filter p xs) == length (tail (segmentBefore p xs))

forAllPredicates $ \p -> all (p . head) . tail . segmentBefore p

forAllPredicates $ \p -> all (all (not . p) . tail) . tail . segmentBefore p

forAllPredicates $ \p x -> flip seq True . (!!100) . concat . segmentBefore p . cycle . (x:)

segmentAfterJust :: (a -> Maybe b) -> [a] -> ([([a], b)], [a])

>>> segmentAfterJust (\c -> toMaybe (isLetter c) (toUpper c)) "123a5345b---"
([("123",'A'),("5345",'B')],"---")

segmentAfterMaybe :: (a -> Maybe b) -> [a] -> ([([a], b)], [a])

Deprecated: use segmentAfterJust instead

segmentBeforeJust :: (a -> Maybe b) -> [a] -> ([a], [(b, [a])])

>>> segmentBeforeJust (\c -> toMaybe (isLetter c) (toUpper c)) "123a5345b---"
("123",[('A',"5345"),('B',"---")])

segmentBeforeMaybe :: (a -> Maybe b) -> [a] -> ([a], [(b, [a])])

Deprecated: use segmentBeforeJust instead

segmentAfterRight :: [Either a b] -> ([([a], b)], [a])

>>> segmentAfterRight [Left 'a', Right LT, Right GT, Left 'b']
([("a",LT),("",GT)],"b")

forAllMaybeFn $ \f xs -> segmentAfterJust f xs == segmentAfterRight (map (\x -> maybe (Left x) Right (f x)) xs)

segmentBeforeRight :: [Either a b] -> ([a], [(b, [a])])

>>> segmentBeforeRight [Left 'a', Right LT, Right GT, Left 'b']
("a",[(LT,""),(GT,"b")])

forAllMaybeFn $ \f xs -> segmentBeforeJust f xs == segmentBeforeRight (map (\x -> maybe (Left x) Right (f x)) xs)

removeEach :: [a] -> [(a, [a])]

removeEach xs represents a list of sublists of xs, where each element of xs is removed and the removed element is separated. It seems to be much simpler to achieve with zip xs (map (flip List.delete xs) xs), but the implementation of removeEach does not need the Eq instance and thus can also be used for lists of functions.

See also the proposal http://www.haskell.org/pipermail/libraries/2008-February/009270.html

>>> removeEach "abc"
[('a',"bc"),('b',"ac"),('c',"ab")]
>>> removeEach "a"
[('a',"")]
>>> removeEach ""
[]

splitEverywhere :: [a] -> [([a], a, [a])]

>>> splitEverywhere "abc"
[("",'a',"bc"),("a",'b',"c"),("ab",'c',"")]
>>> splitEverywhere "a"
[("",'a',"")]
>>> splitEverywhere ""
[]

splitLast :: [a] -> ([a], a)

Deprecated: use viewR instead

It holds splitLast xs == (init xs, last xs), but splitLast is more efficient if the last element is accessed after the initial ones, because it avoids memoizing list.

\(NonEmpty xs) -> splitLast (xs::String)  ==  (init xs, last xs)

viewL :: [a] -> Maybe (a, [a])

Should be prefered to head and tail.

viewR :: [a] -> Maybe ([a], a)

Should be prefered to init and last.

\xs -> maybe True ((init xs, last xs) == ) (viewR (xs::String))

switchL :: b -> (a -> [a] -> b) -> [a] -> b

Should be prefered to head and tail.

switchR :: b -> ([a] -> a -> b) -> [a] -> b

Should be prefered to init and last.

\xs -> switchR True (\ixs lxs -> ixs == init xs && lxs == last xs) (xs::String)

List processing starting at the end

dropRev :: Int -> [a] -> [a]

dropRev n is like reverse . drop n . reverse but it is lazy enough to work for infinite lists, too.

\n xs -> dropRev n (xs::String) == reverse (drop n (reverse xs))

takeRev :: Int -> [a] -> [a]

takeRev n is like reverse . take n . reverse but it is lazy enough to work for infinite lists, too.

\n xs -> takeRev n (xs::String) == reverse (take n (reverse xs))

splitAtRev :: Int -> [a] -> ([a], [a])

splitAtRev n xs == (dropRev n xs, takeRev n xs).

\n xs -> splitAtRev n (xs::String) == (dropRev n xs, takeRev n xs)

\n xs -> (xs::String) == uncurry (++) (splitAtRev n xs)

dropWhileRev :: (a -> Bool) -> [a] -> [a]

Deprecated: Use dropWhile from Data.List.Reverse.StrictElement or Data.List.Reverse.StrictSpine instead

takeWhileRev :: (a -> Bool) -> [a] -> [a]

Deprecated: Use takeWhile from Data.List.Reverse.StrictElement or Data.List.Reverse.StrictSpine instead

List processing with Maybe and Either

maybePrefixOf :: Eq a => [a] -> [a] -> Maybe [a]

maybePrefixOf xs ys is Just zs if xs is a prefix of ys, where zs is ys without the prefix xs. Otherwise it is Nothing. It is the same as stripPrefix.

>>> maybePrefixOf "abc" "abcdef"
Just "def"
>>> maybePrefixOf "def" "abcdef"
Nothing

maybeSuffixOf :: Eq a => [a] -> [a] -> Maybe [a]

>>> maybeSuffixOf "abc" "abcdef"
Nothing
>>> maybeSuffixOf "def" "abcdef"
Just "abc"

partitionMaybe :: (a -> Maybe b) -> [a] -> ([b], [a])

Partition a list into elements which evaluate to Just or Nothing by f.

forAllMaybeFn $ \f xs -> partitionMaybe f xs == (mapMaybe f xs, filter (isNothing . f) xs)

forAllPredicates $ \p xs -> partition p xs == partitionMaybe (\x -> toMaybe (p x) x) xs

takeWhileJust :: [Maybe a] -> [a]

This is the cousin of takeWhile analogously to catMaybes being the cousin of filter.

>>> takeWhileJust [Just 'a', Just 'b', Nothing, Just 'c']
"ab"

Example: Keep the heads of sublists until an empty list occurs.

>>> takeWhileJust $ map (fmap fst . viewL) ["abc","def","","xyz"]
"ad"

For consistency with takeWhile, partitionMaybe and dropWhileNothing it should have been:

takeWhileJust_ :: (a -> Maybe b) -> a -> [b]

However, both variants are interchangeable:

takeWhileJust_ f == takeWhileJust . map f
takeWhileJust == takeWhileJust_ id

dropWhileNothing :: (a -> Maybe b) -> [a] -> Maybe (b, [a])

breakJust :: (a -> Maybe b) -> [a] -> ([a], Maybe (b, [a]))

forAllMaybeFn $ \f xs -> snd (breakJust f xs) == dropWhileNothing f xs

spanJust :: (a -> Maybe b) -> [a] -> ([b], [a])

unzipEithers :: [Either a b] -> ([a], [b])

Sieve and slice

sieve :: Int -> [a] -> [a]

keep every k-th value from the list

>>> sieve 6 ['a'..'z']
"agmsy"

sliceHorizontal :: Int -> [a] -> [[a]]

>>> sliceHorizontal 6 ['a'..'z']
["agmsy","bhntz","ciou","djpv","ekqw","flrx"]

\(NonEmpty xs) -> QC.forAll (QC.choose (1, length xs)) $ \n -> sliceHorizontal n xs == transpose (sliceVertical n (xs::String))

\(NonEmpty xs) -> QC.forAll (QC.choose (1, length xs)) $ \n -> sliceVertical  n xs == transpose (sliceHorizontal n (xs::String))

The properties do not hold for empty lists because of:

>>> sliceHorizontal 4 ([]::[Int])
[[],[],[],[]]

sliceVertical :: Int -> [a] -> [[a]]

>>> sliceVertical 6 ['a'..'z']
["abcdef","ghijkl","mnopqr","stuvwx","yz"]

Search&replace

search :: Eq a => [a] -> [a] -> [Int]

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

\(NonEmpty xs) ys -> replace xs xs ys == (ys::String)

\(NonEmpty xs) (NonEmpty ys) -> equating (take 1000) (replace xs ys (cycle xs)) (cycle (ys::String))

multiReplace :: Eq a => [([a], [a])] -> [a] -> [a]

prop src dst xs -> replace src dst xs == multiReplace (src,dst)

Lists of lists

shear :: [[a]] -> [[a]]

Transform

[[00,01,02,...],          [[00],
 [10,11,12,...],   -->     [10,01],
 [20,21,22,...],           [20,11,02],
 ...]                      ...]

With concat . shear you can perform a Cantor diagonalization, that is an enumeration of all elements of the sub-lists where each element is reachable within a finite number of steps. It is also useful for polynomial multiplication (convolution).

shearTranspose :: [[a]] -> [[a]]

Transform

[[00,01,02,...],          [[00],
 [10,11,12,...],   -->     [01,10],
 [20,21,22,...],           [02,11,20],
 ...]                      ...]

It's like shear but the order of elements in the sub list is reversed. Its implementation seems to be more efficient than that of shear. If the order does not matter, better choose shearTranspose.

\xs -> shearTranspose xs  ==  map reverse (shear (xs::[String]))

outerProduct :: (a -> b -> c) -> [a] -> [b] -> [[c]]

Operate on each combination of elements of the first and the second list. In contrast to the list instance of liftM2 it holds the results in a list of lists.

\xs ys -> let f x y = (x::Char,y::Int) in concat (outerProduct f xs ys)  ==  liftM2 f xs ys

Miscellaneous

takeWhileMulti :: [a -> Bool] -> [a] -> [a]

Take while first predicate holds, then continue taking while second predicate holds, and so on.

rotate :: Int -> [a] -> [a]

rotate left

mergeBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]

Given two lists that are ordered (i.e. p x y holds for subsequent x and y) mergeBy them into a list that is ordered, again.

>>> mergeBy (<=) "agh" "begz"
"abegghz"

allEqual :: Eq a => [a] -> Bool

>>> allEqual "aab"
False
>>> allEqual "aaa"
True
>>> allEqual "aa"
True
>>> allEqual "a"
True
>>> allEqual ""
True

isAscending :: Ord a => [a] -> Bool

>>> isAscending "abc"
True
>>> isAscending "abb"
True
>>> isAscending "aba"
False
>>> isAscending "cba"
False
>>> isAscending "a"
True
>>> isAscending ""
True

isAscendingLazy :: Ord a => [a] -> [Bool]

mapAdjacent :: (a -> a -> b) -> [a] -> [b]

This function combines every pair of neighbour elements in a list with a certain function.

>>> mapAdjacent (<=) ""
[]
>>> mapAdjacent (<=) "a"
[]
>>> mapAdjacent (<=) "aba"
[True,False]
>>> mapAdjacent (,) "abc"
[('a','b'),('b','c')]

\x xs -> mapAdjacent subtract (scanl (+) x xs) == (xs::[Integer])

mapAdjacent1 :: (a -> a -> b -> c) -> a -> [(a, b)] -> [c]

>>> let f x y z = [x,y]++show(z::Int) in mapAdjacent1 f 'a' [('b',1), ('c',2), ('d',3)]
["ab1","bc2","cd3"]

equalWith :: (a -> b -> Bool) -> [a] -> [b] -> Bool

>>> equalWith (<=) "ab" "bb"
True
>>> equalWith (<=) "aa" "bbb"
False
>>> equalWith (==) "aa" "aaa"
False

\as bs -> let f a b = abs (a-b) <= (10::Int) in equalWith f as bs ==  equalWithRec f as bs

\as bs -> let f a b = abs (a-b) <= (10::Int) in equalWith f as bs ==  equalWithLiftM f as bs

range :: Num a => Int -> [a]

Enumerate without Enum context. For Enum equivalent to enumFrom.

>>> range 0 :: [Integer]
[]
>>> range 1 :: [Integer]
[0]
>>> range 8 :: [Integer]
[0,1,2,3,4,5,6,7]

\(NonNegative n) -> length (range n :: [Integer]) == n

padLeft :: a -> Int -> [a] -> [a]

padRight :: a -> Int -> [a] -> [a]

iterateAssociative :: (a -> a -> a) -> a -> [a]

For an associative operation op this computes iterateAssociative op a = iterate (op a) a but it is even faster than map (powerAssociative op a a) [0..] since it shares temporary results.

The idea is: From the list map (powerAssociative op a a) [0,(2*n)..] we compute the list map (powerAssociative op a a) [0,n..], and iterate that until n==1.

\x -> equating (take 1000) (List.iterate (x+) x) (iterateAssociative (+) (x::Integer))

iterateLeaky :: (a -> a -> a) -> a -> [a]

This is equal to iterateAssociative. The idea is the following: The list we search is the fixpoint of the function: "Square all elements of the list, then spread it and fill the holes with successive numbers of their left neighbour." This also preserves log n applications per value. However it has a space leak, because for the value with index n all elements starting at div n 2 must be kept.

\x -> equating (take 1000) (List.iterate (x+) x) (iterateLeaky (+) (x::Integer))

lengthAtLeast :: Int -> [a] -> Bool

>>> lengthAtLeast 0 ""
True
>>> lengthAtLeast 3 "ab"
False
>>> lengthAtLeast 3 "abc"
True
>>> lengthAtLeast 3 $ repeat 'a'
True
>>> lengthAtLeast 3 $ "abc" ++ undefined
True

\n xs -> lengthAtLeast n (xs::String)  ==  (length xs >= n)

lengthAtMost :: Int -> [a] -> Bool

>>> lengthAtMost 0 ""
True
>>> lengthAtMost 3 "ab"
True
>>> lengthAtMost 3 "abc"
True
>>> lengthAtMost 3 "abcd"
False
>>> lengthAtMost 3 $ repeat 'a'
False
>>> lengthAtMost 3 $ "abcd" ++ undefined
False

\n xs -> lengthAtMost n (xs::String)  ==  (length xs <= n)