:: (a -> Bool) -> [a] -> ([a], [a]) -package:hedgehog

span, applied to a predicate p and a list xs, returns a tuple where first element is the longest prefix (possibly empty) of xs of elements that satisfy p and second element is the remainder of the list: span p xs is equivalent to (takeWhile p xs, dropWhile p xs), even if p is _|_.

Laziness

>>> span undefined []
([],[])

>>> fst (span (const False) undefined)
*** Exception: Prelude.undefined

>>> fst (span (const False) (undefined : undefined))
[]

>>> take 1 (fst (span (const True) (1 : undefined)))
[1]

span produces the first component of the tuple lazily:

>>> take 10 (fst (span (const True) [1..]))
[1,2,3,4,5,6,7,8,9,10]

Examples

>>> span (< 3) [1,2,3,4,1,2,3,4]
([1,2],[3,4,1,2,3,4])

>>> span (< 9) [1,2,3]
([1,2,3],[])

>>> span (< 0) [1,2,3]
([],[1,2,3])

break, applied to a predicate p and a list xs, returns a tuple where first element is longest prefix (possibly empty) of xs of elements that do not satisfy p and second element is the remainder of the list: break p is equivalent to span (not . p) and consequently to (takeWhile (not . p) xs, dropWhile (not . p) xs), even if p is _|_.

Laziness

>>> break undefined []
([],[])

>>> fst (break (const True) undefined)
*** Exception: Prelude.undefined

>>> fst (break (const True) (undefined : undefined))
[]

>>> take 1 (fst (break (const False) (1 : undefined)))
[1]

break produces the first component of the tuple lazily:

>>> take 10 (fst (break (const False) [1..]))
[1,2,3,4,5,6,7,8,9,10]

Examples

>>> break (> 3) [1,2,3,4,1,2,3,4]
([1,2,3],[4,1,2,3,4])

>>> break (< 9) [1,2,3]
([],[1,2,3])

>>> break (> 9) [1,2,3]
([1,2,3],[])

The partition function takes a predicate and a list, and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,

partition p xs == (filter p xs, filter (not . p) xs)

Examples

>>> partition (`elem` "aeiou") "Hello World!"
("eoo","Hll Wrld!")

>>> partition even [1..10]
([2,4,6,8,10],[1,3,5,7,9])

>>> partition (< 5) [1..10]
([1,2,3,4],[5,6,7,8,9,10])

Break, but from the end.

breakEnd isLower "youRE" == ("you","RE")
breakEnd isLower "youre" == ("youre","")
breakEnd isLower "YOURE" == ("","YOURE")
\f xs -> breakEnd (not . f) xs == spanEnd f  xs

Span, but from the end.

spanEnd isUpper "youRE" == ("you","RE")
spanEnd (not . isSpace) "x y z" == ("x y ","z")
\f xs -> uncurry (++) (spanEnd f xs) == xs
\f xs -> spanEnd f xs == swap (both reverse (span f (reverse xs)))

spanEnd p l == reverse (span p (reverse l)). The first list returns actually comes after the second list (when you look at the input list).

break, applied to a predicate p and a list xs, returns a tuple where first element is longest prefix (possibly empty) of xs of elements that do not satisfy p and second element is the remainder of the list:

>>> break (> 3) [1,2,3,4,1,2,3,4]
([1,2,3],[4,1,2,3,4])

>>> break (< 9) [1,2,3]
([],[1,2,3])

>>> break (> 9) [1,2,3]
([1,2,3],[])

break p is equivalent to span (not . p).

span, applied to a predicate p and a list xs, returns a tuple where first element is longest prefix (possibly empty) of xs of elements that satisfy p and second element is the remainder of the list:

>>> span (< 3) [1,2,3,4,1,2,3,4]
([1,2],[3,4,1,2,3,4])

>>> span (< 9) [1,2,3]
([1,2,3],[])

>>> span (< 0) [1,2,3]
([],[1,2,3])

span p xs is equivalent to (takeWhile p xs, dropWhile p xs)

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

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

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

Like break, but splits after the matching element.

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

forAllPredicates $ \p xs -> Rev.span p xs == swap (mapPair (reverse, reverse) (List.span p (reverse xs)))

forAllPredicates $ \p xs -> Rev.span p xs == (Rev.dropWhile p xs, Rev.takeWhile p xs)

\x xs pad -> defined $ Match.take (pad::[()]) $ fst $ Rev.span ((x::Char)/=) $ cycle $ x:xs

forAllPredicates $ \p xs -> Rev.span p xs == swap (mapPair (reverse, reverse) (List.span p (reverse xs)))

forAllPredicates $ \p xs -> Rev.span p xs == (Rev.dropWhile p xs, Rev.takeWhile p xs)

\x xs pad -> defined $ mapFst length $ Rev.span ((x::Char)/=) $ Match.replicate (pad::[()]) undefined ++ x:xs

span, applied to a predicate p and a list xs, returns a tuple where first element is longest prefix (possibly empty) of xs of elements that satisfy p and second element is the remainder of the list:

span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
span (< 9) [1,2,3] == ([1,2,3],[])
span (< 0) [1,2,3] == ([],[1,2,3])

span p xs is equivalent to (takeWhile p xs, dropWhile p xs)

break, applied to a predicate p and a list xs, returns a tuple where first element is longest prefix (possibly empty) of xs of elements that do not satisfy p and second element is the remainder of the list:

break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
break (< 9) [1,2,3] == ([],[1,2,3])
break (> 9) [1,2,3] == ([1,2,3],[])

break p is equivalent to span (not . p).

The partition function takes a predicate a list and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,

partition p xs == (filter p xs, filter (not . p) xs)

>>> partition (`elem` "aeiou") "Hello World!"
("eoo","Hll Wrld!")

Split is like break, but the matching element is dropped.

The partition function takes a predicate and a list, and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,

partition p xs == (filter p xs, filter (not . p) xs)

>>> partition (`elem` "aeiou") "Hello World!"
("eoo","Hll Wrld!")

Breaks a list just after an element satisfying the predicate is found.

>>> breakAfter even [1,3,5,2,4,7,8]
([1,3,5,2],[4,7,8])

spanEnd p l == reverse (span p (reverse l)). Invariant: l == front ++ end where (end, front) = spanEnd p l (From package ghc, module Util.)