[racket-dev] Lists aren't sets, but have set-like operations

The implementation of set-union for hash sets would be unnecessarily slow
if that's how I wrote it.  It's faster to extract the hash tables and
operate directly on those.  It's even faster still to find the largest
immutable hash table in the argument list and start from that.  On top of
that, the operation is specified, since before my changes, to go through
the arguments and reject any hash sets that use a different notion of
equality, so that the output of set-union has a meaningful semantics.  For
an arbitrary other set representation, I don't necessarily know what the
notion of equality is.  So currently, I just reject all of them.

Carl Eastlund


On Thu, Aug 22, 2013 at 1:52 PM, Jay McCarthy <jay.mccarthy at gmail.com>wrote:

> I find this an unsatisfying consequence of the implementation and not
> necessary. For instance, you could implement set-union purely
> generically as:
>
> (define (set-union a b)
>  (for/fold ([a a]) ([e (in-set b)]) (set-add a e)))
>
> and then it would work for everything. Right?
>
> Jay
>
> On Thu, Aug 22, 2013 at 10:14 AM, Carl Eastlund <cce at ccs.neu.edu> wrote:
> > Set-union never worked for even different hash set representations.  Even
> > before I touched the code, the union of an eq set and an eqv set, for
> > instance, caused a runtime error.
> >
> > Generics do not have multiple dispatch.  That's not a mechanism we have
> > right now.  And "fallbacks" are for when there's no method implemented
> for a
> > given receiver value, they're not particularly related to a question of
> "are
> > these things the same type".
> >
> > I chose to keep the semantics that union and operations like it only work
> > with the same representation.  Partly because that's how things already
> > were, and partly to set the precedent that generics authors don't have to
> > write two versions of every method.  Perhaps this wasn't the best idiom,
> but
> > it's what I wrote.  Perhaps there's a better idiom for fallbacks that
> makes
> > this work more cleanly.  Anyway, right now, generic sets are designed so
> you
> > can use any one representation, but they don't combine representations.
> >
> > Carl Eastlund
> >
> >
> > On Thu, Aug 22, 2013 at 9:03 AM, J. Ian Johnson <ianj at ccs.neu.edu>
> wrote:
> >>
> >> No, it doesn't seem to be using the fallback in this case.
> >>
> >> ianj at sampson:~/racket/racket/bin$ ./racket -il xrepl
> >> Welcome to Racket v5.90.0.8.
> >> -> (set-union '() (set))
> >> ; in-list: contract violation
> >> ;   expected: list?
> >> ;   given: (set)
> >> ; [,bt for context]
> >> ->
> >>
> >> -Ian
> >> ----- Original Message -----
> >> From: "Sam Tobin-Hochstadt" <samth at cs.indiana.edu>
> >> To: "J. Ian Johnson" <ianj at ccs.neu.edu>, "Carl Eastlund" <
> cce at ccs.neu.edu>
> >> Cc: dev at racket-lang.org, "Matthew Flatt" <mflatt at cs.utah.edu>
> >> Sent: Thursday, August 22, 2013 8:51:30 AM GMT -05:00 US/Canada Eastern
> >> Subject: Re: [racket-dev] Lists aren't sets, but have set-like
> operations
> >>
> >> Wait, `set-union` of two different set representations doesn't work?
> >>
> >> Sam
> >>
> >> On Thu, Aug 22, 2013 at 8:07 AM, J. Ian Johnson <ianj at ccs.neu.edu>
> wrote:
> >> > You misunderstand. I used set-union, but single dispatch saw '() and
> >> > used list-union for the '() (set) combination.
> >> > -Ian
> >> > ----- Original Message -----
> >> > From: "Sam Tobin-Hochstadt" <samth at cs.indiana.edu>
> >> > To: "J. Ian Johnson" <ianj at ccs.neu.edu>
> >> > Cc: dev at racket-lang.org, "Matthew Flatt" <mflatt at cs.utah.edu>
> >> > Sent: Thursday, August 22, 2013 8:02:50 AM GMT -05:00 US/Canada
> Eastern
> >> > Subject: Re: [racket-dev] Lists aren't sets, but have set-like
> >> > operations
> >> >
> >> >
> >> >
> >> > But 'list-union' is not a generic operation so it isn't surprising
> that
> >> > this didn't work. To do this generically, you'd need to use
> 'set-union'.
> >> >
> >> > Sam
> >> > On Aug 22, 2013 7:59 AM, "J. Ian Johnson" < ianj at ccs.neu.edu > wrote:
> >> >
> >> >
> >> > The problem manifested itself when I got an exception that in-list
> can't
> >> > be called on (set), which really confused me. (set? '()) answered
> true, so
> >> > it tried to do (list-union '() (set)), which failed.
> >> > Generic sets as they are don't work generically. Some action should be
> >> > taken. Either set? means what it once did, or we do some awfully slow
> >> > multiple dispatch for set operations. My bias shows.
> >> > -Ian
> >> > ----- Original Message -----
> >> > From: "Matthew Flatt" < mflatt at cs.utah.edu >
> >> > To: "Carl Eastlund" < cce at ccs.neu.edu >
> >> > Cc: "J. Ian Johnson" < ianj at ccs.neu.edu >, "dev" <
> dev at racket-lang.org >
> >> > Sent: Thursday, August 22, 2013 7:22:25 AM GMT -05:00 US/Canada
> Eastern
> >> > Subject: Re: [racket-dev] Lists aren't sets, but have set-like
> >> > operations
> >> >
> >> > How much should we prioritize backward compatibility in this case?
> >> >
> >> > One possibility is to make `set?' mean `hash-set?', and add
> >> > `generic-set?' in place of the current `set?'. That's uglier,
> >> > obviously, but it would be better if we want to prioritize backward
> >> > compatibility.
> >> >
> >> > At Wed, 21 Aug 2013 19:14:06 -0400, Carl Eastlund wrote:
> >> >> Ah, yes. The set? predicate no longer distinguishes a representation.
> >> >> There are several predicates for the original set type, now called
> >> >> "hash
> >> >> sets": set-eq?, set-eqv?, set-equal?, set-mutable?, set-immtuable?,
> and
> >> >> set-weak?. I didn't add the basic "hash-set?", but perhaps I should.
> >> >> It's
> >> >> a weird name, since "hash-set" and "hash-set!" are already existing,
> >> >> unrelated functions.
> >> >>
> >> >> Carl Eastlund
> >> >>
> >> >>
> >> >> On Wed, Aug 21, 2013 at 7:08 PM, J. Ian Johnson < ianj at ccs.neu.edu >
> >> >> wrote:
> >> >>
> >> >> > Okay, I can abide. However, that doesn't really get at my
> >> >> > frustration. I'm
> >> >> > using the set constructor, that appears to now be an
> >> >> > immutable-custom-set
> >> >> > with make-immutable-hash as its make-table. So what I'm looking for
> >> >> > is not
> >> >> > set?, but set-immutable?, as it's a distinct (family of) struct
> types
> >> >> > that
> >> >> > won't clash with the primitive data that I'm otherwise using.
> >> >> > -Ian
> >> >> > ----- Original Message -----
> >> >> > From: "Carl Eastlund" < cce at ccs.neu.edu >
> >> >> > To: "J. Ian Johnson" < ianj at ccs.neu.edu >
> >> >> > Cc: "dev" < dev at racket-lang.org >
> >> >> > Sent: Wednesday, August 21, 2013 6:58:56 PM GMT -05:00 US/Canada
> >> >> > Eastern
> >> >> > Subject: Re: [racket-dev] Lists aren't sets, but have set-like
> >> >> > operations
> >> >> >
> >> >> >
> >> >> > Ian, sets are now a generic datatype, like dictionaries.
> Association
> >> >> > lists
> >> >> > are dictionaries, and lists are now sets. They're also streams and
> >> >> > sequences. They're not just "set-like".
> >> >> >
> >> >> >
> >> >> >
> >> >> > Carl Eastlund
> >> >> >
> >> >> >
> >> >> > On Wed, Aug 21, 2013 at 6:56 PM, J. Ian Johnson < ianj at ccs.neu.edu>
> >> >> > wrote:
> >> >> >
> >> >> >
> >> >> > I just wasted about 2 hours tracking down a bug that ended up being
> >> >> > due to
> >> >> > (set? '()) now evaluating to #t. I have no problems with set-union,
> >> >> > intersection, etc. being defined for lists, but to treat lists as
> >> >> > sets
> >> >> > always is perverse to me. The contracts for set operations should
> use
> >> >> > set-like? for (or/c set? list?) and keep the two constructions
> >> >> > separate.
> >> >> >
> >> >> > This conflation is almost as bad as treating empty list as false.
> >> >> >
> >> >> > -Ian
> >> >> > _________________________
> >> >> > Racket Developers list:
> >> >> > http://lists.racket-lang.org/dev
> >> >> >
> >> >> >
> >> >> >
> >> >> >
> >> >> _________________________
> >> >> Racket Developers list:
> >> >> http://lists.racket-lang.org/dev
> >> > _________________________
> >> > Racket Developers list:
> >> > http://lists.racket-lang.org/dev
> >>
> >
> >
> > _________________________
> >   Racket Developers list:
> >   http://lists.racket-lang.org/dev
> >
>
>
>
> --
> Jay McCarthy <jay at cs.byu.edu>
> Assistant Professor / Brigham Young University
> http://faculty.cs.byu.edu/~jay
>
> "The glory of God is Intelligence" - D&C 93
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20130822/d858cb56/attachment-0001.html>