Re: [Caml-list] Writing the function Set.map using first-class modules and 4.00 inference

[Gabriel Scherer <gabriel.scherer@gmail.com>]

But when you map from an ASet to a BSet, there is no reason to assume
in general that the mapping function preserves the order, so I don't
think you can do without the O(n log n) worst case bound. You could
provide a specialized function that assumes that the mapping is
order-preserving (you could even check it at runtime with no
additional complexity cost, for added safety), but I'm not sure
order-preserving mappings happen that often in practice.

On Fri, Nov 2, 2012 at 4:11 PM, Radu Grigore <radugrigore@gmail.com> wrote:
> On Friday, November 2, 2012 2:59:17 PM UTC, Radu Grigore wrote:
>> Somebody should put the linear time [of_list] in the standard library.
>
> Actually, that should probably be called [of_sorted_list], to make it clear what it does.  If you worry about having a function that requires a sorted list, then note that there is already one in the standard library: List.merge.
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs