Splitting a list by predicate

Question

I have written a function splitAtPredicate that splits the list at element x satisfying p, dropping x and returning a tuple.

-- | 'splitAtPredicate', applied to a predicate @p@ and a list @xs@,
-- splits the list at element @x@ satisfying @p@, dropping @x@.
splitAtPredicate :: (a -> Bool) -> [a] -> ([a], [a])
splitAtPredicate p = splitAtPredicateAcc p []
 where
 splitAtPredicateAcc p left right@(x : xs')
 | null right = (left, right)
 | p x = (left, xs')
 | otherwise = splitAtPredicateAcc p (left ++ [x]) xs'

It works, but I'm new to Haskell, so I'm unsure how idiomatic and performant this is. In addition, I'm not too happy with the name splitAtPredicateAcc. Any suggestions are more than welcome.

• Will Ness: from the description, splitAtPredicate even [2] and splitAtPredicate even [] will both return the same result? also, it should be right@ ~(x : xs'). you say it works, but as written now, splitAtPredicate even [] should cause error AFAICT. have you tested?

Answer 1

Welcome to the Haskell community :)

Haskellers like composition. Your logic is composed of 2 parts:

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

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

---

Let's address splitWhen first.

E.g. splitWhen (== '2') "132342245" should be ["13", "33", "", "45"].

To illustrate how it works:

initial state: (unconsumed input: "132332245", aggregator: [""])
step 1: (current input: '1', unconsumed input: "32342245", aggregator: ["1"])
step 2: (current input: '3', unconsumed input: "2332245", aggregator: ["13"])
step 3: (current input: '2', unconsumed input: "332245", aggregator: ["13",""])
step 4: (current input: '3', unconsumed input: "32245", aggregator: ["13","3"])
step 5: (current input: '3', unconsumed input: "2245", aggregator: ["13","33"])
step 5: (current input: '2', unconsumed input: "245", aggregator: ["13","33", ""])
step 6: (current input: '2', unconsumed input: "45", aggregator: ["13","33", "", ""])
step 7: (current input: '4', unconsumed input: "5", aggregator: ["13","33", "", "4"])
step 8: (current input: '5', unconsumed input: "", aggregator: ["13","33", "", "45"])

There are many ways to write this in Haskell, for example if we call the above logic f:

splitWhen :: (a -> Bool) -> [a] -> [[a]]
splitWhen p xs = f xs [] -- the initial aggregator
 where f [] agg = [agg]
 f (y : ys) agg = if p y
 then agg : f ys [] -- we are ignoring the element here
 else f ys (agg ++ [y]) -- put y into the aggregator

• Notice the pattern match (y : ys), they are the current input and unconsumed input.

• Notice the recursive function call of f.

---

toTuple is trivial:

toTuple :: [[a]] -> ([a], [a])
toTuple [] = ([], [])
toTuple [xs] = (xs, [])
toTuple (xs:ys:_) = (xs, ys)

---

Finally the exiting part - function composition:

splitAtPredicate :: (a -> Bool) -> [a] -> ([a], [a])
splitAtPredicate p = toTuple . splitWhen p

or if you are not yet comfortable with the pointfree style

splitAtPredicate :: (a -> Bool) -> [a] -> ([a], [a])
splitAtPredicate p xs = toTuple . splitWhen p xs

Because Haskell's lazy nature, splitAtPredicate will stop when it finds the second element that satisfies the predicate, as we have enough data to construct the pair.

To put everything together:

splitWhen :: (a -> Bool) -> [a] -> [[a]]
splitWhen p xs = f xs [] -- the initial aggregator
 where f [] agg = [agg]
 f (y : ys) agg = if p y
 then agg : f ys [] -- we are ignoring the element here
 else f ys (agg ++ [y]) -- put y into the aggregator
toTuple :: [[a]] -> ([a], [a])
toTuple [] = ([], [])
toTuple [xs] = (xs, [])
toTuple (xs:ys:_) = (xs, ys)
splitAtPredicate :: (a -> Bool) -> [a] -> ([a], [a])
splitAtPredicate p = toTuple . splitWhen p

Hope that helps :) And again welcome to the Haskell world.

If you haven't done it already, checkout https://hoogle.haskell.org , you'll love it :)

Answer 2

Replace accumulators by post-processing when possible.

splitAtPredicate :: (a -> Bool) -> [a] -> ([a], [a])
splitAtPredicate p [] = ([], [])
splitAtPredicate p (x:xs)
 | p x = ([], xs)
 | otherwise = let (left, right) = splitAtPredicate p xs in (x:left, right)

Use existing library functions.

splitAtPredicate p xs = let (left, right) = break p xs in (left, drop 1 right)