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

user_11370915 0
Viewed 143

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?

instance equals haskell
3 Answers

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
user_59231390

In addition to Aplet123's answer, you can also use pattern matching to match the empty list directly (since [] is a data constructor):

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

However, you are stopping your recursion one step too early. You can match the list of functions against [] directly as the base case, in which case the list of values is the return value.

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step [] xss = xss
step (f:fs) xss = step fs (map f xss)
-- step [] = id
-- step (f:fs) = step fs . map f

At this point, you may want to explore using a fold in place of explicit recursion.

user_11268410

As per chepner's advice, I have rewritten the original code as a fold.

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step cs xss = foldl rmap xss cs
  where rmap xs f = map f xs

I do wonder if there's a more elegant way of doing this than reversing the arguments, but the signature for foldl has forced my hand.

user_113709150
Related