Is there a straight-forward solution to receiving the element *prior* to hitting the dropWhile predicate?

Question

Given a condition, I want to search through a list of elements and return the first element that reaches the condition, and the previous one.

In C/C++ this is easy :

int i = 0;
for(;;i++) if (arr[i] == 0) break;

After we get the index where the condition is met, getting the previous element is easy, through "arr[i-1]"

In Haskell:

• dropWhile (/=0) list gives us the last element I want

• takeWhile (/=0) list gives us the first element I want

But I don't see a way of getting both in a simple manner. I could enumerate the list and use indexing, but that seems messy. Is there a proper way of doing this, or a way of working around this?

Answer 1

I would zip the list with its tail so that you have pairs of elements available. Then you can just use find on the list of pairs:

f :: [Int] -> Maybe (Int, Int)
f xs = find ((>3) . snd) (zip xs (tail xs))

> f [1..10]
Just (3,4)

If the first element matches the predicate this will return Nothing (or the second match if there is one) so you might need to special-case that if you want something different.

As Robin Zigmond says break can also work:

g :: [Int] -> (Int, Int)
g xs = case break (>3) xs of (_, []) -> error "not found"
                             ([], _) -> error "first element"
                             (ys, z:_) -> (last ys, z)

(Or have this return a Maybe as well, depending on what you need.)

But this will, I think, keep the whole prefix ys in memory until it finds the match, whereas f can start garbage-collecting the elements it has moved past. For small lists it doesn't matter.

Answer 2

I would use a zipper-like search:

type ZipperList a = ([a], [a])

toZipperList :: [a] -> ZipperList a
toZipperList = (,) []

moveUntil' :: (a -> Bool) -> ZipperList a -> ZipperList a
moveUntil' _ (xs, []) = (xs, [])
moveUntil' f (xs, (y:ys))
    | f y       = (xs, (y:ys))
    | otherwise = moveUntil' f (y:xs, ys)

moveUntil :: (a -> Bool) -> [a] -> ZipperList a
moveUntil f = moveUntil' f . toZipperList

example :: [Int]
example = [2,3,5,7,11,13,17,19]

result :: ZipperList Int
result = moveUntil (>10) example -- ([7,5,3,2], [11,13,17,19])

The good thing about zippers is that they are efficient, you can access as many elements near the index you want, and you can move the focus of the zipper forwards and backwards. Learn more about zippers here:

http://learnyouahaskell.com/zippers

Note that my moveUntil function is like break from the Prelude but the initial part of the list is reversed. Hence you can simply get the head of both lists.

Answer 3

A non-awkward way of implementing this as a fold is making it a paramorphism. For general explanatory notes, see this answer by dfeuer (I took foldrWithTails from it):

-- The extra [a] argument f takes with respect to foldr
-- is the tail of the list at each step of the fold.  
foldrWithTails :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldrWithTails f n = go
    where
    go (a : as) = f a as (go as)
    go [] = n

boundary :: (a -> Bool) -> [a] -> Maybe (a, a)
boundary p = foldrWithTails findBoundary Nothing
    where
    findBoundary x (y : _) bnd
        | p y = Just (x, y)
        | otherwise = bnd
    findBoundary _ [] _ = Nothing

Notes:

• If p y is true we don't have to look at bnd to get the result. That makes the solution adequately lazy. You can check that by trying out boundary (> 1000000) [0..] in GHCi.

• This solution gives no special treatment to the edge case of the first element of the list matching the condition. For instance:

  GHCi> boundary (<1) [0..9]
  Nothing
  GHCi> boundary even [0..9]
  Just (1,2)
  

Answer 4

There's several alternatives; either way, you'll have to implement this yourself. You could use explicit recursion:

getLastAndFirst :: (a -> Bool) -> [a] -> Maybe (a, a)
getLastAndFirst p (x : xs@(y:ys))
    | p y = Just (x, y)
    | otherwise = getLastAndFirst p xs
getLastAndFirst _ [] = Nothing

Alternately, you could use a fold, but that would look fairly similar to the above, except less readable.

A third option is to use break, as suggested in the comments:

getLastAndFirst' :: (a -> Bool) -> [a] -> Maybe (a,a)
getLastAndFirst' p l =
    case break p l of
        (xs@(_:_), (y:_)) -> Just (last xs, y)
        _ -> Nothing

Answer 5

(\(xs, ys) -> [last xs, head ys]) $ break (==0) list

Using break as Robin Zigmond suggested ended up short and simple, not using Maybe to catch edge-cases, but I could replace the lambda with a simple function that used Maybe.

---

I toyed a bit more with the solution and came up with

breakAround :: Int -> Int -> (a -> Bool) -> [a] -> [a]
breakAround m n cond list = (\(xs, ys) -> (reverse (reverse take m (reverse xs))) ++ take n ys) $ break (cond) list

which takes two integers, a predicate, and a list of a, and returns a single list of m elements before the predicate and n elements after.

Example: breakAround 3 2 (==0) [3,2,1,0,10,20,30] would return [3,2,1,0,10]