From: Radu Grigore <radugrigore@gmail.com>
To: Gabriel Scherer <gabriel.scherer@gmail.com>
Cc: Caml List <caml-list@inria.fr>
Subject: Re: [Caml-list] Writing the function Set.map using first-class modules and 4.00 inference
Date: Fri, 2 Nov 2012 16:21:27 +0000 [thread overview]
Message-ID: <CACMRfCxBi_8w0P6PxL=GjD=uXueDJv6GzfPGMnRHtA_myMW2tg@mail.gmail.com> (raw)
In-Reply-To: <CAPFanBG+OB4iE0N2H2Pp-adNNwwwA5xkmjDNez62LrOOvcq2FQ@mail.gmail.com>
On Fri, Nov 2, 2012 at 4:00 PM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
> 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,
Oops.
> I don't think you can do without the O(n log n) worst case bound.
Probably not.
> I'm not sure order-preserving mappings happen that often in practice.
I can't remember a single instance where I needed to map between sets,
order-preserving or not.
I do, however, often make sets out of lists. In a few cases I know
that the list is sorted by construction. I would like to have
[of_sorted_list]. Or (better?) an [of_list] that works in O(n) for
sorted lists and falls back to O(n lg n) when the list isn't already
sorted. This can't be done without messing with Set's internals, which
is why I think it should be in the interface.
next prev parent reply other threads:[~2012-11-02 16:21 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <fa.FUGAe9RTYsSPA4RwbpKO14B0oVo@ifi.uio.no>
2012-11-02 14:59 ` Radu Grigore
2012-11-02 15:11 ` Radu Grigore
2012-11-02 16:00 ` Gabriel Scherer
2012-11-02 16:21 ` Radu Grigore [this message]
[not found] <fa.yP8czrxqEGCABee05wzAlISIlN4@ifi.uio.no>
[not found] ` <fa.rve4x46ugIvZs4BizovvjOCeTG0@ifi.uio.no>
[not found] ` <fa.i9E+7rAvghoTZ1MXH4g+uL4dpCY@ifi.uio.no>
[not found] ` <fa.AX0JYJa8kXsH/YSZ08tuyBc8m+0@ifi.uio.no>
[not found] ` <fa.YAoOn2iUcpHbr53eeBfGhPTDvtM@ifi.uio.no>
2012-11-05 8:05 ` Radu Grigore
2012-11-05 10:12 ` Gabriel Scherer
2012-11-05 12:02 ` Radu Grigore
2012-11-01 21:00 Jeff Meister
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CACMRfCxBi_8w0P6PxL=GjD=uXueDJv6GzfPGMnRHtA_myMW2tg@mail.gmail.com' \
--to=radugrigore@gmail.com \
--cc=caml-list@inria.fr \
--cc=gabriel.scherer@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).