5

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!

Peter Hall
  • 53,120
  • 14
  • 139
  • 204
AnchovyLegend
  • 12,139
  • 38
  • 147
  • 231
  • 6
    Have you tried implementing one? – is7s Apr 05 '13 at 14:03
  • Yes I have. I understand how they work. But that doesn't really help me understand the language design and why it was made to not be instances of Eq or of type class Show. – AnchovyLegend Apr 05 '13 at 14:06
  • The fact you have to ask already shows that an instance of `Eq` for functions would be confusion because of unclear semantics. When are two functions equal? What would that mean? –  Apr 05 '13 at 14:06
  • 12
    If you had a correct `Eq` instance, you could solve the halting problem by comparing a function with a known function. – phipsgabler Apr 05 '13 at 14:12
  • @Zoidberg. I am not sure. I've come to believe that Haskell never fails to provide a logical explanation to the most unconventional things. So I am simply trying to understand exactly why the above does not work. – AnchovyLegend Apr 05 '13 at 14:12
  • Functions in Haskell are compiled into GHC Core and then into the native code. They don't have string representation at the language level because it's not meaningful, if you really want to see what they "look" like at the implementation level pass "-ddump-simpl" to GHC. – Stephen Diehl Apr 05 '13 at 14:31
  • The following questions have answers describing the problems with comparing functions for equality: http://stackoverflow.com/q/9906628/507803 http://stackoverflow.com/q/4844043/507803 – Heatsink Apr 05 '13 at 14:43

4 Answers4

9

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

Peter Hall
  • 53,120
  • 14
  • 139
  • 204
6

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.

Luis Casillas
  • 29,802
  • 7
  • 49
  • 102
  • 4
    computers can show functions are equal also--the point is that it is not *decidable* (in general), and that goes for humans as well as machines. I can't solve the halting problem in general, can you? – Philip JF Apr 05 '13 at 20:29
  • True. I was trying to simplify, but yeah, it's a bridge too far. I'll edit it. – Luis Casillas Apr 05 '13 at 23:34
  • I wouldn't say that there are functions that cannot be compared for equality. Any possible function-equality-checker has cases that will defeat it, but they're not the same cases for every checker. – Ben Apr 06 '13 at 01:17
4

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.

dave4420
  • 46,404
  • 6
  • 118
  • 152
  • 4
    I disagree with both these answers. The first one because it is _very_ common to have `Eq` instances for infinite data that work exactly as you describe, and since we can represent many functions simply as infinite mappings of input -> output the problem is in fact much the same. Dragging Godel into this seems rather far-fetched (and even dragging in the halting problem is besides the point). Your second point feels similarly silly. – sclv Apr 05 '13 at 14:45
  • 1
    The real issue in both cases is intensional vs. extensional equality (or i guess syntactic vs semantic). The semantics of Haskell dictate the latter but all we can capture for your proposed `Show` is the former. `Eq`, on the other hand, is possible over finite domain things, but that's a narrow subset of what we might want, and inefficient to boot. – sclv Apr 05 '13 at 14:49
  • 4
    No, @sclv, Godel's incompleteness Theorem _is_ relevant. Consider a function that returns all the even numbers and another one that returns the even numbers that are the sum of two smaller primes. Are they equal? I'm impressed if you can write a Haskell program that can solve a problem unsolved by mathematicians for centuries, and which we don't know is solvable. Godel shows that there are unprovable truths in any mathematical system sophisticated enough to include arithmetic - so any Eq instance for functions must be incorrect or incomplete, and incomplete in the sense of does not terminate. – AndrewC Apr 05 '13 at 16:10
  • 4
    @AndrewC, I think the point was `(==)` would return bottom in that case, just as it does for `[1..] == [1..]`, which we (arguably) consider reasonable. – luqui Apr 05 '13 at 16:58
  • 1
    Forget Godel -- that's too strong! Existentional equality is not decidable in general. That's all we need to illustrate the difficulty. Using Godel in this context is like dragging in a jackhammer to unclog a sink. – sclv Apr 05 '13 at 17:46
  • @sclv OK, and indeed my example was `[Integer]` rather than `a -> b` although of course it's equivalent to `Integer -> Bool`. Let's agree it's intractible at least. – AndrewC Apr 05 '13 at 19:15
1

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)]
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61