Anonymous function conceptual understanding

Question

I am trying to learn and understand the design of Haskell. I am currently on Lambda / Anonymous functions and I was wondering.

Why aren't function types instances of the Eq class?

Prelude> (\z -> z + 5) == (+5)

On this question, I was wondering if it is because z can be anything and may be even be a free variable, in all lambda functions, so it would be a design flaw to make lambda functions of type Eq.

Why aren't function types instances of the type class Show?

Prelude> (\q -> q - 2)

I appreciate any clarification.

Many thanks in advance!

Answer 1

Are these functions the same or are they different:

dbl1 :: Int -> Int
dbl1 x = x + x

dbl2 :: Int -> Int
dlb2 x = 2 * x

?

For some functions it's "easy" for the compiler to see that they contain the same logic. But most functions would be extremely difficult to compare. Then there are functions that are logically different, but behave the same - like dbl1 and dbl2 above. So, you would have to make a choice to either test them against every possible value, or decide they are not equal. The former is completely impractical in most cases. The latter is definitely not desirable or intuitive. Now, consider that the problem is already too difficult to solve, and then throw in IO...

Answer 2

A critical concept that I feel neither Dave nor Peter have stressed enough is this: two functions are equal if and only if (a) they have the same type, and (b) for every possible argument you can give them, they both produce the same result.

Now, with this clear, the answer for Eq is just what they said. Peter points out that an Eq instance for functions would need to be able to analyze two arbitrary functions and correctly determine whether they produce the same result for any two inputs. And as Dave points out, this is actually mathematically impossible; any checker that tried to compare arbitrary functions will fail for some functions—meaning it will hang or produce a wrong answer for some cases.

You will see Haskell programmers talking about equality of functions all the time, however, but most of the time what they mean is that humans have proven that some two functions are equal. For example, the function composition operator is defined like this:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

We can now prove that for all possible h :: c -> d, g :: b -> c and h :: a -> b, f . (g . h) == (f . g) . h. It's pretty easy in this case, we just expand the expressions according to the definition of (.), and we get the same thing for both:

f . (g . h) = f . (\y -> g (h y))          -- expand `g . h` by definition
            = \x -> f ((\y -> g (h y)) x)  -- expand `f . (\y -> g (h y))`
            = \x -> f (g (h x))            -- apply the inner lambda

(f . g) . h = (\y -> f (g y)) . h
            = \x -> (\y -> f (g y)) (h x)
            = \x -> f (g (h x))

But this can only be done for carefully chosen functions, and computers generally can't do it well or reliably. For any program you write to try and test the equality of arbitrary functions, there will be some functions for which it will either produce the wrong answer or loop forever.