Checking in four directions for board game win

Question

I have the following code which I would like to simplify in Haskell, although I'm not sure how. I recall that I can use monads to simplify a case chain when the result of the case leads onto a next bit of code but in my example, I return from the function when I get a value, and continue to the next bit of code if I don't get a value (Nothing).

checkWon :: Board -> Maybe Col
checkWon board = let moves = pieces board
                     n     = target board
                     col   = snd (moves !! 0) in
    case east moves col n of
        Just c  -> Just c
        Nothing ->
            case west moves col n of
                Just c -> Just c
                Nothing ->
                    case north moves col n of
                        Just c -> Just c
                        Nothing ->
                            case south moves col n of
                                Just c -> Just c
                                Nothing -> Nothing

The only other thing I've tried is using if statements where I calculate all the values of the functions before-hand and test against them in a if-else branch; but this still feels verbose. Is there any syntactic sugar in Haskell to simplify this, or is my current solution the best option? Maybe I would need to structure my code so I don't fall into this example?

Answer 1

Nice question! This is a little trickier than the usual “clean up a string of Maybes” in that you want short-circuiting on the Just case, and continued computation on Nothing. There is—of course—a function for that. Skip to the bottom for the answer, or read through for how you might find or derive it.

Finding the Answer

Hoogle. Pretty much always Hoogle. Think about what you've got and what you need, then start testing types against Hoogle. In this case you've got a sequence of Maybe a values that you want to reduce to a single value. The key insight is that the sequence must all be of the same Maybe a type, so it's possible (and thus probably necessary) to create a list (an actual [Maybe a]) of them. Thus our candidate type signature—

? :: [Maybe a] -> Maybe a

Pop that type signature into Hoogle and the very first thing that comes up is—

-- "base" Control.Monad
-- | This generalizes the list-based concat function.
msum :: MonadPlus m => [m a] -> m a

Test it in GHCi and—

> msum [Nothing, Just 1, Just 2]
Just 1
> msum [Just 1, Nothing, Just 2]
Just 1
> msum [Nothing] :: Maybe Int
Nothing

Yep, that's what we want.

Deriving the Answer

There are probably two different ways you might come up with your own solution. Either start at the concrete and generalize, or cobble a solution from typeclasses down.

From the Concrete

Consider again the type of the function you need.

? :: [Maybe a] -> Maybe a

A no-frills solution to this with primitive recursion and pattern matching should be self-obvious (or will be with experience).

firstJust :: [Maybe a] -> Maybe a
firstJust []             = Nothing
firstJust (Nothing:ms)   = firstJust ms
firstJust (j@(Just _):_) = j

From there we can deploy our usual bag of tricks higher-order functions to write this more idiomatically.

firstJust :: [Maybe a] -> Maybe a
firstJust = foldr orElse Nothing
    where
        orElse :: Maybe a -> Maybe a -> Maybe a
        orElse Nothing    m = m
        orElse j@(Just _) _ = j

Now a few facts may percolate to the top of your brain and strike you as insight.

1. Maybe encapsulates a notion of “failure”.
2. orElse provides an alternative value in the case of failure.
3. Alternative is a typeclass that exists.

So we get a spiffy one-liner—

firstJust :: [Maybe a] -> Maybe a
firstJust = foldr (<|>) Nothing

From the Typeclass Down

This all depends on which tools you're most familiar with. If you're a Monoid fan and used to relying on newtypes you may recognize the pattern of condensing a list of values as Control.Monoid.mconcat. Then you just need to write or choose an appropriate Monoid instance, and of course if you're really on top of the ball you'll know that one already exists.

import Control.Monoid
import Data.Coerce (coerce) -- GHC 7.8.1

firstJust :: [Maybe a] -> Maybe a
firstJust = getFirst . mconcat . coerce
-- Compatible with older GHC but slower, `getFirst . mconcat . map First`

Just the Answer

This version relies on MonadPlus, which ties up all of the other concepts we used and provides various handy functions to leverage their combined power. This version is as terse as it's gonna get.

import Control.Monad (msum) -- Or, Control.Applicative.asum

checkWon :: Board -> Maybe col
checkWon board = msum [ east moves col n
                      , west moves col n
                      , north moves col n
                      , south moves col n
                      ]
    where
        moves = pieces board
        n     = target board
        col   = snd (moves !! 0)

Answer 2

If you were going to use a monad, the Maybe monad wouldn't be the right choice for this logic. Your logic uses Nothing as a signal to keep going; the Maybe monad uses it as a signal to stop.

It's a little difficult to follow the code, because I don't know the types of a lot of things. I'm going to assume that east/west/north/south are functions that take moves, col, and n as arguments.

Assuming I've guessed correctly, you can do this: map (\dir -> dir moves col n) [east, west, north, south]