Limits of type inference

General Usage
1

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)

2

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
3

I unfortunately don’t understand what your answer wants to say.
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

4

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
5

@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.

So let me go in detail on your answer

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 :slight_smile:

6

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.

7

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!