It explodes because of the #:lazy? contract imposed on the value returned from the first function, right? And it called that function itself, so I’m not seeing much action-at-a-distance.

I’m not seeing an inconsistency here, just a choice of two legitimately different notions of what a set does. If it’s data that can be traversed and copied without losing anything, then the non-lazy behavior covers it. If it’s an object that can have arbitrary impersonation and mutation going on in the background, then the lazy behavior ensures the contract will be enforced after accounting for all of that.

There may be a self-consistent way for set-add to create a set entry that isn’t subject to any prior #:lazy? contracts. However, keeping track of which contracts apply to which subsets of elements could get rather complex.

The inconsistency in my mind is that whether to check a contract lazily enough is supposed to be a matter of performance tradeoffs, not semantics tradeoffs

Using lazy contracts on immutable data structures is a way to pay the cost of checking only for the elements that are accessed, rather than the whole collection

I’m not sure what distinction you’re drawing there. In the example, the “semantic” distinction is whether there’s an error or not, right? But in order to get them to match error-for-error, you’d have to make them both “pay the cost” of checking. The lazy contract doesn’t pay the cost of checking elements that aren’t accessed, which can cause an error discrepancy for certain examples. The non-lazy contract doesn’t pay the cost of checking new elements, giving you a discrepancy in the particular example you wrote.

you could certainly have a data structure where (a) access was checked lazily and (b) new elements were not checked at all

Potentially, there could be a whole “pay the cost when?” checklist, including options for caching (e.g. memoizing contract results per set element) or only performing a check some small fraction of the time…

I think that’s why I made sense of it with the data/object semantic distinction at first, ’cause distinguishing things by performance or how many errors they detect could broaden the design space drastically.

That being said, the historical distinction is probably like “is this contract allowed to store itself in the contracted value or not (i.e., is it higher-order)?”… right? And that does seem like more or less a performance distinction.

I think the option samth mentioned is the right one to go with

since immutable collections are supposed to be covariant

I think it’s hard to currently implement efficiently with the primitives racket provides but that’s not a problem with the concept

primitives at the racket/set and racket/generic layers? or at the chaperones and impersonators layer?

The latter. hash-set on an impersonated hash keeps the impersonator

You could implement the intended semantics even given that but it would be hard/inefficient

ahhh, right yes, that does make it tricky

And if you think about the implementation it’s clear why it works that way

You’d need basically a pair of tables to do what we want

In my case I’m making my own collections APIs, they’re using racket/generic, and the implementations don’t depend on racket’s persistent hash table implementation (since mine are sorted and thus use RB trees)

so I think it might work out

racket hashes are HAMTs right?

Yes

hmm

if the semantics of lazy contracts were “elements might not be checked unless accessed” rather than “elements won’t be checked unless accessed”, then the implementation could give up on laziness upon (persistent) modification and just check everything right away

so, (set-add numbers 'foo) wouldn’t error, but it would force numbers to check that all elements in it are actually numbers, so that it can then discard the impersonator

Perhaps imposing an element contract on an RB tree should store it in the root node (possibly strengthening another contract already there), and then operations that traverse into the tree should gradually push it in toward the elements until each of the elements has finally been replaced with a contracted version.

Then, when an element is set-add’ed into an existing tree, the existing contracts latent in that tree naturally don’t apply to it; they only apply to the subtrees they’re on.

That could probably work, but it’s complicated to implement and I doubt it matters much. The use case where you’re passing a contracted persistent collection from one API to another API that’s inserting a bunch of stuff into it, and also you really want lazy checking, probably isn’t all that common

really what I need is something that’s robust enough that I can make lazy checking the default and users won’t have to think about it

I was getting excited about lazy checking as a default… maybe too excited? lol

Lazy checking as a default is what I want, yes. But I think persistently adding stuff to the collection will by default turn off that laziness. My hope is that sorted-set/c won’t have to expose a #:lazy? parameter to users.

which means the semantics need to not be weird in corner cases

I’ve been thinking sometimes about a system of contracts that ensures that contracted operations don’t suddenly traverse over things in ways that change their algorithmic complexity. I guess I’ve been thinking about it idly ever since I heard about shallow type enforcement for Typed Racket.

Hmm, if I had something like

  (-> (sorted-set/c string?) void?)
  (void))

(discard (sorted-set 1 2 3))

In a world which wasn’t fully committed to lazy contracts, I would want that to traverse the set and fail the contract. That way I better protect discard’s API in case I want to extend it to do something else with a set of numbers someday. In other words, I expect contracts to be best-effort and as eager as possible by default.

Of course, that does affect discard’s algorithmic complexity. That’s why I find the lazy contract world compelling too. XD