OK, je suis convaincu qu'on peut le descendre à n*log(n) (tu prends un hash commutatif, et tu utilises une structure de donnée moins "impérative" qu'un tableau), mais la constante sera probablement moins bonne qu'avec add_c donc il vaut peut être mieux le garder.
Est-ce que le fait de vérifier si l'argument a bien été évalué est si prohibitif que ça ? Parce que sinon il suffit de supprimer add et d'utiliser add_c à la place, et puis d'appeler eval de façon paresseuse quand on en aura besoin, du coup on peut se débarrasser de tous les _c.