# Limits of type inference

Hi julia developers,

just stumbled upon a limitation in typeinference and minified it to the following example.
The example is actually quite similar to my real usecase, where I like to define a generic `map` for multiple Types, supporting extra type-inference.

As you can see, typeinference breaks as soon as the `fmap` has multiple overloadings.

``````struct Iterable{T}
iterable::T
end

a = Iterable(i for i ∈ [1,2,3])
b = Iterable(i for i ∈ [4,5,6])

function fmap end
fmap(f, it::Iterable) = Iterable(f(x) for x in it.iterable)

function nested_eltype()
h = fmap(a) do x
fmap(b) do y
x + y
end
end
# infering eltype of newly created Base.Generator
Core.Compiler.return_type(h.iterable.f, Tuple{eltype(h.iterable.iter)})
end
nested_eltype()  # Iterable

function fmap(func, d::Dict)
Dict(k => func(v) for (k, v) in d)
end
nested_eltype()  # returns Union{Dict, Iterable}, however should be Iterable

fmap(f, v::Vector) = map(f, v)
nested_eltype()  # returns Any, however should be Iterable
``````

EDIT: the expected return type of `nested_eltype()` is always `Iterable` or something even more concrete

Anyone who knows how to workaround this?
Anyone any idea whether this is improvable in julia?
(Would be awesome if a soon julia version can typeinfer these expressions in detail)

Julia does not know what type of `Vector` your map will return.
Assuming your vector `map` returns a `Vector` of the same type:

``````julia> struct Iterable{T}
iterable::T
end

julia> a = Iterable(i for i ∈ [1,2,3])

julia> b = Iterable(i for i ∈ [4,5,6])

julia> function fmap end

julia> fmap(f, it::Iterable) = Iterable(f(x) for x in it.iterable)
fmap (generic function with 1 method)

julia> function nested_eltype()
h = fmap(a) do x
fmap(b) do y
x + y
end
end
# infering eltype of newly created Base.Generator
Core.Compiler.return_type(h.iterable.f, Tuple{eltype(h.iterable.iter)})
end

julia> nested_eltype()  # Iterable
Iterable{_A} where _A

julia> function fmap(func, d::Dict)
Dict(k => func(v) for (k, v) in d)
end
fmap (generic function with 2 methods)

julia> nested_eltype()  # Union{Dict, Iterable}
Union{Dict{_A,_B} where _B where _A, Iterable{_A} where _A}

julia> (fmap(f, v::Vector{T})::Vector{T}) where {T} = map(f, v)
fmap (generic function with 3 methods)

julia> nested_eltype()  # not Any
Union{Dict{_A,_B} where _B where _A, Array{_A,1} where _A, Iterable{_A} where _A}
``````
1 Like

I edited my Question to clarify that the thing which does not work here is that `nested_eltype()` should always return `Iterable` (or something more concrete) but it doesn’t

Let’s try this again, using your revised example.

``````struct Iterable{T}
iterable::T
end

a = Iterable(i for i ∈ [1,2,3])
b = Iterable(i for i ∈ [4,5,6])

function fmap end
fmap(f, it::Iterable) = Iterable(f(x) for x in it.iterable)

function nested_eltype()
h = fmap(a) do x
fmap(b) do y
x + y
end
end
# infering eltype of newly created Base.Generator
Core.Compiler.return_type(h.iterable.f, Tuple{eltype(h.iterable.iter)})
end
nested_eltype()  # Iterable

function fmap(func, d::Dict)
Dict(k => func(v) for (k, v) in d)
end
nested_eltype()  # returns Union{Dict, Iterable}, however should be Iterable
``````

up to there everything is as you wrote it

I am going to change the next line You had

``````fmap(f, v::Vector)  = map(f, v)
``````

Because there is no way for Julia to ascertain what happens when this `f` is mapped over that `v` (is the result a vector of the same eltype as v [f = x -> x+x]? is the result a vector of some other eltype [f = x -> Float32(x)]? is the result … [f = x -> typeof(x)]?)
Julia must work with the return type `Any`.

Now, I will presuppose that your function `f` maintains the type of the values within the vector. With that presupposition, we can remove the ambiguity I highlighted above.

``````(fmap(f, v::Vector{T})::Vector{T}) where {T} = map(f, v)
``````

That says “fmap returns a vector with the same type of elements as it is given”.
It does not restrict the vector to any specific element type.
Now.

``````julia> nested_eltype()
Union{Dict{_1,_2} where _2 where _1, Array{_1,1} where _1, Iterable{_1} where _1}
``````

Hope that clarifies this part of it for you.

You cannot expect to get iterables where you are getting `Any`.

Someone else may better know how to guide you from here.

1 Like

@JeffreySarnoff

thank you very much for your intense help,
unfortunately it seems to me that you misunderstood my question.

by now this thread is so large already that I am going to reopening my original intent in another topic. Hence lets focus now on your understanding, because I still find it interesting.

I disagree here. To the best of my understanding julia’s type inference takes into account the concrete input values, i.e. also the concrete input types. If I define a function as general like `fmap(f, v::Vector) = map(f, v)` it does not mean that the type inference only knows `f isa Any` and `v isa Vector`. It will get the concrete types to reason with.
For example when calling `fmap(x->x, [1,2,3])` we expect the correct type output, which indeed also works. (finally this is just forwarding to `map`). Julia’s typeinference is awesome in this regard - I really like it.

The problem arises only in the nested setting as I setup here in my minimal working example. Out of a sudden the type-inference machine cannot propagate the concrete types to the nested functions. To me it clearly seems like the type information is there and could be propagated correctly, it is just not done yet.

I just now realize that this last explanation should become part of my question in the first place to better explain my need

Please don’t do that — you lose all context, and waste the effort of those engaged in helping you.

I don’t get the purpose of the original exercise, but note that `nested_eltype` — as you wrote it originall — uses two globals, which could change at any time, so all bets are off when it comes to type inference. It just returns whatever `fmap` can return, so it indeed depends on what methods you have defined for the latter.

If you want type inference to work, don’t use globals.

That said, what you are actually trying to do is still unclear to me.

Thanks a lot for your help. I am sorry for having difficulties phrasing my question, but your remark with the globals is awesome. I already did this mistake once, that my typeinference didn’t work as expected because I forgot to use a `const` in my tests…

Unfortunately this makes only this minimal working example running, while my original failing case still fails and does not use any apparent globals…
I have to investigate further and hope to find what else could it be which does not work in my complex scenario.

Thanks @Tamas_Papp thanks @JeffreySarnoff for your help!