Using type parameters in the types of the fields

General Usage
,
1

I’m not a data structures person, so the right answer here might be “you’re doing it wrong, try this instead”; but I’ll start with the immediate question I have:

in a recursive type, is it not possible to have the type parameters of the fields be related to the type parameters of the struct itself? for example, if one were to try to define:

struct Simplex{T<:Any, dim, size}
    x::Union{NTuple{size, Simplex{T, dim-1}}, T}
end

you get no method matching -(::Typevar, ::Int64).

what I'm actually trying to do

I have data which is ‘shaped’ like a n-dimensional regular simplex, by which I mean I often want the data which is along some specific edge, face, volume, hyper-volume, etc of the simplex. eg, say the data is 1:10 and the dimension is 2 (so size is 4), I would want to represent it like

(
    (1),
    (2, 3),
    (4, 5, 6),
    (7, 8, 9, 10)
)

since I’ll be needing last() (7, 8, 9, 10), last.() (1, 3, 6, 10), and first.() (1, 2, 4, 7) a lot.
or with the same data if the dimension (and size) was 3, I would want it to look like

(
    ((1)),
    ((2), (3, 4)),
    ((5), (6, 7), (8, 9, 10))
)

and the pieces I’d need are last() ((5), (6,7), (8,9,10)), last.() ((1), (3,4), (8,9,10)), last..() ((1), (2,4), (5,7,10)), and first..() ((1), (2,3), (5,6,8)). (if you’re really good at visualizing this kind of thing, you’ll notice those are the four faces on this 3d triangular pyramid)

most of them are 4- or 5- d, where faking it with an array starts getting really confusing; but they can be arbitrarily big (seen up to 10-d so far)

I tried defining it as

b(size, dim) = prod(size:dim+size-1)/prod(1:dim)

struct Simplex{T<:Any, dim, size}
    x::Union{NTuple{size, Simplex{T, dimMinusOne}}, T} where dimMinusOne
    Simplex{T, dim, size}(x::Vector{T}) where {T} = dim==1 ?
        new{T, 1, size}(ntuple(n->Simplex{T}(x[n]), size)) :
        new{T, dim, size}(ntuple(n->Simplex{T, dim-1, n}(x[b(n-1,dim)+1:b(n,dim)]), size))
    Simplex{T}(x::T) where T = new{T, 0, 1}(x)
end

but Simplex{Int, 2, 2}([1, 2, 3]) says there’s no method.

2

It’s not possible to do math on typevars (though just today I see Proof of concept: Allow some limited arithmetic on type vars - Pull Request #62707 - JuliaLang/julia - GitHub). This is why StaticArray’s SMatrix is parameterized like SMatrix{M, N, T, MtimesN} with a “redundant” fourth parameter that is simply required to be the product M*N (the length, which parameterizes the NTuple used for storage).

In your case you can do something similar:

struct Simplex{T<:Any, dim, size, dim1}
    x::Union{NTuple{size, Simplex{T, dim1}}, T}
end
# use inner constructor to set (and require) dim1 = max(dim-1,0)

Do note that your inner simplex is not fully typed (missing size and its own dim1) so you may have a bit of boxing and type instability here.

Personally, I would use a design more like

struct Simplex{T, dim, size, SubSimplex}
    x::NTuple{size, SubSimplex}
end

where SubSimplex is required to be either <:Simplex{T, dim-1} or T. You could use the Union{..., T} like before, but instead I would simply set size=1, SubSimplex=T at the bottom level.

Although I would probably go further and not have a naked T at all, simply define the (0 or 1, I haven’t thought about it) dimensional Simplex{T} to follow all the relevant rules of a scalar.

3

yeah, it’s the 0-d simplex that’s a point; 1-d is a line (vector). first two dimensions are exactly the same as arrays. all three possible n-d regular polytopes are the same in 0- and 1- d.

this sounds like exactly what I want, but still getting a a syntax error trying to define it:

struct Simplex{T, dim, size, SubSimplex} where {SubSimplex <: Simplex{T, dim-1}}
    x::NTuple{size, SubSimplex}
end
ERROR: syntax: invalid type signature


struct Simplex{T, dim, size, SubSimplex} where {SubSimplex isa Simplex{T, dim-1}}
    x::NTuple{size, SubSimplex}
end
ERROR: syntax: invalid type signature

the reason I tried to put a union with the naked T is because if the NTuple is made of Simplex and Simplex is made of NTuple then I don’t know how to stop the infinite loop; if there’s a better way around that, I’m all ears ^^

4

Just do the definition as I wrote it. You can’t enforce the where in the struct definition. The place to enforce this is in an inner constructor.

Here’s a sketch (that almost certainly has multiple errors – I didn’t even check whether this was syntactically correct):

struct Simplex{T, dim, size, SubSimplex}
    x::NTuple{size, SubSimplex}
    function Simplex{T, dim, size, SubSimplex}(subsimplices::NTuple{size, SubSimplex}) where {T, dim, size, SubSimplex}
        SubSimplex <: Simplex{T, dim-1} || error("subsimplices of Simplex{T, dim} must be Simplex{T, dim-1}") # don't allow construction of nonsense simplex
        return new{T, dim, size, SubSimplex}(subsimplices)
    end
end

dimension(::Type{<:Simplex{<:Any, dim}}) where dim = dim
dimension(x::Simplex) = dimension(typeof(x))
Base.eltype(::Type{<:Simplex{T}}) where T = T
Base.eltype(x::Simplex) = Base.eltype(typeof(x))

function Simplex(subsimplices::NTuple{size, SubSimplex}) where {size, SubSimplex}
    # fill parameters to call inner constructor
    return Simplex{eltype(SubSimplex), dimension(SubSimplex)+1, size, SubSimplex}(subsimplices)
end

For a better example, maybe look at how StaticArrays does it.

5

Related links: