如何让Julia中product迭代器相关代码的变量A实现类型稳定？

我正尝试让以下代码中的变量A实现类型稳定：

using Primes: factor

function f(n::T, p::T, k::T) where {T<:Integer}
    return rand(T, n * p^k)
end

function g(m::T, n::T) where {T<:Integer}
    
    i = 0
    for A in Iterators.product((f(n, p, T(k)) for (p, k) in factor(m))...)
        i = sum(A)
    end
    return i

end

注意，函数f是类型稳定的。变量A之所以类型不稳定，是因为Iterators.product会根据n和m的值返回不同尺寸的元组。如果存在一个返回Vector而非Tuple的类似product迭代器，我认为类型不稳定问题就能解决。

补充说明：f返回的是类型为T的可变长度Vector。

我已找到一种解决类型稳定性问题的方法，但会带来大量内存开销：

function g(m::T, n::T) where {T<:Integer}
    B = Vector{T}[T[]]
    for (p, k) in factor(m)
        C = Vector{T}[]
        for (b, r) in Iterators.product(B, f(n, p, T(k)))
            c = copy(b)
            push!(c, r)
            push!(C, c)
        end
        B = C
    end

    for A in B
        i = sum(A)
    end

    return i
end

这种方法下变量A已经实现了类型稳定，但内存开销太大，想知道有没有更优的实现方式。

更优的实现方案 #

核心思路：避免预存所有组合，按需计算 #

既然核心操作是对每个组合求和，完全不需要把所有组合都存储在内存中。可以通过递归或迭代的方式逐个遍历组合元素，实时计算总和，既保证类型稳定，又把内存开销降到最低。

方案1：递归遍历实现

using Primes: factor

function f(n::T, p::T, k::T) where {T<:Integer}
    return rand(T, n * p^k)
end

function g(m::T, n::T) where {T<:Integer}
    factors = collect(factor(m))  # 获取(m的质因数, 指数)对列表
    sequences = [f(n, p, T(k)) for (p, k) in factors]
    total = zero(T)

    # 递归遍历所有组合并累加总和
    function traverse(idx::Int, current_sum::T)
        if idx > length(sequences)
            total += current_sum
            return
        end
        for val in sequences[idx]
            traverse(idx + 1, current_sum + val)
        end
    end

    traverse(1, zero(T))
    return total
end

方案2：迭代式（栈模拟）实现

如果担心递归深度问题（比如m的质因数数量过多），可以用栈模拟递归逻辑：

using Primes: factor

function f(n::T, p::T, k::T) where {T<:Integer}
    return rand(T, n * p^k)
end

function g(m::T, n::T) where {T<:Integer}
    factors = collect(factor(m))
    sequences = [f(n, p, T(k)) for (p, k) in factors]
    isempty(sequences) && return zero(T)
    
    total = zero(T)
    # 栈元素存储：(当前遍历的序列索引, 当前累加和)
    stack = [(1, zero(T))]
    
    while !isempty(stack)
        idx, current_sum = pop!(stack)
        if idx > length(sequences)
            total += current_sum
            continue
        end
        # 反向入栈保证遍历顺序和递归一致（不关心顺序可省略reverse）
        for val in reverse(sequences[idx])
            push!(stack, (idx + 1, current_sum + val))
        end
    end
    return total
end

方案优势 #

• 类型稳定：所有变量的类型在编译期即可确定，完全符合类型稳定要求；
• 内存高效：仅存储f返回的原始序列，不会生成和存储任何组合向量，内存开销远低于原方案；
• 逻辑简洁：直接聚焦于求和目标，避免不必要的中间存储操作。

内容的提问来源于stack exchange，提问作者user19565054