How to handle unknown length returns in recursion without allocating

General Usage
1

I have a recursive function f(x, data) which can return anywhere between 1 and length(x) elements. All I want to be able to do is iterate over the return value of f so the result doesn’t need to be instantiated into a Tuple, for example, but I can’t figure out how to return an iterator over the result, or whether I even need to worry about it.

My reason for asking is that I could simply have the returns be wrapped in Tuple, but the length of a Tuple is part of its type, and so the function would not be stable. I’m looking to not allocate a vector, and not have type instability. How can I do this?

1 Like
2

Would something like

f(xs) = (x for x in xs)

@show typeof(f([1, 2, 3]))
for x in f([1, 2, 3])
    @show x
end
@show length(f([1, 2, 3]))

resulting in

typeof(f([1, 2, 3])) = Base.Generator{Vector{Int64}, typeof(identity)}
x = 1
x = 2
x = 3
length(f([1, 2, 3])) = 3

qualify? But there are caveats, for example

f(xs) = (x for x in xs if x != 1)

@show typeof(f([1, 2, 3]))
for x in f([1, 2, 3])
    @show x
end
@show length(f([1, 2, 3]))

yielding

typeof(f([1, 2, 3])) = Base.Generator{Base.Iterators.Filter{var"#7#8", Vector{Int64}}, typeof(identity)}
x = 2
x = 3
ERROR: MethodError: no method matching length(::Base.Iterators.Filter{var"#7#8", Vector{Int64}})
3

Yeah you found my problem, in a way. The iterator needs a compile-time length which I guess isn’t possible.

4

The general allocation-free way to do this is to define your own type struct FooIterator with an iterate method. For example, see the combinations function in Combinatorics.jl. This may require a bit of rethinking of how your function works, since it needs to be rearranged to compute return values one at a time as iterate is called.

Otherwise you should just return an array if you want a dynamically sized container, not a tuple. (No need to optimize allocations unless they are performance-critical, and type instability is generally worse than array allocations.)

3 Likes