ユーザ定義クラスの既存アルゴリズムへの適用

Pythonで、自分で作成したクラスを、例えばビルトイン関数に与えて、条件を満たすオブジェクトを見つけたい場合、新たに作成しないといけない。
例えば、

class A:

    def __init__(self, id, val):

        self.id = id

        self.val = val

というクラスがあり、Aのシーケンスの中から最小のvalの値を持つオブジェクトのidが欲しいとする。

as = [A(1, 1), A(2, 2), A(3, 0), A(4, 4)]

# ここで、asを直接min()に入れられない!

id_of_min_val = min(as).id  # id_of_min_valは、1になる

min()関数では、単純にシーケンスの要素の最小値を求めるので、そのまま入れると、オブジェクトのアドレス値の最小値になってしまうと思われる。
もちろん、以下のように

class A:

    def __init__(self, id, val):

        self.id = id

        self.val = val

    def __cmp__(self, other):

        return self.val - other.val

という__cmp__()フックメソッドを定義すればOK。しかし、Aを汚したくない場合、これを外付けで与えたい。つまり、

id_of_min_val = min(as, lambda a: a.val).id

のように。しかし、これは、min()関数が、対応していないといけないし、Pythonは関数オーバーロードもできないので、解決できない。
class Aを一時的に拡張して、__cmp__()を定義したAのサブクラスを作成することもできるが、あまりおいしくない。

何かうまい方法があるのかぜひ知りたい…。