Overloading update operators

New to Julia
1

Hi all,
I have this test code:

import Base.+


mutable struct Polynomial
    data::Dict{Int, Real}

    function Polynomial(data::Dict{Int, <:Real})
        @assert all(n->n>=0, keys(data))
        @assert all(!iszero, values(data))
        new(data)
    end
    Polynomial() = new(Dict())
end

function +(P::Polynomial, Q::Polynomial)
    """ P + Q """
    R = Polynomial()
    pds = keys(P.data)
    qds = keys(Q.data)

    for n in setdiff(pds, qds)
        R.data[n] = P.data[n]
    end

    for n in setdiff(qds, pds)
        R.data[n] = Q.data[n]
    end

    for n in pds ∩ qds
        if (c = P.data[n] + Q.data[n]) != 0
            R.data[n] = c
        end
    end
    R
end

function +=(P::Polynomial, Q::Polynomial)
    """ P += Q """
    pds = keys(P.data)
    qds = keys(Q.data)

    for n in setdiff(qds, pds)
        P.data[n] = Q.data[n]
    end

    for n in pds ∩ qds
        if (c = P.data[n] + Q.data[n]) != 0
            P.data[n] = c
        end
    end
end

I was trying to overload the += operator, but I had this error instead:

ERROR: LoadError: syntax: invalid identifier name "+="
Stacktrace:
 [1] include at .\boot.jl:317 [inlined]
 [2] include_relative(::Module, ::String) at .\loading.jl:1044
 [3] include(::Module, ::String) at .\sysimg.jl:29
 [4] exec_options(::Base.JLOptions) at .\client.jl:231
 [5] _start() at .\client.jl:425
in expression starting at C:\Users\User\Desktop\Tfach\julia_project\test.jl:36

how can I define the += operator ?

2

See this section of the manual, specifically writing x += 3 is equivalent to writing x = x + 3. In other words, you’d just overload +.

3

See also https://github.com/JuliaLang/julia/issues/3217 and https://github.com/JuliaLang/julia/issues/249 for why we opted not to allow += etcetera to be overloadable separately from +, unlike Python.

(For defining in-place operations, .+= is much more powerful because it fuses with other “dot” operations, and .+= can be customized via the broadcast machinery.)

4

I don’t think .+= is suitable because here (and eventually in many other cases) the type is not a container (although might be seen as one), the required operation is on the type itself, not its elements.
just a quick benchmark shows a speed and space gain between the two versions (Note: renamed += => iadd):

julia> using BenchmarkTools

julia> P = Polynomial(Dict(1=>2, 2=>-5))                                                                                                                                                                       
Polynomial(Dict{Int64,Real}(2=>-5,1=>2))                                                                                                                                                                       
                                                                                                                                                                                                               
julia> Q = Polynomial(Dict(0=>5, 1=>-2, 3=>5))                                                                                                                                                                 
Polynomial(Dict{Int64,Real}(0=>5,3=>5,1=>-2))

julia> @btime $P = $P + $Q                                                                                                                                                                                     
  2.941 μs (27 allocations: 2.70 KiB)                                                                                                                                                                          
Polynomial(Dict{Int64,Real}(0=>5,2=>-5,3=>5))                                                                                                                                                                  
                                                                                                                                                                                                               
julia> @btime iadd($P, $Q)                                                                                                                                                                                     
  1.829 μs (17 allocations: 1.08 KiB)
5

Incidentally, perhaps you should make it Dict{Int, T} and T a type parameter, for performance. See Performance Tips · The Julia Language

6

yes but the Polynomial takes an arbitrary Real.
changing the type to be more specific

mutable struct Polynomial{T<:Real}
    data::Dict{Int, T}

    function Polynomial(data::Dict{Int, <:Real})
        @assert all(n->n>=0, keys(data))
        @assert all(!iszero, values(data))
        new(data)
    end
    Polynomial() = new(Dict())
end

produces this error:

ERROR: LoadError: syntax: too few type parameters specified in "new{...}"
Stacktrace:
 [1] include at .\boot.jl:317 [inlined]
 [2] include_relative(::Module, ::String) at .\loading.jl:1044
 [3] include(::Module, ::String) at .\sysimg.jl:29
 [4] exec_options(::Base.JLOptions) at .\client.jl:231
 [5] _start() at .\client.jl:425
in expression starting at C:\Users\User\Desktop\Tfach\julia_project\test.jl:5

why is that ?

7

Excuse me for asking, but isn’t implementing polynomials using Dicts incredibly inefficient? It also seems to lead to very messy code. Why not use tuples or StaticArrays to hold the coefficients? Or maybe just plain vectors would be the easiest.

8

I don’t know if it’s “incredibly” inneficient, but it’s just for academic purpose, I have a python exercice to implement polynomials using dicts and i wanted to reimplement it as is in julia.

9

Because your type is parametric and new needs that information:

mutable struct Polynomial{T <: Real}
    data::Dict{Int, T}

    function Polynomial(data::Dict{Int, W}) where {W <: Real}
        @assert all(n->n>=0, keys(data))
        @assert all(!iszero, values(data))
        new{W}(data)
    end
    Polynomial{T}() where {T <: Real} = new{T}(Dict{Int, T}())
    # and for a default of `Real`
    # Polynomial() = Polynomial{Real}()
end

EDIT: Note that the type assertion T <: Real in the constructors is redundant - it’s already ensured by the type signature itself and technically doesn’t need to be checked in the constructor again.

10

OK, that’s fine. It just seems so much more obvious to use vectors (or tuples) which have integer indices by default, than to use dicts. I guess it can be useful if you have very widely separated terms, like 2x^3 + 11x^{74} or something.

Python loves dicts, but in Julia they are not necessarily the obvious goto solution.

11

Thanks, I just found out that examining the code in Polynomials.jl

12

I guess dicts do have some advantage here in making sure the uniqueness of the degrees.

13

In that case, would a SparseVector be good as well? This would need some testing, but I’m feeling lucky today in saying it would be easier to use with existing multiplication etc.

14

The indices of the vector or tuple would be equivalent to the power at that position in the example by @DNF - for example, v = [3 0 0 2 0] would uniquely describe the polynomial 3x^4 + 2x.

15

Not quite sure what you mean.

A quick and dirty test using vectors gave me a 60x speedup using vectors and 10-15th power polynomials, both for construction and addition. If you have only small polynomials, you can probably get incredible speedups with tuples/staticvectors, though at the cost of more messing about with type parameters and maybe generated functions.