Haskell: interrupt the loop conditionally

Question

I want to break the loop in this situation:

import Data.Maybe (fromJust, isJust, Maybe(Just)) tryCombination :: Int -> Int -> Maybe String tryCombination xy | x * y == 20 = Just "Okay" | otherwise = Nothing result :: [String] result = map (fromJust) $ filter (isJust) [tryCombination xy | x <- [1..5], y <- [1..5]] main = putStrLn $ unlines $result 

Imagine that "tryCombination" is much more complicated than in this example. And it consumes a lot of processor power. And this is not an evalutation of 25 possibilities, but 26 ^ 3.

Therefore, when "tryCombination" finds a solution for this combination, it returns "Just", otherwise "Nothing". How can I instantly break the loop on the first solution found?

Answer 1

Simple solution: find and join

It looks like you are looking for Data.List.find . find has a type signature

 find :: (a -> Bool) -> [a] -> Maybe a 

So you would do something like

 result :: Maybe (Maybe String) result = find isJust [tryCombination xy | x <- [1..5], y <- [1..5]] 

Or, if you don't want Maybe (Maybe String) (why do you need it?), You can stack them together with Control.Monad.join , which has a signature

 join :: Maybe (Maybe a) -> Maybe a 

so you have

 result :: Maybe String result = join $ find isJust [tryCombination xy | x <- [1..5], y <- [1..5]] 

---

More advanced solution: asum

If you want a slightly more advanced solution, you can use Data.Foldable.asum , which has a signature

 asum :: [Maybe a] -> Maybe a 

What he does is select the first Just value from the list of many. He does this using an Alternative instance of Maybe . An Alternative Maybe instance works as follows: (import Control.Applicative to access the <|> operator)

 λ> Nothing <|> Nothing Nothing λ> Nothing <|> Just "world" Just "world" λ> Just "hello" <|> Just "world" Just "hello" 

In other words, he selects the first Just value from two alternatives. Imagine putting <|> between each item in your list so that

 [Nothing, Nothing, Just "okay", Nothing, Nothing, Nothing, Just "okay"] 

goes into

 Nothing <|> Nothing <|> Just "okay" <|> Nothing <|> Nothing <|> Nothing <|> Just "okay" 

This is exactly what the asum function does! Since <|> is short-circuited, it will only evaluate to the first Just value. At the same time, your function will be as simple as

 result :: Maybe String result = asum [tryCombination xy | x <- [1..5], y <- [1..5]] 

Why do you need this more advanced solution? It is not only shorter; once you know the idiom (i.e. when you are familiar with Alternative and asum ), it’s much more clear what the function does by simply reading the first few characters of the code.

Answer 2

To answer your question, find is what you need. After you get Maybe (Maybe String) , you can convert it to Maybe String with join

While find more enjoyable, more readable, and certainly does just what you need, I would not be so sure of the inefficiency of the code that you have in the question. A lazy assessment will probably take care of this and calculate only what is needed (additional memory can still be used). If you are interested, try comparing.

Answer 3

Laziness can really take care of this in this situation.

By calling unlines , you request all the output of your "loop" ¹ so obviously it cannot stop after the first successful tryCombination . But if you need only one match, just use listToMaybe (from Data.Maybe ); it will convert your list to Nothing if there are no matches, or Just first match is found.

Laziness means that the results in the list will be evaluated only on demand; if you never require more list items, the calculations necessary to create them (or even see if there are any other items in the list) will never be executed!

This means that you often don’t need to “break loops” the way you do in imperative languages. You can write a complete "cycle" as a list generator, and the consumer (s) can decide for themselves how many of them they want. An extreme case of this idea is that Haskell is happy to generate and even filter endless lists; it will only run the generation code, sufficient to get exactly as many elements as you later study.

---

¹ In fact, even unlines creates a lazy line, so if, for example, you only read the first line of the resulting concatenated line, you could have broken the loop before! But you are all typing here.

Answer 4

The evaluation strategy you are looking for is precisely the target of the Maybe MonadPlus . In particular, there is a msum function, the type of which in this case specializes in

 msum :: [Maybe a] -> Maybe a 

Intuitively, this version of msum accepts a list of potentially unsuccessful calculations, executes them one by one until the first calculations succeed and return the corresponding result. So, result will become

 result :: Maybe String result = msum [tryCombination xy | x <- [1..5], y <- [1..5]] 

In addition, you can make your code, in a sense, agnostic for an exact evaluation strategy, generalizing from Maybe to any MonadPlus instance:

 tryCombination :: MonadPlus m => Int -> Int -> m (Int,Int) -- For the sake of illustration I changed to a more verbose result than "Okay". tryCombination xy | x * y == 20 = return (x,y) -- `return` specializes to `Just`. | otherwise = mzero -- `mzero` specializes to `Nothing`. result :: MonadPlus m => m (Int,Int) result = msum [tryCombination xy | x <- [1..5], y <- [1..5]] 

To get the desired behavior, simply run the following:

 *Main> result :: Maybe (Int,Int) Just (4,5) 

However, if you decide that you need not only the first combination, but all of them, just use the [] instance of MonadPlus :

 *Main> result :: [(Int,Int)] [(4,5),(5,4)] 

I hope this helps more at a conceptual level than just providing a solution.

PS: I noticed that MonadPlus and msum are too strict for this purpose, Alternative and asum would be enough.