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 :)
splitAtPredicate even [2]
andsplitAtPredicate even []
will both return the same result? also, it should beright@ ~(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