Data.Map with functions as values in Haskell

Question

I'm a Haskell newbie trying to understand how to work with the Data.Map structure, lazy evaluation, and the Maybe type.

In Python I can define a dictionary structure whose values are functions. Given a key I can then use the corresponding function:

d = {"+": lambda x,y: x+y}

def f(key, v1, v2):
    if key in d:
        return d[key](v1, v2)
    else:
        return 0

I've tried to do a similar thing in Haskell but it does not compile.

d = Map.fromList [('+', (+))]

f :: Char -> Integer -> Integer -> Integer
f key v1 v2 =
    if k == Nothing
        then 0
        else f v1 v2
    where
        k = Map.lookup key d
        (Just f) = k

This doesn't compile and returns an error like

No instance for (Eq (Integer -> Integer -> Integer))

I believe it's because Map.lookup '+' d only returns an instance of Maybe (Integer -> Integer -> Integer) not (Just (+)) or Nothing. And I assume this has to do with lazy evaluation.

Is there a Haskell-like way to do this kind of thing? Am I working with the Maybe type incorrectly? Can I force evaluation of the lookup?

This came up because I was trying to implement a reverse polish calculator in Haskell. I used the dictionary to organize the possible functions I could be using. I found a nice solution (https://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm#Haskell) without a dictionary but now I just want to understand how to properly access values in a Haskell Data.Map.

Note that, even if that worked, it is considered non idiomatic in Haskell. In many imperative programming languages it is somehow common to find methods like obj.getX() which will throw an exception unless one checks obj.hasX() beforehand. This is frowned upon in Haskell, since it is easy to forget the check: in your code, if you used f without checking k == Nothing first, you would crash the program. Fortunately, pattern matching provides a better way to solve it: in a case we are prodded to consider all the constructors, and act accordingly -- this is always safe. — chi

melpomene melpomene · Accepted Answer · 2016-08-07T19:58:14

The problem is this expression: k == Nothing

It requires k to support equality testing. The type of k is Maybe (Integer -> Integer -> Integer). Maybe T supports equality testing if T does, but Integer -> Integer -> Integer doesn't: You can't compare functions for equality. So the whole expression doesn't typecheck.

I don't know what you mean by "an instance of Maybe (Integer -> Integer -> Integer)": Classes have instances (which are types), but Maybe (Integer -> Integer -> Integer) is not a class, it's an ordinary type. The class in question is Eq (which provides the == method). The issue is that function types don't have an Eq instance. This has nothing to do with lazy evaluation, either.

The solution is to just use pattern matching instead:

f key v1 v2 =
    case Map.lookup key d of
        Nothing -> 0
        Just f  -> f v1 v2
        -- but consider naming 'f' something else;
        -- the surrounding function is already called 'f'

Alternatively you can use one of the Maybe helper functions:

f key v1 v2 =
    maybe 0 (\f -> f v1 v2) (Map.lookup key d)

Or even:

f key v1 v2 =
    fromMaybe (\_ _ -> 0) (Map.lookup key d) v1 v2

Data.Map with functions as values in Haskell

3 Answers