Choosing implementation depending on class instances using rewriting rules

[Dinko Tenev]

On Wed, Jun 3, 2009 at 7:43 PM, Daniel Peebles <pumpkingod at gmail.com> wrote:
> An equality-based (n^2) nub
> works "fine" on infinite lists, whereas any O(n log n) sort-based nub
> must necessarily evaluate the entire list before being able to return
> the value.

No.  You just need to keep anything seen so far in a container with O(
log n ) insert/lookup times.

> The original n^2 nub also returns the elements in the order
> of their first appearance rather than sorted order.

Where exactly did sorted order come in?


D