No instance of (Eq ([a] -> [a])) when pattern matching a list of functions

Consider the following code:

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss
  | (fs == []) = yss
  | otherwise = step fs yss
  where yss = map f xss

It throws the following error:

No instance for (Eq ([a] -> [a])) arising from a use of ‘==’
  (maybe you haven't applied a function to enough arguments?)

  |
3 |   | (fs == []) = res
  |      ^^^^^^^^

fs should be either a list of functions or an empty list, so why is the compiler trying to make a function out of it?

Solution

You can only check lists for equality when their elements can be checked for equality (instances of Eq). You might think this is nonsense, since you're comparing to the empty list, so the value of the elements don't matter. But typewise, Haskell sees all these lists as just lists, and it's unknown if it's empty, so it can't let the comparison happen.

Luckily, there's a function just for this: null :: [a] -> Bool, that checks if a list is empty:

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss
  | null fs = yss
  | otherwise = step fs yss
  where yss = map f xss

(disclaimer: null is actually defined for all foldables, but for our purposes you can treat it as a list function)

You can also use a pattern guard for pattern matching (since pattern matching can recognize empty lists):

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss
  | [] <- fs = yss
  | otherwise = step fs yss
  where yss = map f xss