16

It sounds silly, but I can't get it. Why can the expression [] == [] be typed at all? More specifically, which type (in class Eq) is inferred to the type of list elements?

In a ghci session, I see the following:

Prelude> :t (==[])
(==[]) :: (Eq [a]) => [a] -> Bool

But the constraint Eq [a] implies Eq a also, as is shown here:

Prelude> (==[]) ([]::[IO ()])

<interactive>:1:1:
No instance for (Eq (IO ()))
  arising from use of `==' at <interactive>:1:1-2
Probable fix: add an instance declaration for (Eq (IO ()))
In the definition of `it': it = (== []) ([] :: [IO ()])

Thus, in []==[], the type checker must assume that the list element is some type a that is in class Eq. But which one? The type of [] is just [a], and this is certainly more general than Eq a => [a].

IMHO this should by ambiguous, at least in Haskell 98 (which is what we are talking about)

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
Ingo
  • 36,037
  • 5
  • 53
  • 100
  • 3
    With GHC (not GHCi) I've got `Ambiguous type variable \`a' in the constraint \`Eq a' arising from a use of \`=='` – kennytm May 21 '10 at 18:06
  • @Kenny - yes thats what I expected before I tried in ghci - the greater my surprise. Thanks for the hint, now my world order is restored :) – Ingo May 21 '10 at 18:14
  • It's interesting Hugs gives the expression `[] == []` type `Eq a => Bool`. – sdcvvc May 21 '10 at 23:14
  • 1
    Sorry for "necroposting", but there is no way to specify the context for `[] == []` is there? Without specializing `[]` themselves. – Dan M. Jul 10 '16 at 20:19

2 Answers2

19

GHCi has extended rules for type defaulting, which is what tripped you up. In this case, I believe it would default the ambiguous type to (). The subtle ways that GHCi behaves differently are nice for the sake of better interactivity, but they do occasionally result in confusion...

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
  • 8
    @camccann: run `ghci -Wall`. then `[] == []` gets `Warning: Defaulting the following constraint(s) to type '()'` – yairchu May 21 '10 at 18:28
  • 1
    The extended defaulting only matters when you want to show or run the code. The :: (Eq a) => [a] -> Bool type is entirely correct. – Don Stewart May 21 '10 at 18:32
  • 1
    @Don Stewart: That type is of course fine--I think what confused Ingo is rather `([] == []) :: Bool`, where the ambiguous `Eq a` constraint is satisfied by defaulting to `()`, as yairchu demonstrated. – C. A. McCann May 21 '10 at 18:34
  • Certainly, that's defaulting at work. But his initial type appears wrong-- there's no Eq [a] constraint. – Don Stewart May 21 '10 at 18:42
  • @Don Stewart: Ah, I didn't even notice that. I'd guess that as a typo, since that's obviously not what GHCi would report. Maybe he's using Windows and copy-paste from a terminal window doesn't work well. – C. A. McCann May 21 '10 at 18:47
  • @Don - Yes, constraint as per ghci is Eq [a], not Eq a. Which is fine as (==) :: Eq a => a -> a -> Bool – Ingo May 21 '10 at 18:49
  • @Ingo: Really? It ought to simplify that to just an `Eq a` constraint. What version of GHC are you using? – C. A. McCann May 21 '10 at 18:52
  • @camccann 6.4.2. But for me this is ok, as (==) :: Eq a => a -> a -> Bool One substitution [b] for a, and we get the above. Yet, the constraint for b that arises is not shown, perhaps because it is implied? – Ingo May 21 '10 at 18:57
  • @Ingo: Wow, that's an ancient version of GHC. – kennytm May 21 '10 at 19:00
  • @Kenny: It appears that "ancient" nowadays means "more than half a year old"? :) – Ingo May 21 '10 at 19:03
  • Anyway, it's at least 2008, so it should cover the 98 standard very well. – Ingo May 21 '10 at 19:04
  • 4
    @Ingo: Hehe. (Actually [GHC 6.4.2 is released in 2006](http://haskell.org/ghc/download_ghc_642.html), i.e. 4 years ago. The current version is 6.12.2, i.e. 4 major versions apart.) – kennytm May 21 '10 at 19:55
1

GHC infers the most general type:

(==[]) :: (Eq a) => [a] -> Bool

It should be read as:

  • if you have an instance of Eq a,
  • then Haskell can give you a function from lists of those 'a's to Bool

So yes, the implication here is that you have an instance of Eq for elements of the list, and GHC already has an instance for lists in general (relying on Eq for the elements), so we get a nice general type.

The type checker "assumes" you can supply an Eq a instance when called at a particular type.

I can't reproduce your results of having a Eq [a] constraint.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • though Kenny above got different results with GHC. Note: We are talking haskell 98, I am sure some fancy GHC extensions are clever enough to type it correctly, yet I still do not understand how exactly. IMHO, this is really an ambiguous case. – Ingo May 21 '10 at 18:17
  • 1
    @Ingo: `(== [])` isn't ambiguous, just polymorphic as usual; it will work the same (and correctly) in GHCi or otherwise. As for GHC extensions, you can enable the same extended defaulting that GHCi uses, but I don't know why you'd want to... – C. A. McCann May 21 '10 at 18:41
  • @Don: Perhaps you have different version/flags? As for me: X:\fc3>ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Prelude> :t (==[]) (==[]) :: (Eq [a]) => [a] -> Bool Prelude> – Ingo May 21 '10 at 18:51
  • 3
    @Ingo: Wow, retro! Do you have shag carpet and listen to disco, too? :) Seriously, newer versions have nice features, why not upgrade... – C. A. McCann May 21 '10 at 18:56
  • 4
    GHC 6.4.2 was released was released 5 years ago. We're at GHC 6.12.2 now. – Don Stewart May 21 '10 at 21:49
  • Weird that several people over the last few days have been using 6.4 or 6.6. I googled for "GHC", and the first result is... "download ghc 6.12". So I have no idea where people are getting this from... – jrockway May 22 '10 at 03:50
  • Hunh. If I google for "download haskell compiler" or "download GHC" it decides to show links to download pages for GHC 6.6.1 and 6.2.1 (!) respectively. – C. A. McCann May 22 '10 at 22:21
  • 1
    @Don Stewart: http://i.imgur.com/Bz0DR.png Those aren't unreasonable search terms, are they...? I don't even know... – C. A. McCann May 22 '10 at 23:23