ERROR - Inferred type is not general enough

Question

I am trying to write a simple higher order function in Haskell which takes two arguments:

1. A list of functions of any type.
2. A list of (Numbers or Strings or Boolean, etc) --> any type

The function should apply all the functions in the first list to all the elements in the the second list, store the values in a list, and return the list. An example of the program is:

Main> apply [(^2),(^3),(^4)] [2..8]
--result: --[4,8,9,16,25,27,32,36,49,64,81,125,128,216,256,343,512,625,1296,2401,4096]

The type of the function must be:

apply :: Ord u => [v->u]->[v]->[u]

To do that I've used two helper functions and used recursion. My program is this:

apply :: Ord u => [v->u]->[v]->[u]             
apply p s = myApply p s []              --line 59--

myApply :: Ord u => [v->u]->[u]->[u]->[u]
myApply f_list num_list starterlist
    | null f_list = starterlist
    | otherwise = myApply (tail f_list) (num_list) ( applyList (head     f_list) num_list starterlist )

applyList :: Ord u => (v->u)->[u]->[u]->[u]
applyList f num_list starterlist
    | null num_list = starterlist
    | otherwise = applyList f (tail num_list) ( (head num_list) :     starterlist )

I get the error:

ERROR "Lab2.hs":59 - Inferred type is not general enough
*** Expression    : applyList
*** Expected type : Ord a => (b -> a) -> [a] -> [b] -> [a]
*** Inferred type : Ord a => (a -> a) -> [a] -> [a] -> [a]

Any idea what is wrong the with types?

Answer 1

Variation on a theme: taking into Willem's comment indicating that this is a pretty convoluted code (making it difficult to analyze) I'd start with a simpler code, without stating any types at all, to first get a simple working case (that is, a function that produces the expected output), still using a helper function, and recursion:

apply fs     []  = []
apply []     xs  = []
apply (f:fs) xs  = (helper f xs) ++ (apply fs xs)

helper f []     = []
helper f (x:xs) = f x : helper f xs

Then I would ask the Haskell compiler to give me information about what type signature it inferred:

*Main> :t apply
apply :: [t1 -> t] -> [t1] -> [t]

By realizing that t1 -> t maps to your v->u, I can see that the type signature can also be written as:

[v -> u] -> [v] -> [u] 

Doing the similar for helper, you will end up with the following:

apply :: [v->u] -> [v] -> [u]             
apply fs     []  = []
apply []     xs  = []
apply (f:fs) xs  = (helper f xs) ++ (apply fs xs)

helper :: (v -> u) -> [v] -> [u]
helper f []     = []
helper f (x:xs) = f x : helper f xs

From here, you can work your way by adding Ord constraint, and build up sorting functionality, etc.

Answer 2

The reason why you get this error is because there are conflicting type signatures:

apply :: Ord u => [v->u]->[v]->[u]
apply p s = myApply p s []              --line 59--

myApply :: Ord u => [v->u]->[u]->[u]->[u]
myApply f_list num_list starterlist
    | null f_list = starterlist
    | otherwise = myApply (tail f_list) (num_list) ( applyList (head     f_list) num_list starterlist )

As you can see, the apply function immediately calls the myApply function. Since myApply has signature [v -> u] -> [u] -> [u] -> [u], it means that apply can only have signature [v->u] -> [u] -> [u].

A quick fix is to generalize both myApply and myApplyList to [v -> u] -> [v] -> [u] -> [u]. Now the compile will also detect an error you've made in your applyList function: you forgot to call f on the head num_list. So you can fix it and obtain the following code:

apply :: Ord u => [v->u]->[v]->[u]             
apply p s = myApply p s []              --line 59--

myApply :: Ord u => [v->u]->[v]->[u]->[u]
myApply f_list num_list starterlist
    | null f_list = starterlist
    | otherwise = myApply (tail f_list) (num_list) ( applyList (head     f_list) num_list starterlist )

applyList :: Ord u => (v->u)->[v]->[u]->[u]
applyList f num_list starterlist
    | null num_list = starterlist
    | otherwise = applyList f (tail num_list) ( (f (head num_list)) :     starterlist )

Nevertheless, this code is quite unelegant and uses way to many functions and arguments. You can replace it entirely with a single list comprehension:

apply :: [v -> u] -> [v] -> [u]
apply fs xs = [f x | f <- fs, x <- xs]

Based on your comment you also have to sort the values later in the process, you can do this by using the sort :: Ord a => [a] -> [a] builtin:

-- sorting variant
apply :: Ord u => [v -> u] -> [v] -> [u]
apply fs xs = sort [f x | f <- fs, x <- xs]

This generates the required result:

Prelude Data.List> (\fs xs -> sort [f x | f <- fs, x <- xs]) [(^2),(^3),(^4)] [2..8]
[4,8,9,16,16,25,27,36,49,64,64,81,125,216,256,343,512,625,1296,2401,4096]