Question: I'm trying to use Data.Map to map strings to functions. The issue I'm having is that the main error handling in my program uses an Either monad, and `Map.lookup` will return `Maybe ([SomeVal] -> Either ValError SomeVal)`. How can I make `Map.lookup` play nicely with the Either monad in this case?

```
apply :: String -> [SomeVal] -> Either ValError SomeVal
apply s args = (Map.lookup s prims) >>= \fn -> fn args

prims :: Map String ([SomeVal] -> Either ValError SomeVal)
prims = Map.fromList
    [("key", function)
    ,("key2", function2)
    ]

::> apply "key" [val1, val2, val3]

```

Answer: 
The other answers have explained how to turn `Maybe` into `Either` in general. However for `Data.Map` specifically, instead of `Map.lookup`, you can use `Map.findWithDefault`, which doesn't wrap in a `Maybe` and allows you to choose what to do with non-existing keys.
The [`Control.Error` package](http://hackage.haskell.org/package/errors-1.2.1/docs/Control-Error-Util.html) has a nice function

```
note :: e -> Maybe a -> Either e a
note e Nothing  = Left e
note _ (Just a) = Right a

```

which is useful for "upgrading" `Maybe`-like failures to `Either`-like ones.

```
lookupNote :: k -> Map.Map k v -> Either ValError v
lookupNote k = note (Missing k) . lookup k

```

It also has many others like this for mapping between transformers of `Either` and `Maybe` and generic `MonadPlus` instances. I highly recommend that package.