Haskell: Break a loop conditionally

问题:

I want to break a loop in a situation like this:

import Data.Maybe (fromJust, isJust, Maybe(Just))

tryCombination :: Int -> Int -> Maybe String
tryCombination x y 
               | x * y == 20 = Just "Okay"
               | otherwise = Nothing

result :: [String]
result = map (fromJust) $ 
    filter (isJust) [tryCombination x y | x <- [1..5], y <- [1..5]]

main = putStrLn $ unlines $result

Imagine, that "tryCombination" is a lot more complicated like in this example. And it's consuming a lot of cpu power. And it's not a evalutation of 25 possibilities, but 26^3.

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

回答1:

Simple solution: find and join

It looks like you're looking for Data.List.find. find has the type signature

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

So you'd do something like

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

Or, if you don't want a Maybe (Maybe String) (why would you?), you can fold them together with Control.Monad.join, which has the signature

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

so that you have

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

---

More advanced solution: asum

If you wanted a slightly more advanced solution, you could use Data.Foldable.asum, which has the signature

asum :: [Maybe a] -> Maybe a

What it does is pick out the first Just value from a list of many. It does this by using the Alternative instance of Maybe. The Alternative instance of Maybe works like this: (import Control.Applicative to get access to the <|> operator)

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

In other words, it picks the first Just value from two alternatives. Imagine putting <|> between every element of your list, so that

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

gets turned to

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

This is exactly what the asum function does! Since <|> is short-circuiting, it will only evaluate up to the first Just value. With that, your function would be as simple as

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

Why would you want this more advanced solution? Not only is it shorter; once you know the idiom (i.e. when you are familiar with Alternative and asum) it is much more clear what the function does, just by reading the first few characters of the code.

回答2:

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

While find is nicer, more readable and surely does only what's needed, I wouldn't be so sure about inefficiency of the code that you have in a question. The lazy evaluation would probably take care of that and compute only what's needed, (extra memory can still be consumed). If you are interested, try to benchmark.

回答3:

Laziness can actually take care of that in this situation.

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

Laziness means that the results in the list will only be evaluated on demand; if you never demand any more elements of the list, the computations necessary to produce them (or even see whether there are any more elements in the list) will never be run!

This means you often don't have to "break loops" the way you do in imperative languages. You can write the full "loop" as a list generator, and the consumer(s) can decide independently how much of the they want. The extreme case of this idea is that Haskell is perfectly happy to generate and even filter infinite lists; it will only run the generation code just enough to produce exactly as many elements as you later end up examining.

---

¹ Actually even unlines produces a lazy string, so if you e.g. only read the first line of the resulting joined string you could still "break the loop" early! But you print the whole thing here.

回答4:

The evaluation strategy you are looking for is exactly the purpose of the Maybe instance of MonadPlus. In particular, there is the function msum whose type specializes in this case to

msum :: [Maybe a] -> Maybe a

Intuitively, this version of msum takes a list of potentially failing computations, executes them one after another until the first computations succeeds and returns the according result. So, result would become

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

On top of that, you could make your code in some sense agnostic to the exact evaluation strategy by generalizing from Maybe to any instance of MonadPlus:

tryCombination :: MonadPlus m => Int -> Int -> m (Int,Int)
-- For the sake of illustration I changed to a more verbose result than "Okay".
tryCombination x y 
    | 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 x y | x <- [1..5], y <- [1..5]]

To get your desired behavior, just run the following:

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

However, if you decide 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 on a conceptual level than just providing a solution.

PS: I just noticed that MonadPlus and msum are indeed a bit too restrictive for this purpose, Alternative and asum would have been enough.