Simplify code by distributing []

Question

I have the following function

type Assignment = [(Ref, Val)]

predi2 :: [(Val,Val)] -> Ref -> Ref -> (Maybe Assignment -> [Maybe Assignment])
predi2 f k1 k2 = \ma -> case ma of
    Nothing -> [Nothing]
    Just a -> case lookup k1 a of
        Nothing -> [Nothing]
        Just e1 -> case lookup k2 a of
            Nothing -> [Nothing]
            Just e2 -> if elem (e1, e2) f
                then [Just a]
                else []

Given all the instances of Maybe, I thought I could simplify it to something more simple inside the Maybe monad:

predi2 :: [(Val,Val)] -> Ref -> Ref -> (Maybe Assignment -> [Maybe Assignment])
predi2 f k1 k2 = [\ma -> do
    a <- ma
    e1 <- lookup k1 a
    e2 <- lookup k2 a
    if elem (e1, e2) f then (return a) else ???]

But my problem is the final else, where I need to return nothing.

That is my question: Is it possible to return nothing in a way such that [f a] = []?

Answer 1

No, it's not.

I would write your predi2 function more like this:

predi2 f k1 k2 ma = fromMaybe [Nothing] $ do
    a <- ma
    e1 <- lookup k1 a
    e2 <- lookup k2 a
    if elem (e1, e2) f then return [Just a] else return []

i.e.

• post-process the monadic computation, using fromMaybe
• have the list inside the monadic computation, instead of outside it
• have the False branch of the if statement count as successful (by the standards of the monadic computation)

Answer 2

I think it's possible, if I understand the question correctly.

What strikes me is that you're trying to track two different kinds of failure, the empty list indicates that the final elem lookup failed. The Maybe indicates that either (1) the original Maybe Assignment was Nothing or (2) either lookup failed. We can be more explicit about this. The return type ought to be something like

data FailureType = Existence | SeenInF
Either FailureType Assignment

Then we'll just translate the Maybe type failures into Eithers using the errors module.

import Control.Error
predi2 :: [(Val, Val)] -> Ref -> Ref -> Maybe Assignment -> Either FailureType Assignment
predi2 f k1 k2 ma = do a  <- note Existence ma
                       e1 <- note Existence $ lookup k1 a
                       e2 <- note Existence $ lookup k2 a
                       note SeenInF $ guard $ (e1, e2) `elem` f
                       return a

This solution is a little strange since it involves translating between the two failure monads, Maybe and Either, but note is an incredibly useful function for this purpose.