module TupleTail
export tuple_tail
function vararg_tail((@nospecialize unused), r...)
r
end
# More or less equivalent to `Base.tail`
function tuple_tail(@nospecialize t::Tuple{Any,Vararg})
r = vararg_tail(t...)::Tuple
if t isa NTuple
r = r::NTuple
end
r
end
end
# Taken from my in-development package HeterogeneousLists.jl
#
# Not all of the code in the module is necessary here.
module TypeDomainNaturalNumbers
export NonnegativeInteger, PositiveInteger, natural_successor, natural_predecessor
using ..TupleTail
abstract type AbstractNonnegativeInteger end
"""
NonnegativeInteger
Nonnegative integers in the type domain.
The implementation is inspired by the Zermelo construction of the natural numbers.
"""
struct NonnegativeIntegerImpl{
Predecessor<:Union{Nothing,AbstractNonnegativeInteger},
} <: AbstractNonnegativeInteger
predecessor::Predecessor
global const NonnegativeInteger = NonnegativeIntegerImpl{P} where {
P<:Union{Nothing,NonnegativeIntegerImpl},
}
global function new_nonnegative_integer(p::P) where {P<:Union{Nothing,NonnegativeInteger}}
t_p = P::DataType
r = new{t_p}(p)
r::NonnegativeInteger
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)
new_nonnegative_integer(o)::PositiveInteger
end
"""
natural_predecessor(::PositiveInteger)
Return the predecessor of a nonzero natural number.
"""
function natural_predecessor(o::PositiveInteger)
o.predecessor::NonnegativeInteger
end
function Base.zero(::Type{NonnegativeInteger})
new_nonnegative_integer(nothing)
end
Base.@assume_effects :foldable 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
const negative_error = ArgumentError("can't convert negative to natural")
Base.@assume_effects :foldable function from_val(::Val{N}) where {N}
n = N::Int
if n < 0
throw(negative_error)
end
if n === 0
zero(NonnegativeInteger)
else
let v = Val{n - 1}(), p = @inline from_val(v)
natural_successor(p::NonnegativeInteger)
end
end::NonnegativeInteger
end
function from_int(n::Int)
if n < 0
throw(negative_error)
end
if n === 0
zero(NonnegativeInteger)
else
from_val(Val{n}())
end::NonnegativeInteger
end
function Base.convert(::Type{NonnegativeInteger}, n::Int)
from_int(n)
end
Base.@assume_effects :foldable function subtracted((@nospecialize l::NonnegativeInteger), @nospecialize r::NonnegativeInteger)
if r isa PositiveInteger
let a = natural_predecessor(l), b = natural_predecessor(r)
@inline subtracted(a, b)
end
else
l
end::NonnegativeInteger
end
Base.@assume_effects :foldable function added((@nospecialize l::NonnegativeInteger), @nospecialize r::NonnegativeInteger)
if r isa PositiveInteger
let a = natural_successor(l), b = natural_predecessor(r)
@inline added(a, b)
end
else
l
end::NonnegativeInteger
end
function Base.:(-)((@nospecialize l::NonnegativeInteger), @nospecialize r::NonnegativeInteger)
subtracted(l, r)
end
function Base.:(+)((@nospecialize l::NonnegativeInteger), @nospecialize r::NonnegativeInteger)
added(l, r)
end
end
module TupleUtils
using ..TypeDomainNaturalNumbers
export natural_tuple_length, tuple_element_at_index
"""
natural_tuple_length(::Tuple)
Return a nonnegative integer which is the length of the given tuple.
"""
Base.@assume_effects :foldable function natural_tuple_length(@nospecialize t::Tuple)
if t === ()
zero(NonnegativeInteger)
else
let a = tuple_tail(t), b = @inline natural_tuple_length(a)
natural_successor(b::NonnegativeInteger)
end
end::NonnegativeInteger
end
function tuple_element_at_index(t::Tuple{Any,Vararg}, @nospecialize n::NonnegativeInteger)
p = natural_successor(n)
i = convert(Int, p)
t[i]
end
end
module WeightedRandPickFromHeterogeneous
using ..TypeDomainNaturalNumbers, ..TupleUtils
export weighted_rand_pick_from_heterogeneous
function weighted_rand_pick_from_heterogeneous_recursive(
rand::R,
f::F,
heterogeneous::Tuple{Any,Vararg},
weights::Tuple,
len::NonnegativeInteger,
(@nospecialize n::NonnegativeInteger),
)
i = len - n
a = tuple_element_at_index(heterogeneous, i)
if n isa PositiveInteger
let heterogeneous = heterogeneous::Tuple{Any,Any,Vararg},
weights = weights::Tuple{Any,Vararg},
j = natural_predecessor(i),
w = tuple_element_at_index(weights. j),
x = rand()
if x < w
f(a)
else
let nm1 = natural_predecessor(n)
@inline weighted_rand_pick_from_heterogeneous_recursive(
rand, f, heterogeneous, weights, len, nm1,
)
end::Nothing
end
end
else
f(a)
end
nothing
end
function weighted_rand_pick_from_heterogeneous(
r::R, f::F, h::Tuple{Any,Vararg}, w::Tuple
) where {R,F}
len = natural_tuple_length(w)
weighted_rand_pick_from_heterogeneous_recursive(r, f, h, w, len)
end
end
function usefunc end
function pickfunc(data, funcs::Tuple{Any,Vararg}, cumweights::Tuple)
f = let data = data, closure
function closure(g::G) where {G}
usefunc(data, g)
end
end
weighted_rand_pick_from_heterogeneous(rand, f, funcs, cumweights)
end
