Can anyone explain set
? I tried doing some stuff to see what’s going on with these: #lang racket
(define set1 (set 'b 'c 'comment))
(define set2 (set 'b 'c 'joe))
(define set3 (set 'b 'c))
(for [(s (list set1 set2 set3))]
(displayln s))
But the output is so confusing: >
#<set: comment c b>
#<set: c b joe>
#<set: c b>
I was trying to understand them since I saw them being used in code elsewhere, but I’m confused as to how they are ordered. Are they ordered at all? From https://docs.racket-lang.org/reference/sets.html?q=set it just lists a bunch of procedures to create sets and mentions: “Creates a <https://docs.racket-lang.org/reference/sets.html?q=set#%28tech._hash._set%29|hash set> with the given _v_s as elements. The elements are added in the order that they appear as arguments, so in the case of sets that use https://docs.racket-lang.org/reference/Equality.html?q=set#%28def._%28%28quote._~23~25kernel%29._equal~3f%29%29\|equal? or https://docs.racket-lang.org/reference/Equality.html?q=set#%28def._%28%28quote._~23~25kernel%29._eqv~3f%29%29\|eqv?, an earlier element may be replaced by a later element that is https://docs.racket-lang.org/reference/Equality.html?q=set#%28def._%28%28quote._~23~25kernel%29._equal~3f%29%29\|equal? or https://docs.racket-lang.org/reference/Equality.html?q=set#%28def._%28%28quote._~23~25kernel%29._eqv~3f%29%29\|eqv? but not https://docs.racket-lang.org/reference/Equality.html?q=set#%28def._%28%28quote._~23~25kernel%29._eq~3f%29%29\|eq?.” But these don’t seem to be added in the order they appear in arguments? How are they sorted?
A set
is like a set in mathematics. There’s no order. Only thing that matters is whether an element belongs to the set or not.
The sentence added in the order they appear matters if you add the “same” element twice.
In that case the last element is stored in the set.
I see! Is this similar to unordered_map
in other languages? so set-member?
would take constant time?
You can see sets as “maps” from element to true or false. But most languages have a separate data structure for sets.
Oh I think I meant unordered_set
in C++, which has constant lookup times to check if the element is in the set or not. The docs don’t seem to mention a specific time for set-member?
If you need a map, then in most cases you want to use a hash table, but there are other options.
Since we use map
for something else in Racket, we use the word dict
for dictionary instead (if you want to look it up in the docs).
Determining membership of an element is more or less constant.
Got curious, my second Google result URL looks a little familiar: https://users.cs.northwestern.edu/~robby/courses/395-495-2013-fall/three-algorithms-on-braun-trees.pdf :slightly_smiling_face:
Thank you for the answer. Something new here in racket, what is the difference between sets that are “mutable with strongly-held keys” and “mutable with weakly-held keys”?
The garbage collector is allowed to reuse space occupied by values that can no longer be reached from live values. If for example you have allocate a list (list 1 2 3)
and store it in a variable (define foo (list 1 2 3))
then the value is live. If at a later time, you do (set! foo 42)
then the list value can no longer be reached, and the memory where the list is stored can be reused.
Now normally when you put values into hash table or set, and that hash table or set is live, then the values used for keys will be live too.
But suppose you want to insert a key into a set and want it to be automatically removed, when the garbage collector finds out that key can’t be reached from other parts of your program, then you need a data structure that has “weakly held keys”.
In short: Strongly vs weakly held indicated whether the garbage collector can remove the key, if it is otherwise dead.
Wouldn’t we always be able to reach the key, as long as the corresponding hash-table or set is still live?
I am thinking of the primitive types of integer and symbol here of course
Yes for standard strongly held keys. And that’s potentially a problem: it means a value that you would like the GC to remove can be kept a live by holding it in the hash table. In other words, you need to remove it manually.
That’s why hash tables with weakly held keys were introduced. The garbage collector simply ignores connections from such hash tables to keys - and that allows otherwise dead keys to be removed.
A more precise description: https://docs.racket-lang.org/reference/weakbox.html?q=weakly
You usually want strongly held keys. Weak references have niche use cases. They’re sometimes used in caches, where you want to hold on to something you computed just in case you need it again soon, but you still want to let the garbage collector reclaim it if you’re running low on memory.
how do i safely upgrade racket to the last version? i have many scripts/programs made… also is there an alternative for virtual envs?
What do you mean by “safely upgrade”?
Is there a string function that unconditionally casts something to a string? I know there’s number->string
list->string
etc, but I just want a to-string
procedure if there is one
Type safety here is not important
Basically I want to store to a buffer first before I print. Usually I would just do (printf "~a ~a ~a" symbal namber bolean)
, but in this case I need to check for errors first