Add Pattern to List Removing Duplicates

Question

Lets say I have a list of patterns

p={
  HoldPattern[f[x___]] :> {x},
  HoldPattern[f[a_,b_]] :> {a,b},
  HoldPattern[f[a_,a_]] :> {a,a},
  HoldPattern[f[x_]] :>x
} 

what is the most elegant way to add another pattern to the list while removing all duplicates? For example let's say I what to add f[c_,d_]:>code then f[a_,b_] should be mapped as a duplicate but not f[a_,a_].

Answer 1

Automatic behaviors

It's worth noting that replacement rules have precedence by order, therefore you may not need to remove the duplicates. For example:

Prepend[p, HoldPattern[f[c_, d_]] :> foo[c, d]];

f[1, 2] /. %

foo[1, 2]

For the specific rules you show and for matching of the left-hand-side only you can use the automatic duplicate removal of definitions made with Set or SetDelayed:

Cases[p, (_[lhs_] :> rhs_) :> (lhs := rhs)];

f[c_, d_] := foo[c, d]

DownValues[f]

{HoldPattern[f[a_, a_]] :> {a, a}, HoldPattern[f[c_, d_]] :> foo[c, d], 
 HoldPattern[f[x_]] :> x, HoldPattern[f[x___]] :> {x}}

If the sorting that occurs here is undesired that can be temporarily disabled with SetSystemOptions["DefinitionsReordering" -> "None"] as I did for How to select minimal subsets?

Manual filtering

A manual approach for matching the LHS of arbitrary rules is to replace all Pattern names with indexes before comparing:

uniform[(lhs_ -> _) | (lhs_ :> _)] :=
 lhs /. MapIndexed[
   Verbatim[Pattern][#, x_] :> Pattern[#2, x] &,
   Cases[lhs, Verbatim[Pattern][name_, _] :> HoldPattern[name], -1] // DeleteDuplicates
  ]

p2 = Prepend[p, HoldPattern[f[c_, d_]] :> foo[c, d]];

First /@ GatherBy[p2, uniform]

{HoldPattern[f[c_, d_]] :> foo[c, d], HoldPattern[f[x___]] :> {x}, 
 HoldPattern[f[a_, a_]] :> {a, a}, HoldPattern[f[x_]] :> x}

Other approaches

If the methods above are not sufficient you may be facing a complicated problem; see:
How to generally match, unify and merge patterns?

From Oleksandr's answer there we learn of Internal`ComparePatterns which may be used for the automatic definition filtering illustrated in section one. If one is comfortable with using undocumented internal functions one might use:

ptest[(L1_ -> _) | (L1_ :> _), (L2_ -> _) | (L2_ :> _)] :=
  Internal`ComparePatterns[L1, L2] === "Identical"

p2 = Prepend[p, HoldPattern[f[c_, d_]] :> foo[c, d]];

DeleteDuplicates[p2, ptest]

{HoldPattern[f[c_, d_]] :> foo[c, d], HoldPattern[f[x___]] :> {x}, 
 HoldPattern[f[a_, a_]] :> {a, a}, HoldPattern[f[x_]] :> x}

For matching both the LHS and RHS of rules you can try the method I provided for:
Pattern matching a pattern with patterns.