Why are the items in Julia's Sets mutable, but there is no immutable version of the latter?


  1. First, clarify a point: a set in Julia is an “immutable type”, but in its definition (’ set.jl ‘), a set is represented as a “wrapper around a Dict”, and this “immutability” is represented as "you cannot change the dictionary (’ dict 'field) wrapped in it".
  2. Secondly, according to the source code of Julia v1.9.1, the feature of Julia collection “element disorder does not repeat” comes from the disordered non-repeatability of its dictionary key.
  3. In addition, in assembly, C and other languages that are closer to hardware, the length of the array cannot be changed, and its immutable version is similar to the Tuple in Julia.
  4. In the case of immutable contents, the actual performance of immutable arrays is usually better than that of mutable arrays.

Based on the above background, the problem are as follows:


Requirements: Use an immutable Set of elements, immutable number of elements, and want to outperform Julia’s built-in ‘set’ type

Conflict: Set in Julia is’ element variable ‘and’ element number variable ’

Solution attempts before asking questions:

  1. When searching on Discourse, there was no Topic about “immutable set”
  2. Try to write an type named of ImmutableSet{T} <: AbstractSet by containing a Tuple as the only field, and find that its performance is not as good as the built-in Set
  3. In GitHub - JuliaLang/julia: The Julia Programming Language, search on all Issues, not found with “immutable collections” about the Topic
  4. Trying to search all GitHub repositories written in Julia, there is no repository related to “Immutable Set”

My code of the trial on ImmutableSet{T}

struct ImmutableSet{T} <: Base.AbstractSet{T}

    global _ImmutableSet(tuple::Tuple, T::Type) = new{T}(

ImmutableSet{T}() where {T} = _ImmutableSet(Tuple{}(), T)
ImmutableSet{T}(s::ImmutableSet{T}) where {T} = @show ImmutableSet{T}(s.tuple)
ImmutableSet{T}(itr) where {T} = _ImmutableSet(Tuple{Vararg{T}}(itr), T)
ImmutableSet() = ImmutableSet{Any}()

ImmutableSet(itr) = _ImmutableSet(itr, Base.IteratorEltype(itr))
_ImmutableSet(itr, ::Base.HasEltype) = ImmutableSet{eltype(itr)}(itr)

function _ImmutableSet(itr, ::Base.EltypeUnknown)
    T = @Base.default_eltype(itr)
    (isconcretetype(T) || T === Union{}) || return grow_to!(ImmutableSet{T}(), itr)
    return ImmutableSet{T}(itr)

Base.empty(s::ImmutableSet{T}, ::Type{U}=T) where {T,U} = ImmutableSet{U}()

Base.isempty(s::ImmutableSet) = isempty(s.tuple)
Base.length(s::ImmutableSet)  = length(s.tuple)
Base.in(x, s::ImmutableSet) = in(x, s.tuple)

Base.copy(s::ImmutableSet) = copymutable(s)
Base.copymutable(s::ImmutableSet{T}) where {T} = ImmutableSet{T}(s.tuple)

Base.iterate(s, i...) = iterate(s.tuple, i...)

function Base.show(io::IO, s::ImmutableSet)
    if Base.isempty(s)
        if Base.get(io, :typeinfo, Any) == Base.typeof(s)
            Base.print(io, "ImmutableSet()")
            Base.show(io, Base.typeof(s))
            Base.print(io, "()")
        Base.print(io, "ImmutableSet(")
        Base.show_vector(io, s)
        Base.print(io, ')')

# alias
const ISet::Type = ImmutableSet

# test
@show s = ISet()
@show s = ISet([1,2,3])
@show s = ISet((1,2,3))
@show s = ISet(Set([1,2,3]))
@show s = ISet(ISet([1,2,3]))
@show s = ISet(1=>2)
@show s = ISet(Dict(

@time for i in 1:0xff
    Set(j for j in 1:i)

@time for i in 1:0xff
    ImmutableSet(j for j in 1:i)


One of the related discussions about “immutable set”:

GitHub - noahbenson/Air.jl: Light-weight functional collections and utilities for Julia. ?