1

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.

Improve this question
2
  • 1
    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. Commented Aug 7, 2016 at 20:43
  • I'd also recommend to read about boolean blindness. Commented Aug 7, 2016 at 20:46

3 Answers 3

Reset to default
9

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
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks! Great answer. Thanks for also explaining why this has nothing to do with lazy evaluation. And point taken on my double use of the variable f!
@Ben: I'd add that more generally, things like equality comparisons are eschewed in Haskell. Boolean blindness is the keyword: you rely on expressions of unspecific types like Bool to decide how more specific types like Maybe (Int -> Int -> Int). The preferred solution is to work only with the specific, meaningful types; this prevents a lot of bugs. Pattern matching is great in this regard.
"an instance of Maybe (Integer -> Integer -> Integer)" means a value whose types is Maybe (Integer -> Integer -> Integer).
@immibis That sentence continues "not (Just (+)) or Nothing", but those are values of type Maybe (Integer -> Integer -> Integer). That makes no sense.
@melpomene Indeed, the thing following it doesn't make sense.
1

Indeed, the function (== Nothing) as type (Eq a) => Maybe a -> Bool, in your case, functions not being a member of the Eq typeclass, this doesn't compile.

However you can use the isNothing function from Data.Maybe, or you can define it yourself like this:

isNothing :: Maybe a -> Bool
isNothing Nothing = True
isNothing (Just _) = False

Because you are pattern-matching on the constructor and therefore not using (==), you don't need a to be an instance of Eq.

Improve this answer

Comments

1

This is because you're using k of type Maybe (Integer -> Integer -> Integer) in a comparison expression. Haskell does not know how to compare two functions.

A solution is to 'unpack' the return of lookup.

import qualified Data.Map as Map                                                                 

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

f :: Char -> Integer -> Integer -> Integer                                                       
f key v1 v2 =                                                                                    
  case Map.lookup key d of                                                                       
    Nothing -> 0                                                                                 
    Just f -> f v1 v2

.

λ> f '-' 1 2                                                                                     
0                                                                                                
λ> f '+' 1 2                                                                                     
3                                                                                                
λ>
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.