# Parametric type (new struct) whose parameter is a constant of a specific type?

I wish to create an efficient type for integers modulo `m`. Yes, I do realize there are several existing ones out there, but I wish to have my own, and perhaps squeeze a bit more performance out of it.

I’ve already achieved this in this GitHub issue.
But I wish to further improve on this. Observe the code:

``````abstract type AbstractModInt <: Number end;
struct Mod8{m} <:AbstractModInt  where {m<:UInt8}  # m=modulus is a concrete value; during runtime it is not checked that m is of type UInt8
val ::UInt8
function Mod8{m}(val ::tw) where {m, tw<:UInt8}
return new{m}(mod(val,m)) end end;
``````

It allows creating `Mod8{UInt8(5)}`, but also `Mod8{Int(5)}, Mod8{Int}, ...`, which is not what I wanted. How can I have a constant `m::UInt8` as the type parameter, which is checked only at compile time, not at run time?

I’ve noticed there’s `Val{m}`, but am unsure how to use it.

Taking your question literally (how to constrain the value of a type parameter to some type?), the answer is you can’t, at least currently.

Your goal can be accomplished, though, by encoding `m` using a Zermelo ordinal-like construction (@Sukera). E.g., this is a recent piece of code of mine for representing natural numbers in the type domain, inspired by Zermelo ordinals:

``````module TypeDomainNaturalNumbers

module Internals
export Internal
struct Internal end
end

module TupleTail
export tuple_tail
function vararg_tail((@nospecialize ::Any), @nospecialize r...)
r
end
function tuple_tail(@nospecialize t::Tuple{Any,Vararg})
vararg_tail(t...)::Tuple
end
end

export NonnegativeInteger, PositiveInteger, natural_successor, natural_predecessor, natural_tuple_length

abstract type AbstractNonnegativeInteger end

"""
NonnegativeInteger

Nonnegative integers in the type domain.

The implementation is inspired by the Zermelo construction of the natural numbers.
"""
struct NonnegativeInteger{
Predecessor<:Union{Nothing,AbstractNonnegativeInteger},
} <: AbstractNonnegativeInteger
predecessor::Predecessor
function NonnegativeInteger{P}(::Internal, p::P) where {P}
new{P}(p)
end
end

"""
PositiveInteger

Positive integers in the type domain.
"""
const PositiveInteger = let t = NonnegativeInteger
t{<:t}
end::Type{<:NonnegativeInteger}

"""
natural_successor(::NonnegativeInteger)

Return the successor of a natural number.
"""
function natural_successor(o::NonnegativeInteger)
NonnegativeInteger{typeof(o)}(Internal(), o)::PositiveInteger
end

"""
natural_predecessor(::PositiveInteger)

Return the predecessor of a nonzero natural number.
"""
function natural_predecessor(o::PositiveInteger)
o.predecessor::NonnegativeInteger
end

function (::Type{NonnegativeInteger})()
NonnegativeInteger{Nothing}(Internal(), nothing)
end

function Base.zero(::Type{NonnegativeInteger})
NonnegativeInteger()
end

function to_int(@nospecialize o::NonnegativeInteger)
if o isa PositiveInteger
let p = natural_predecessor(o), t = @inline to_int(p)
t::Int + 1
end
else
0
end::Int
end

function Base.convert(::Type{Int}, o::NonnegativeInteger)
to_int(o)
end

function from_val(::Val{N}) where {N}
Vararg{Any,N}
if N === 0
NonnegativeInteger()
else
let v = Val{N - 1}(), p = @inline from_val(v)
natural_successor(p::NonnegativeInteger)
end::PositiveInteger
end::NonnegativeInteger
end

function from_int(n::Int)
Vararg{Any,n}
if n === 0
NonnegativeInteger()
else
from_val(Val{n}())
end::NonnegativeInteger
end

function Base.convert(::Type{NonnegativeInteger}, n::Int)
from_int(n)
end

"""
natural_tuple_length(::Tuple)

Return a nonnegative integer which is the length of the given tuple.
"""
function natural_tuple_length(@nospecialize t::Tuple)
if t === ()
NonnegativeInteger()
else
let a = tuple_tail(t), b = @inline natural_tuple_length(a)
natural_successor(b::NonnegativeInteger)
end::PositiveInteger
end::NonnegativeInteger
end

end
``````

Then you could do something like this for your own type:

``````struct Mod8{M<:NonnegativeInteger}
val::UInt8
end
``````

Then you can convert `M` to `Int` or `UInt8` or whatever as needed. Technically you could also constrain `M` to be less than 256 by constraining it with a big `Union` of `NonnegativeInteger` subtypes, however I guess this would make Julia’s subtyping really slow.

1 Like

Uhm, I’m a bit lost in your code, I don’t understand what all `module`s have to do with my modular integers? Isn’t `module` used to isolate namespaces and create packages, precompile them, …

Could you post a MWE on how my type could be implemented, pls? Or is all of the above code necessary?

1 Like

Your problem is the fact that in Julia it’s currently not possible to constrain non-`Type` type parameters. My proposal is to work around this by encoding the nonnegative integer value (`m`) as a type (`M`). I expect that you probably don’t want to bother with implementing this while you’re still a newbie, but perhaps you like this as food-for-thought.

1 Like

You can always do something like the following:

``````struct Mod8{m}
val::UInt8
function Mod8(m::UInt8, val::UInt8)
new{m}(val)
end
end
``````

Now you can only make a `Mod8{m}` with `m::UInt8` because this is what is returned by the inner constructor.

Then of course you can add more constructors for convenience, such as:

``````function Mod8(m::Integer, val::Integer)
Mod8(convert(UInt8, m), convert(UInt8, val))
end
``````
2 Likes