Custom map function: mapLift

Question

After discussing my current issue at Writing a custom map function, I thought I found a solution to my problem:

mapLift :: Monad m => (a -> b) -> [m a] -> [m b]
mapLift f = map (liftM f)

However, when I use it, I get a compiler error. My actual code is:

actuals     = zipWith mapLift (mapLift eval wffs) assignments

where

eval :: Wff -> Assignment -> Maybe Bool
wffs :: [Either String Wff]
assignments :: [Assignment]

This code gives the following error message:

Couldn't match expected type `a0 -> Wff'
            with actual type `Either String Wff'
Expected type: [a0 -> Wff]
  Actual type: [Either String Wff]
In the second argument of `mapLift', namely `wffs'
In the second argument of `zipWith', namely `(mapLift eval wffs)'

What am I doing wrong? I want to map eval over wffs while preserving any Lefts which give error messages from a previous step in the process.

Edit:

Originally, my idea was that actuals :: [Either String (Maybe Bool)]. However, I am considering modifying eval to be eval :: Wff -> Assignment -> Either String Bool instead, so that actuals :: [Either String Bool].

Update:

I made a typo in my original question. assignments should be:

assignments :: [[Assignment]]

Answer 1

I'm not exactly sure what you want the type of actuals to be, but let's assume it's [Either String (Maybe Bool)]. In that case, let's start with

actuals = zipWith (\ew a -> undefined) wffs assignments

where ew is an Either String Wff and a is an Assignment. What should the body of our function be? Somehow, we need to lift eval into the Either. If the Assignment were in Either as well, we could write liftM2 eval a ew - but it's not. So, we can either use a return a here, or apply eval to its Assignment argument first with flip, and then lift it (or many other possibilities):

actuals = zipWith (\ew a -> liftM (flip eval a) ew) wffs assignments

Optionally, let's golf further:

actuals = zipWith (\ew -> flip liftM ew . flip eval) wffs assignments

In my opinion, neither is as clear as

\ew a -> eval <$> ew <*> return a

where <$> is another name for liftM from Control.Applicative. You can learn more about <$> and <*> in, e.g., "Learn you a Haskell", but basically f <$> ma <*> mb <*> ... <*> mn (equivalently liftMn f ma mb ... mn for small enough n) is the monadic (actually, applicative) version of f a ... n.

At this point you could extract all the failures or whatever. I wonder if the presence of the Maybe and the Either is a sign you could simplify your types slightly. For instance, if your eval could fail to evaluate a Wff, you could use an Either instead of Maybe to record the error. Then, errors will be caught at the step in which they occur, and successes will propagate in the usual way of the Either monad:

-- eval :: Wff -> Assignment -> Either String Bool
actuals :: [Either String Bool]
actuals  = zipWith (\ew a -> ew >>= flip eval a) wffs assignments

See also the errors package, which provides - among its many salutatory features - some helpful combinators to go between Either and Maybe.

I didn't solve the problem in the way you proposed, which was to map over the first list before zipping. But you can do that too, of course:

actuals  = zipWith (\ef a -> liftM ($ a) ef) (mapLift eval wffs) assignments

Here liftM ($ a) is a mildly clever alternative to ef <*> return a.

This seems a bit noisier - zipWith is already a sort of map, a fact you may as well take advantage of.

EDIT in response to OP's edits: If you want actuals :: [[Assignment]] then the needed changes are simple:

actuals :: [Either String (Maybe Bool)]
actuals = 
  concat $ zipWith (\ew -> map (liftA2 eval ew . return)) wffs assignments

The idea here is I again started with something of the form concat $ zipWith f wffs assignments for unknown f (the concat is because the [[]] type needs to be flattened somehow ... if you forgot it, the types wouldn't quite match), and then queried the compiler for the type of f (via writing where f :: (); f = undefined and examining the resulting error message), then wrote the appropriate function, then eta-reduced (golfed). GHC 7.8 will have type holes, allowing you to get the type of an undefined, still-to-be written expression, enabling a much more elegant way of Type-Driven Development (TDD) than is possible today (except in, e.g., Agda).

Adapting this to use list comprehensions and to have type [Either String Bool], as per my original post, is left as a useful exercise :)

Answer 2

fmap or <$> is enough for this case (assuming the output you want is of type [Either String (Maybe Bool)]:

result :: [Either String (Maybe Bool)]
result =  zipWith (<$>) [flip eval $ a | a <- assignments]  wffs

Answer 3

mapLift's first argument is a function from a -> b. You pass as a first argument eval :: Wff -> Assignment -> Maybe Bool. Due to associativity of (->) that means that a unifies with Wff and b with Assignment -> Maybe Bool. That means that the next argument to mapLift, wffs is anticipated to have the type [m Wff] which lets m unify with Either String. That's all fine.

The problem is that the result mapLift eval wffs will end up with type [m b] which, given what m and b unified to is [Either String (Assignment -> Maybe Bool)]. This is going south already, but let's continue to follow it.

zipWith has type (a -> b -> c) -> [a] -> [b] -> [c] and we pass the first argument to it as mapLift :: (s -> t) -> [m s] -> [m t]. This means that zipWith ends up unifying a with the function type (s -> t), b with [m s] and [c] with [m t] such that

zipWith mapLift :: [s -> t] -> [[m s]] -> [[m t]]

Now let's pass in the result (mapLift eval wffs) and watch the fireworks.

zipWith mapLift :: [s -> t] -> [[m s]] -> [[m t]]
                (mapLift eval wffs) :: [Either String (Assignment -> Maybe Bool)]

In order to proceed the typechecker must unify [s -> t] with [Either String (Assignment -> Maybe Bool)]. The outer [] is dispatch immediately, but we still need to find a way to show s -> t ~ Either String (Assignment -> Maybe Bool) which is just impossible due to the wrapping Either String.

---

The problem is that your types don't line up because your semantics are missing a way of unifying the two kinds of failure---the Either String and the Maybe. Fortunately, this is doable by unpacking the Either into functions which take an Assignment. Here's one way

fixEither :: Either String (Assignment -> Maybe Bool) -> (Assignment -> Maybe Bool)
fixEither (Left _)  _ = Nothing
fixEither (Right f) a = f a

---

Now finally, if we were to try running

zipWith mapLift (map fixEither $ mapLift eval wffs) assignments

there'd still be a problem as

zipWith mapLift (map fixEither $ mapLift eval wffs)
  :: [[m Assignments]] -> [[m (Maybe Bool)]]

while assignments :: [Assignments] won't match. We need to wrap assignments in at least another layer of [] and some m. Furthermore, it's not clear what m you want.

---

What this means is you probably haven't defined your algorithm well enough yet.

I would always recommend doing a recursive algorithm or one that uses just "plain" map first to test that you understand completely how the various layers of lists and functions and monads interleave. The shortcuts afforded by fmap and liftM are very powerful but take some time to get right.