1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Will Ness Jan 14 at 13:53
1
\$\begingroup\$

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 :)

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.