Type parameter transformation, StaticArray with blade indexing

question
array
type
parametric-types

#1

My goal is to create a new type, let’s say MultiVector which contains an MVector{2^N,T} with 2^N elements, but I am going to define an unusual type of indexing on MultiVector using multivector blades.

With standard arrays, this would look like this

mutable struct MultiVector{T}
    N::UInt8
    v::Vector{T}
end

function Base.getindex(m::MultiVector, i::Int) 
    0 <= i <= m.N || throw(BoundsError(m, i))
    r = sum([binomial(Int(m.N),k) for k ∈ 0:i-1])
    return @view m.v[r+1:r+binomial(Int(m.N),i)]
end

with the expected behavior like this

julia> g = MultiVector{Int}(2,[3,4,5,6])
MultiVector{Int64}(0x02, [3, 4, 5, 6])

julia> g[0]
1-element view(::Array{Int64,1}, 1:1) with eltype Int64:
 3

julia> g[1]
2-element view(::Array{Int64,1}, 2:3) with eltype Int64:
 4
 5

julia> g[2]
1-element view(::Array{Int64,1}, 4:4) with eltype Int64:
 6

However, now I would like to use StaticArrays instead of the standard Array, so I could do

mutable struct MultiVector
    N::UInt8
    v::MVector
end

However, what if I also want to include the parametric type T and also specify the size 2^N, since I am going to be dealing with MVector{2^N,T} essentially. Note that the behavior of MultiVector is going to be different because the indexing is based on a completely different concept.

This is going to be part of my Multivectors package

So basically this is a question about parametric types, what is the best way to specify T and N in the type?


#2

See how it is done in OffsetArrays.jl

Also, I have asked similar question for custom array types here:


#3

Alright, that is somewhat useful, but it doesn’t work the way I want. This is valid,

julia> mutable struct MyArray{T,N,MV<:MVector{N,T}} <: AbstractArray{T,N}
           v::MV
       end

julia> MyArray{Int,3}
MyArray{Int64,3,MV} where MV<:MArray{Tuple{3},Int64,1,3}

However, what I need is an MVector with 2^N elements, which is problematic

julia> mutable struct MyArray{T,N,MV<:MVector{2^N,T}} <: AbstractArray{T,N}
           v::MV
       end
ERROR: MethodError: no method matching ^(::Int64, ::TypeVar)

which is not valid because 2^N is a Type calculation.

Is it necessary to define a method on ^(Int64, ::TypeVar) to solve this?


#4

Perhaps someone like @jeff.bezanson could comment on whether it is possible with Julia to compute on numerical type variables, such as in the situation where the parameter N translates to a parameter 2^N in one of the fields of the parametric type

MyArray{T,N,MV<:MVector{2^N,T}} <: AbstractArray{T,N}

What I would like is for N to be a parameter for a type which contains another parametric type having 2^N as its parameter, dependent on the N parameter of the container parametric type.

So the parameter of the type contained within a parametric type is a transformation of the container’s parametric type, N -> 2^N is the type parameter transformation. Is such a thing possible with Julia?


#5

So it’s not possible to do anything like this with parametric type variables in Julia? Is it a fundamental limitation with the language, or is it just a feature that’s not implemented yet?


#6

I think you’re essentially looking for https://github.com/JuliaLang/julia/issues/18466

So no, this isn’t currently possible in Julia. ComputedFieldTypes.jl can make your life a bit easier, but otherwise the easiest thing to do is something like:

julia> struct MyArray{T, N, MV <: (MVector{N2, T} where N2)}
       end

or:

julia> struct MyArray{T, N, N2, MV <: MVector{N2, T}}
       end

(the only difference is whether you want to expose N2 as its own type parameter).

You can enforce the invariant that MV has N^2 dimensions inside the inner constructor. This is, admittedly, a bit less convenient, but it should perform perfectly well.


#7

Thanks. How does the constructor work for your first option?

julia> struct MultiVector{T, MV <: (MVector{N, T} where N)}
           n::UInt8
           v::MV
       end

julia> MultiVector{Int}(0x2,MVector(3,4,5,6))
ERROR: MethodError: no method matching MultiVector{Int64,MV} where MV<:(MArray{Tuple{N},Int64,1,N} where N)(::UInt8, ::MArray{Tuple{4},Int64,1,4})
Stacktrace:
 [1] top-level scope at none:0

julia> methods(MultiVector)
# 1 method for generic function "(::Type)":
[1] (::Type{MultiVector})(n::UInt8, v::MV) where {T, MV<:(MArray{Tuple{N},T,1,N} where N)} in Main at REPL[14]:2

#8

You can just define some helpful outer constructors:

julia> MultiVector{T}(n::T, mv::MV) where {T, N, MV <: MVector{N, T}} = MultiVector{T, MV}(n, mv)

julia> MultiVector{Int}(1, MVector(1, 2))
MultiVector{Int64,MArray{Tuple{2},Int64,1,2}}(0x01, [1, 2])
julia> MultiVector(n::T, mv::MV) where {T, N, MV <: MVector{N, T}} = MultiVector{T, MV}(n, mv)

julia> MultiVector{Int}(1, MVector(1, 2))
MultiVector{Int64,MArray{Tuple{2},Int64,1,2}}(0x01, [1, 2])

#9

By the way, I updated the ComputedFieldTypes repository to Julia 1.0 on my fork

Using that, this is working

julia> using ComputedFieldTypes, StaticArrays

julia> @computed mutable struct MultiVector{T,N}
           v::MVector{2^N,T}
       end
fulltype (generic function with 2 methods)

julia> MultiVector{Int,2}(MVector(1,2,3,4))
MultiVector{Int64,2,4}([1, 2, 3, 4])