Order-sensitivity in SpecConstr

Consider this code

foo :: Int -> (a,a) -> Maybe (a,a)
foo 0 p     = Just p
foo n (x,y) = foo (n-1) (y,x)

wombat1 = foo 20 ("yes", "no")
wombat2 xs ys = foo 3 (xs, ys)

Here foo is lazy in its second argument, but it does decompose it, so SpecConstr should catch it. We have two calls, one of which (in wombat2)is polymorphic. Ideally we would like to see

  RULE  forall a. forall n::Int, x::a, y:;a. foo n (x,y) = $sfoo n x y

which fires on all three calls to foo. And that is what happens if the declaration of wombat2 appears before wombat1. But as written, we get this specialisation (only):

 RULES: "SC:$wfoo0" [2]
            forall (sc_sVo :: [Char])
                   (sc_sVp :: [Char])
                   (sc_sVn :: GHC.Prim.Int#).
              $wfoo_sV6 @String sc_sVn (sc_sVo, sc_sVp)
              = $s$wfoo_sVt sc_sVo sc_sVp sc_sVn]

and indeed the call in wombat2 is never specialise. Boo!

Diagnosis

We discover two calls but in callsToNewPats we see

              -- Remove duplicates
              non_dups = nubBy samePat new_pats

Moreover samePat treats both calls (one polymorphic and one at type String) as the "same". So the nubBy drops one of them, and which is dropped is order-dependent.

Why does it treat them the same? Because of Note [Ignore type differences] which points out that we don't want lots of identical specialisations, differing only in their type. Good point, but the consequences are bad.

Cure

We need some form of patten-generality comparison, to make the polymorphic pattern "beat" the monomorphic one.

This pattern-subsumption approach would then be vulnerable to generating multiple specialisations for calls

  foo 10 ("foo", "baz")    -- Called at String
  foo 10 (True, False)     -- Called at Bool

Ideally we'd like to to generalise to a specialisation that works for all types, not just String and Bool. And that must be possible, because if the function scrutinises its argument, can't be poymorphic in it. Using foo's polymorphic type, We ought to be able to generalise from a single call

  foo @Int 10 (3,4)

to the more general form

  foo @a n (x::a, y:;a)

That looks do-able, but not trivial.

Meanwhile, a simple subumption check would avoid discarding the wrong pattern. It risks generating lots of identical specialisations, while we currently arbitrarily pick one. But we have other (crude) ways of throttling lots of specialisations.