Implementing Haskell#break

Question

Learn You a Haskell demonstrates the break function:

breaks it when the predicate is first true.

Example:

-- ghci> break (==4) [1,2,3,4,5,6,7] 
-- ([1,2,3],[4,5,6,7]) 

Here's my code:

break' :: (a -> Bool) -> [a] -> ([a], [a])
break' _ [] = ([], [])
break' f ys = break'' f ys []
 where break'' _ [] acc = (reverse acc, [])
 break'' g xxs@(x:xs) acc 
 | g x = (reverse acc, xxs)
 | otherwise = break'' g xs (x:acc)

I used the reverse rather than use the ++ function due to @Anonymous's helpful advice on my implementation of lines.

Please review it.

Answer 1

The first [] case is unnecessary, since break'' already handles empty lists.

g is unnecessary, since f is in scope.

break'' has two nearly identical base cases, which could be combined into one (you may need to use head and tail instead of pattern-matching). That's a line shorter but IMO no clearer.

My previous advice to reverse the accumulator contained a subtle flaw: it needs to find the boundary before it returns anything, so it's not lazy enough. (This is a subtlety of lazy data structures; if you don't understand it yet, don't worry about it.) This occasionally matters in cases like this:

let (a, b) = break (==' ') $ "abc" ++ undefined in head a

The actual implementation avoids this by simply adding x to the result of the recursive call, without using an accumulator:

break _ xs@[] = (xs, xs)
break p xs@(x:xs')
 | p x = ([],xs)
 | otherwise = let (ys,zs) = break p xs' in (x:ys,zs)