Haskell: Applying function to all combinations of arguments

Question

I am posting below some code in Haskell. Please treat the code as an example, which I am going to use, to explain what I would like to know.

try :: [[Char]] -> [[Char]] -> [[Char]] -> [[Char]]
try (a:as) (b:bs) (c:cs)  | ((checkIfCorrect a b c) == True) =  a:b:[c]
                          | otherwise = try as bs cs 

checkIfCorrect :: [Char] -> [Char] -> [Char] -> Bool
checkIfCorrect a b c = True

Eventually, checkIfCorrect returns True for only one combination of arguments. checkIfCorrect is really long function, so I decided to post substitute here. In the example above, function checkIfCorrect is applicated (by function try) to: first [Char] on the first list, first [Char] on the second list and first [Char] one the third list. If first guarded equation is not fulfilled, function checkIfCorrect is applied to: second [Char] on the first list ... and so on. What I would like to reach, is to applicate function checkIfCorrect (by function try) to all combinations of [Char]s from all lists ([[Char]] ). I mean the following (e.g.): third [Char] on the first list, eighth [Char] on the second list, eleventh [Char] on the third list and so on. Everyone with everyone. How could I easy reach that?

Answer 1

I just wanted to show you an alternative way of writing @WillemVanOnsem's code. I'm guessing that you're a Haskell beginner, so hopefully this answer will give you a tiny glimpse of a rich and beautiful idea which you'll soon be learning about in full as you progress with the language. So don't worry too much if you don't understand everything about this code right away; I'm just trying to give you a taste!

A list comprehension can always be reformulated using the list monad:

import Control.Monad (guard)

try as bs cs = head $ do
    a <- as
    b <- bs
    c <- cs
    guard $ checkIfCorrect a b c
    return [a,b,c]

I'm using do notation as a special notation for nested loops: for each a in as, for each b in bs, and for each c in cs, we yield [a,b,c] if checkIfCorrect returns True. The translation from list comprehensions is simple: "enumeration" parts of the list comprehension turn into "binds" using <-, "filter"s turn into calls to guard, and "yield"s turn into returns.

In an imperative language like Python you might write it like this:

def try(as, bs, cs):
    for a in as:
        for b in bs:
            for c in cs:
                if checkIfCorrect(a, b, c):
                    yield [a,b,c]

Like politics under the Western neoliberal hegemony, the imperative code gradually marches rightward. "Staircase" code like this actually crops up quite frequently in imperative programming (think of "callback hell" in JS), so monads were invented to help counteract this tendency. They turned out to be so useful that a special syntax was invented for them, namely do-notation.

Answer 2

Yes, you can make it also look more elegant with list comprehension:

try :: [[Char]] -> [[Char]] -> [[Char]] -> [[Char]]
try as bs cs = head [ [a,b,c] | a <- as, b <- bs, c <- cs, checkIfCorrect a b c ]
--                    \__ __/   \__________ ____________/  \__________ _______/
--                       v                 v                          v
--                     yield           enumeration                 filter

The code works as follows: the right part of the list comprehension consists out of an "enumeration" part (denoted by the comment section). Since we write a <- as, b <- bs, c <- cs it means that a will take any value from as, and for every such a, b will take any value of bs, etc. So that means every possible combination will be emitted.

Next there is the "filter" phase: there is a predicate checkIfCorrect a b c that will be called and only if that predicate returns True, the result will be "yielded".

On the left side we see "yield". It describes what to add to the list (based on the enumeration) given the filter succeeds. If that happens we add [a,b,c] to that list. If there are multiple such configurations that succeed, we might end up with a list containing multiple solutions. Note however that list comprehension is done lazily: so as long as you do not ask for at least one such element, it will not generate the first element, nor the second, etc.

Now we also need head (in front of the list comprehension). head :: [a] -> a returns the first element of the list. So try will return the first element that satisfies the condition.

Answer 3

While both Willem Van Onsem's and The Orgazoid's answers are good (upvoted), you can also approach part of the problem in a more generalised way, and not only for lists.

For the following, you're going to need these imports:

import Control.Monad (MonadPlus, mfilter)
import Data.Maybe (fromMaybe, listToMaybe)

If I'm understanding the question correctly, you want to try all combinations of as, bs, and cs. You can typically achieve combination-like behaviour with the Applicative typeclass:

combinations = (,,) <$> as <*> bs <*> cs

(,,) is a function that creates triples (three-element tuples) from three individual values.

This works for lists, because lists are applicative:

*Prelude> (,,) <$> [1,2] <*> ["foo", "bar"] <*> [True, False]
[(1,"foo",True),(1,"foo",False),(1,"bar",True),(1,"bar",False),(2,"foo",True),(2,"foo",False),(2,"bar",True),(2,"bar",False)]

but it also works for e.g. Maybes:

*Prelude> (,,) <$> Just 1 <*> Just "foo" <*> Just False
Just (1,"foo",False)

With that, you can now define the core of your function:

try' :: MonadPlus m => ((a, a, a) -> Bool) -> m a -> m a -> m a -> m [a]
try' predicate as bs cs =
  tripleToList <$> mfilter predicate combinations
  where
    combinations = (,,) <$> as <*> bs <*> cs
    tripleToList (a, b, c) = [a, b, c]

You'll notice that this helper function is completely generic. It works for any MonadPlus instance of any contained element a.

Here are some examples:

*Answer> try' (const True) ["foo", "bar", "baz"] ["qux", "quux", "quuz", "corge"] ["grault", "garply"]
[["foo","qux","grault"],["foo","qux","garply"],["foo","quux","grault"],["foo","quux","garply"],["foo","quuz","grault"],["foo","quuz","garply"],["foo","corge","grault"],["foo","corge","garply"],["bar","qux","grault"],["bar","qux","garply"],["bar","quux","grault"],["bar","quux","garply"],["bar","quuz","grault"],["bar","quuz","garply"],["bar","corge","grault"],["bar","corge","garply"],["baz","qux","grault"],["baz","qux","garply"],["baz","quux","grault"],["baz","quux","garply"],["baz","quuz","grault"],["baz","quuz","garply"],["baz","corge","grault"],["baz","corge","garply"]]
*Answer> try' (const False) ["foo", "bar", "baz"] ["qux", "quux", "quuz", "corge"] ["grault", "garply"]
[]
*Answer> try' (const True) (Just "foo") (Just "bar") (Just "baz")
Just ["foo","bar","baz"]
*Answer> try' (const False) (Just "foo") (Just "bar") (Just "baz")
Nothing

You should notice that if predicate always returns False, you'll get nothing back. For lists, you get the empty list; for Maybe, you literally get Nothing.

So far it's all generic, but checkIfCorrect isn't. It also looks like you'd like to get only the first elements that match. You can achieve that by composing try' with checkIfCorrect:

try :: [String] -> [String] -> [String] -> [String]
try as bs cs = fromMaybe [] $ listToMaybe $ try' isCorrect as bs cs
  where isCorrect (a, b, c) = checkIfCorrect a b c

Here, I've created a private isCorrect function in order to uncurry the checkIfCorrect function. I've then used a combination of listToMaybe and fromMaybe to return the first element of the resulting list. Other answers here use head, but that's going to throw an exception if the list is empty, so I used this combination instead, because it's safe.