`maximum`/`minimum` breaks inference in recursive definitions where `mapreduce` works

[danielwe]

When defining f(x) = maximum(f, x) plus an appropriate base case, julia fails to infer the return type of f. The equivalent definition f(x) = mapreduce(f, max, x) does not have this problem. minimum is the same.

julia> x = [[1, 2], [3, 4]];

julia> f(x) = maximum(f, x); f(x::Number) = x;

julia> @code_warntype f(x)
MethodInstance for f(::Vector{Vector{Int64}})
  from f(x) in Main at REPL[19]:1
Arguments
  #self#::Core.Const(f)
  x::Vector{Vector{Int64}}
Body::Any
1 ─ %1 = Main.maximum(Main.f, x)::Any
└──      return %1


julia> g(x) = mapreduce(g, max, x); g(x::Number) = x;

julia> @code_warntype g(x)
MethodInstance for g(::Vector{Vector{Int64}})
  from g(x) in Main at REPL[21]:1
Arguments
  #self#::Core.Const(g)
  x::Vector{Vector{Int64}}
Body::Int64
1 ─ %1 = Main.mapreduce(Main.g, Main.max, x)::Int64
└──      return %1

Stumbled upon this in #44893. Perhaps related to #43461, but not the same as this is still a problem after #43467, and maximum(f, x[1]) infers.

I'm using version 1.7.2. @MasonProtter confirmed this is still an issue on master.

julia> versioninfo()
Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)

[N5N3]

If you call

maximum(f, x[1])
maximum(f, x)
f(x)

in order with a fresh REPL, then the inference will success.
Thus this looks more like a internal limitation on self-recursion.

[danielwe]

Thanks, I did notice the inference go through after cycling through various calls but wasn't able to nail down the required sequence. Still, it's always able to infer if you use mapreduce, so this is still a mystery to me. The recursion is the same, no?

[mbauman]

I'm not able to reproduce this on v1.11-rc1 or the nightly. I do see it in v1.10.

  | | |_| | | | (_| |  |  Version 1.11.0-rc1 (2024-06-25)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> x = [[1, 2], [3, 4]];

julia> f(x) = maximum(f, x); f(x::Number) = x;

julia> @code_warntype f(x)
MethodInstance for f(::Vector{Vector{Int64}})
  from f(x) @ Main REPL[2]:1
Arguments
  #self#::Core.Const(f)
  x::Vector{Vector{Int64}}
Body::Int64
1 ─ %1 = Main.maximum::Core.Const(maximum)
│   %2 = Main.f::Core.Const(f)
│   %3 = (%1)(%2, x)::Int64
└──      return %3


julia> g(x) = mapreduce(g, max, x); g(x::Number) = x;

julia> @code_warntype g(x)
MethodInstance for g(::Vector{Vector{Int64}})
  from g(x) @ Main REPL[4]:1
Arguments
  #self#::Core.Const(g)
  x::Vector{Vector{Int64}}
Body::Int64
1 ─ %1 = Main.mapreduce::Core.Const(mapreduce)
│   %2 = Main.g::Core.Const(g)
│   %3 = Main.max::Core.Const(max)
│   %4 = (%1)(%2, %3, x)::Int64
└──      return %4

Looks fixed?