Maybe you haven't applied enough arguments to a function?

Question

I am learning Haskell in a course in university, and there is a Exam-Exercise, where we need to define a function which takes a List of functions [(Int ->Int)] and another parameter of Type Int and returns an Int. So the Type should be

compose :: [(Int ->Int)] -> Int -> Int.

The function should return a composition of the functions in the list from left to right and apply it to the 2nd parameter. I tried the following :

compose :: [(Int -> Int)] -> Int -> Int
compose [] x = x
compose (f:fs) x  
    |fs == [] = f x
    |f  : (compose fs x)

But the compiler throws an error :

003Exam.hs:24:22:
    Couldn't match expected type ‘Int’ with actual type ‘[Int -> Int]’
    In the expression: f : (compose fs x)
    In an equation for ‘compose’:
        compose (f : fs) x
          | fs == [] = f x
          | otherwise = f : (compose fs x)

003Exam.hs:24:28:
    Couldn't match expected type ‘[Int -> Int]’ with actual type ‘Int’
    In the second argument of ‘(:)’, namely ‘(compose fs x)’
    In the expression: f : (compose fs x)

If I leave the last line away, like :

compose :: [(Int -> Int)] -> Int -> Int
compose [] x = x
compose (f:fs) x  
    |fs == [] = f x

then I also get an error - this is the one that I realy don't understand :

003Exam.hs:23:13:
    No instance for (Eq (Int -> Int))
      (maybe you haven't applied enough arguments to a function?)
      arising from a use of ‘==’
    In the expression: fs == []
    In a stmt of a pattern guard for
               an equation for ‘compose’:
      fs == []
    In an equation for ‘compose’: compose (f : fs) x | fs == [] = f x

I would be happy for any help that clarifies what I am doing wrong.

Answer 1

First of all, (:) is only for adding elements at the front of a list (or pattern match against those), so you have to replace

f : compose fs x

with

f (compose fs x)

Next, you have to use an expression of type Bool or a pattern match in a guard:

| fs == []  = -- this line is still wrong, see below
| otherwise = f (compose f xs)

However, there is no Eq instance for functions. The equivalence of two functions is undecidable (in general), so use null :: [a] -> Bool instead of (==) :: Eq a => [a] -> [a] -> Bool:

compose :: [(Int -> Int)] -> Int -> Int
compose [] x = x
compose (f:fs) x  
  | null fs   = f x
  | otherwise = f (compose fs x)

Since compose [] x is the same as x you can even remove the check:

compose :: [(Int -> Int)] -> Int -> Int
compose []     x = x
compose (f:fs) x = f (compose fs x)

Exercises

• Extend compose [(+1), (+2)] 1 (replace it with its definition) without getting rid of intermediate terms. Do you notice a pattern?
• Does this pattern remind you of a library function?
• Try to use that library function in order to write compose.