2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
| improve this answer | |
\$\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.