Anonymous function conceptual understanding

Question 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...

Question 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.

Question 3

Gödel's incompleteness theorems imply that any Eq instance for functions must either give inaccurate results or sometimes return ⊥. That's not what we expect from Eq instances (at least for finite data).

show is supposed to provide Haskell source code that evaluates to its input. That is awkward when compiling a Haskell program, because now you must keep a copy of the source code for every function, bloating the executable, even if the Show instance for functions is never used.

It is possible to provide a Show instance for functions that breaks this rule, e.g. by always returning "{-function-}", or (for some types) returning the type of the function. Early versions of Haskell did. But it was felt that breaking this rule was not a good idea.

Question 4

I like everyone's answers...they seem to make sense. I wouldn't imagine, at this stage, answering why functions are not set by default as instances of Eq and Show. This is just some experimentation that might give you ideas for trying it out yourself:

Prelude> :set -XFlexibleInstances
Prelude> instance Eq (Int -> Int) where x == y = map x [0..10] == map y [0..10]
Prelude> ((\z -> z+5) :: Int -> Int) == ((+5) :: Int -> Int)
True
Prelude> instance Show (Int -> Int) where show x = show (zip [0..10] (map x [0..10]))
Prelude> (\q -> q-2) :: (Int -> Int)
[(0,-2),(1,-1),(2,0),(3,1),(4,2),(5,3),(6,4),(7,5),(8,6),(9,7),(10,8)]