如何编写类型推理友好的memoizer

Question

function memoize(f, T)
    cache = Dict{Any, T}()
    function g(args...)::T
        key = make_key(args...)
        get!(cache, key) do
            f(args...)
        end
    end
    g
end

fib = memoize(x::Int -> begin
    if x == 2
        return 2 
    end
    if x == 1
        return 1
    end
    fib(x - 1) + fib(x - 2)
end, Int)

这就是我得到的,遗憾的是,虽然我注释了它不能识别返回类型.

另外,有没有办法注释匿名函数的返回类型？

@code_warntype fib(3)

Variables:
  #self#::#g#40{##44#45,DataType,Dict{Any,Int64}}
  args::Tuple{Int64}
  key::Tuple{Int64}
  #39::##39#41{Tuple{Int64},##44#45}

Body:
  begin 
      SSAValue(0) = (Core.getfield)(#self#::#g#40{##44#45,DataType,Dict{Any,Int64}},:T)::DataType
      key::Tuple{Int64} = (Core.tuple)((Core.getfield)(args::Tuple{Int64},1)::Int64)::Tuple{Int64} # line 20:
      #39::##39#41{Tuple{Int64},##44#45} = $(Expr(:new, ##39#41{Tuple{Int64},##44#45}, :(args), :((Core.getfield)(#self#,:f)::##44#45)))
      SSAValue(1) = #39::##39#41{Tuple{Int64},##44#45}
      SSAValue(2) = (Core.getfield)(#self#::#g#40{##44#45,DataType,Dict{Any,Int64}},:cache)::Dict{Any,Int64}
      return (Core.typeassert)((Base.convert)(SSAValue(0),$(Expr(:invoke, LambdaInfo for get!(::##39#41{Tuple{Int64},##44#45}, ::Dict{Any,Int64}, ::Tuple{Int64}), :(Main.get!), SSAValue(1), SSAValue(2), :(key))))::ANY,SSAValue(0))::ANY
  end::ANY

更新

我创建了一个包,通过宏为类型推断友好的通用函数memoization提供基本支持.它还允许从函数参数自定义缓存键.

https://github.com/colinfang/Memoize.jl

Answer 1

为了让Julia专门针对特定的实现DataType,您必须使用::Type{T}参数类型:

function memoize{T}(f, ::Type{T})
    …

这个简单的改变意味着Julia将专门为每种类型的memoize遭遇提供方法,而不是仅为所有DataTypes 进行一次专门化.