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

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