Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Method will not match with nested type restrictions

Tags:

dispatch

julia

I have this simple method which calculates the weighted average of a collection of vectors

function meanw{T <: Number}(x::AbstractArray{AbstractVector{T}, 1}, w::AbstractVector{T})
  x̄ = sum(x .* w)
  x̃ = map(z -> z - x̄, x)
  x̄, x̃
end

but the dispatch cannot match my method when I try to use it.

ERROR: `meanw` has no method matching meanw(::Array{Array{Float64,1},1}, ::Array{Float64,1})

I suspect that I have misunderstood how to use type restrictions when there is nesting involved. How should I rewrite this function to match my collections?

P.S.

I know vectors and arrays are the same thing but the differentiation makes it clearer how the function is used.

like image 250
Godisemo Avatar asked Aug 25 '14 16:08

Godisemo


1 Answers

So if you rewrite your code to use the concrete Types it works

function meanw{T <: Number}(x::Array{Vector{T}, 1}, w::Vector{T})
  x̄ = sum(x .* w)
  x̃ = map(z -> z - x̄, x)
  x̄, x̃
end

this also works

function meanw{T <: Number}(x::Array{Vector{T}, 1}, w::AbstractVector{T})
  x̄ = sum(x .* w)
  x̃ = map(z -> z - x̄, x)
  x̄, x̃
end

this doesn't work

function meanw{T <: Number}(x::Array{AbstractVector{T}, 1}, w::AbstractVector{T})
  x̄ = sum(x .* w)
  x̃ = map(z -> z - x̄, x)
  x̄, x̃
end

and this does work again

function meanw{T <: Number}(x::AbstractArray{Vector{T}, 1}, w::AbstractVector{T})
  x̄ = sum(x .* w)
  x̃ = map(z -> z - x̄, x)
  x̄, x̃
end

the problem we have here is described in the Julia manual under parametric types

This last point is very important:

Even though Float64 <: Real we DO NOT have Point{Float64} <: Point{Real}.

In other words, in the parlance of type theory, Julia’s type parameters are invariant, rather than being covariant (or even contravariant). This is for practical reasons: while any instance of Point{Float64} may conceptually be like an instance of Point{Real} as well, the two types have different representations in memory:

What actually does work is this

function meanw{T <: Number, V <: AbstractVector}(x::AbstractArray{V, 1}, w::AbstractVector{T})
  x̄ = sum(x .* w)
  x̃ = map(z -> z - x̄, x)
  x̄, x̃
end

but the real question is why do you want to do this? The Julia Compiler is clever enough even without type annotations to produce efficient code as long as the inputs are well-typed and the function itself is type-stable. Type annotations are only really needed for multiple-dispatch and as contract to specify what the function can actually handle, but this is notoriously difficult in Julia due to the extensive type system.

like image 69
vchuravy Avatar answered Nov 22 '22 16:11

vchuravy