How can I map a function to a list and stop when a condition is fulfilled and tell me if it stopped or reached the end?

user_12946736 0
Viewed 256

I want to apply a function over a list, but if, at any moment, a result returned by the function is of a certain kind, then I don't want to continue to iterate over the rest of the elements.

I know I could achieve this with this function:

example p f ls = takeWhile p $ map f ls

The thing is that I would like to know if it reached the end of the list, or if it failed to do so.

I thought of this function, but it seems a bit cumbersome:

haltmap :: Eq a => (a -> Bool) -> (b -> a) -> [a] ->  [b] -> Either [a] [a]
haltmap _ _ acc [] = Right acc
haltmap p f acc (h:t)
  | p output = Left acc
  | otherwise = haltmap p f (acc ++ [output]) t
  where output = f h

I use Left and Right to know if it went through the entire list or not.

I'm sure there's a better way to do that.

functional-programming haskell
3 Answers

I'd use span for this. It's like takeWhile but it gives you a pair with the remainder of the list as well as the matching part, like this:

> span (<3) [1,2,3,2,1]
([1,2],[3,2,1])

Then you can check if the remainder is empty:

haltmap :: (a -> Bool) -> (b -> a) -> [b] -> Either [a] [a]
haltmap p f xs = (if null rest then Right else Left) ys
  where
    (ys, rest) = span p (map f xs)
user_41689720

You can use foldr for this. Because go does not evaluate the second argument unless needed, this will also work for infinite lists. (Will Ness also had an answer that also used foldr, but it seems they've deleted it).

import Data.Bifunctor (bimap)

haltmap :: Eq a => (b -> Bool) -> (a -> b) -> [a] -> Either [b] [b]
haltmap p f xs = foldr go (Right []) xs
  where
    go x a
      | p output = let o = (output:) in bimap o o a
      | otherwise = Left []
      where output = f x

main = do
  print $ haltmap (<5) (+1) [1..]
  print $ haltmap (<12) (+1) [1..10]

Try it online!

Using a tuple with a Bool may be easier, though.

import Data.Bifunctor (second)

haltmap :: Eq a => (b -> Bool) -> (a -> b) -> [a] -> (Bool, [b])
haltmap p f xs = foldr go (True, []) xs
  where
    go x a
      | p output = second (output:) a
      | otherwise = (False, [])
      where output = f x

haltmap (<5) (+1) [1..]    //(False,[2,3,4])
haltmap (<12) (+1) [1..10] //(True,[2,3,4,5,6,7,8,9,10,11])

Try it online!

user_118820020

I found a solution with foldr, which is the following:

haltMap :: (a -> Bool) -> (b -> a) -> [b] -> Either [a] [a]
haltMap p f = foldr (\x acc -> if p x then Left []
                               else (either (\a -> Left (x:a)) (\b -> Right (x:b)) acc))
                    (Right []) . map f

Also, to return, instead of the partial list, the element which failed, all is needed it to change Left [] to Left x in the if clause, and change the (\a -> Left (x:a)) to Left in the else clause.

user_129467360
Related