Haskell function works with char type but is not working with number type

Question

I'm really new to Haskell and functional programming in general, and I can't figure out why I keep getting "Non type-variable argument in the constraint: Num [a] (Use FlexibleContexts to permit this)" errors.

I have this function for looking up value in dictionary by key:

lookup1 x [] = []
lookup1 x (h:t) = if x == fst h then snd h else lookup1 x t

and it is working fine with char type, for example, lookup1 "b" [("a", "aa"), ("b", "bb"), ("c", "cc")] returns "bb". But when I try the same with number type, for example lookup1 2 [(1, 11), (2, 22), (3, 33)] I get this:

* Non type-variable argument in the constraint: Num [a]
  (Use FlexibleContexts to permit this)
* When checking the inferred type
    it :: forall a. Num [a] => [a]

Weird thing is that if I define the same function in ghci it works with both chars and numbers.

As I also need function for returning all values from dictionary where dictionary can contain duplicate keys, I tried this workaround:

    lookup_duplicates x [] = []
    lookup_duplicates x (h:t) = if x == fst h then (snd h):(lookup_duplicates x t) else lookup_duplicates x t 
    lookup1 x (h:t) = let (a:b) = lookup_duplicates x (h:t) in a

which takes first value from lookup_duplicates and it did work fine. But now I have this function that finds all values for given keys in dictionary:

    find_all_values [] (h:t) = []
    find_all_values (g:a) (h:t) = let found = (lookup1 g (h:t)) in (if found == [] then find_all_values a (h:t) else found:(find_all_values a (h:t)))

which also works very good with char types but with number types I get this:

* Non type-variable argument in the constraint: Num [a1]
  (Use FlexibleContexts to permit this)
* When checking the inferred type
    it :: forall a1. (Num [a1], Eq a1) => [[a1]]

Can anyone please guide me to the right direction?

Answer 1

Your first problem is that you don't return a correct value from lookup1 when an item isn't found. You can't just return an empty list, because you aren't necessarily returning a list in the other cases (it depends on the type of value found in the tuples). Instead, you need to return a value of some Maybe type:

lookup1 :: Eq a => a -> [(a, b)] -> Maybe b
lookup1 x [] = Nothing
lookup1 x ((k,v):t) | x == k = Just v
                    | otherwise = lookup1 x t

Alternatively, you could guarantee that list is returned, one containing zero or one values. This isn't ideal, though, since the type doesn't guarantee only an empty or singleton value is returned.

lookup1 :: Eq a => a -> [(a, b)] -> [b]
    lookup1 x [] = []
    lookup1 x ((k,v):t) | x == k = [v]
                        | otherwise = lookup1 x t

The reason your code worked for lookup1 "b" [("a", "aa"), ("b", "bb"), ("c", "cc")] is that you were using String values, and String is just an alias for [Char]; [] was a valid base case in that instance.

Answer 2

Look at

lookup1 x [] = []
lookup1 x (h:t) = if x == fst h then snd h else lookup1 x t

What's its type? The first equation says that we're taking two arguments, where the first is of unknown type, and the second is a list of unknown type, and we're returning another list of unknown type:

lookup1 :: _a -> [_b] -> [_c] -- Not fully solved

In the second equation, when you use fst and snd on the head of your second argument, you force that second argument to be a list of pairs

lookup1 :: _a -> [(_b, _d)] -> [_c]

and since your function can evaluate to snd h, we know that _d must be [_c].

lookup1 :: _a -> [(_b, [_c])] -> [_c]

and since you check (==) between the first argument and fst h, we know that _a ~ _b and Eq _a

lookup1 :: Eq _a => _a -> [(_a, [_c])] -> [_c]

That's all the information we have, so we say we've totally solved this type and replace all the remaining variables with universally quantified types:

lookup1 :: Eq a => a -> [(a, [b])] -> [b]

and if you ask :type lookup1 in GHCi it'll tell you the same. This is wrong, because you can only ever use this to look up lists of things, when you should be able to look up whatever you want! Specifically, this function will either look up the target list, or, if it can't find it, evaluate to [] instead. Also, you say it works fine for Char, and give the example

lookup1 "b" [("a", "aa"), ("b", "bb"), ("c", "cc")]

But that isn't Char! That's [Char] (aka String)! Strings are zero or more characters enclosed in ""; Chars are exactly one character enclosed in ''.

Also, if you tried

lookup1 'b' [('a', "a")]

you'd get "", and that's not really a sensible output, because you don't know if "b" was found and just happened to point to "", or it wasn't there at all and we just defaulted.

When you try

lookup1 2 [(1, 11), (2, 22), (3, 33)]

each numeric literal starts with type Num _a => _a (Haskell numeric literals are polymorphic). The type of lookup1 forces the second element of every pair to also be a list of something, so 11, 22, and 33 take on the type Num [a] => [a], which is not allowed without the FlexibleContexts language extension (and is nonsense regardless).

The correct type for this is

lookup1 :: Eq a => a -> [(a, b)] -> Maybe b
lookup1 _ []     = _ -- Exercise for reader
lookup1 x (e:es) = _

Now, lookupDuplicates (camel case is the convention) should have the type

lookupDuplicates :: Eq a => a -> [(a, b)] -> [b]

which is true for what you wrote, but now lookup1 is bad:

lookup1 x (h:t) = let (a:b) = lookupDuplicates x (h:t) in a

What happens if you give it an empty list? You will try to match it to h:t, which will fail. Worse, you only take the list apart to put it back again. It should just be

lookup1 x es = head $ lookupDuplicates x es
-- Read: First result of looking up x in es

Yet, this is still undesirable. If you don't find your entry anywhere, you throw a runtime error (which you cannot catch unless you're in the IO monad). You want to use another monad, probably Maybe, for this:

lookup1 :: Eq a => a -> [(a, b)] -> Maybe b
lookup1 x es = case lookupDuplicates x es of
                    []    -> _ -- Exercise for reader
                    (e:_) -> _

The listsafe library provides versions of list functions that work in Maybe instead of being partial, so if you had that installed you could say

import qualified Data.List.Safe as LS
lookup1 x es = LS.head $ lookupDuplicates x es

Now, onto findAllValues

findAllValues [] (h:t) = []
findAllValues (g:a) (h:t) = let found = (lookup1 g (h:t))
                            in if found == []
                                  then findAllValues a (h:t)
                                  else found:(findAllValues a (h:t))

You can write this much more clearly:

import Data.Maybe
findAllValues :: Eq a => [a] -> [(a, b)] -> [b]
findAllValues keys dict = catMaybes $ flip lookup1 dict <$> keys
-- Go over the list of keys with (flip lookup1 dict), then remove the Maybes
-- (flip lookup1 dict) is a function that takes a key and looks it up in dict
-- (<$>) is the infix version of fmap which is the general version of map
-- catMaybes :: [Maybe a] -> [a]
-- Nothings stop existing and the Just wrappings evaporate

If you used the

import qualified Data.List.Safe as LS
lookup1 x es = LS.head $ lookupDuplicates x es

version above, then the most general type of lookup is actually (MonadThrow m, Eq a) => a -> [(a, b)] -> m b, which means findAllValues simplifies to:

findAllValues keys dict = concat $ flip lookup1 dict <$> keys

because MonadThrow []. (A failed lookup1 "magically" returns Nothing in some cases and [] in others and Left (SomeException EmptyListException) in yet others, all depending on type.)

Final note: always think of your type signatures first and write them down (at least for top level definitions). It really helps you get a handle on what you should do.