Constructor with Any

[tor]

I am trying to add an 'any' constructor to my AVL tree. I now call the datatype a 'SortDict', so I want to be able to say:

Julia> sd = SortDict() # no type parameters
Julia> sd[1] = "yo"
Julia> sd['ð'] = 1//88

etc.

I don't understand how Dict() works. I have tried to copy bits and pieces from Dict.jl in various combinations, but since I don't really understand what I'm doing, it's like when cargo cults are trying to make airplanes land.


I finally managed to 'push' the avl stuff to GitHub, so you can browse it: https://github.com/torgausen/JuliaAVL/  (Yay, my first repo! :)

The exported things in "AVL.jl" might work.

[Jameson Nash]

Do you have a method definition for the empty parameter case? (I've only looked briefly, but I didn't see one)

Julia> SortDict() = SortDict( Any, Any ) #define SortDict() to return a new SortDict{Any, Any}

Julia> sd = SortDict() #call the constructor

--
 
 
 

[tor]

What I have tried is

SortDict() = SortDict(Any, Any)

Because I have defined SortDict(K, V), which works fine.

For instance, I can say sd = SortDict(Int, Char) and then sd[4] = 'a'

If I try to make a SortDict(Any, Any), it's allowed, but I can't put anything into it.

Say, if I try with ints, I get an error:

julia> sd[1] = 1
no method assign(SortDict{Any,Any},Int64,Int64)
 in method_missing at base.jl:70

I find this odd, since an 'Int' should also be an 'Any'.

[John Myles White]

Have you actually defined the method assign(SortDict, Int64, Int64)? A Constructor won't be sufficient to handle assignment operations.

 -- John

--
 
 
 

[Stefan Karpinski]

I'm not following your example 100% but parametric types are invariant in Julia, which means that SortDict{Int,Int} is not a subtype of SortDict{Any,Any}, for example. In general, Foo{A} and Foo{B} are only disjoint unless A and B are the same.

--
 
 
 

[tor]

Yes, as mentioned above, and it works when I use specific types such as Ints or Chars. It does not work with abstract types though.

[Stefan Karpinski]

On Sun, Aug 5, 2012 at 3:30 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

I'm not following your example 100% but parametric types are invariant in Julia, which means that SortDict{Int,Int} is not a subtype of SortDict{Any,Any}, for example. In general, Foo{A} and Foo{B} are only disjoint unless A and B are the same.

Delete the word "only" from that last sentence. 

[tor]

But Dict() does it! You can make a Dict(Any, Any) and put all sorts of stuff in it! :)

[tor]

Sorry, that should be a Dict(), not Dict(Any, Any).

[Stefan Karpinski]

That's true: a Dict{Any,Any} can have any kind of value for its keys and values. However, a Dict{Int,Int} is not an instance of Dict{Any,Any} even though all its keys and values could be keys and values for a Dict{Any,Any}. I'm not sure if that's your problem, but it sounds suspiciously like something of that kind might be going on.

--
 
 
 

[tor]

julia> d = Dict()
Dict()

julia> d["foo"] = 1/3
0.3333333333333333 # GOOD!

julia> sd = SortDict()
SortDict(Nil(),isless)

julia> sd["foo"] = 1/3
no method assign(SortDict{Any,Any},Float64,ASCIIString)  # BAD!

[Patrick O'Leary]

On Sunday, August 5, 2012 2:43:45 PM UTC-5, tor wrote:

julia> sd = SortDict()
SortDict(Nil(),isless)

julia> sd["foo"] = 1/3
no method assign(SortDict{Any,Any},Float64,ASCIIString)  # BAD!
 in method_missing at base.jl:70

Your assign() is too restrictive.  You need to allow the key and value to be subtypes of the dict's key and value. This should work:

function assign{K, V, K1<:K, V1<:V}(sd :: SortDict{K, V}, value :: V1, key :: K1) 
	h, c, sd.tree = assign(sd.tree, key, value, sd.cf)
end

 

[Stefan Karpinski]

Dispatch like that doesn't work:

julia> foo(x,y) = false

julia> foo{S,T<:S}(x::S,y::T) = true

S not defined

The RHS of a type bound on a type parameter for a method can't itself be a parameter. That would allow stronger dispatch than just diagonal dispatch.

--
 
 
 

[tor]

I tried that in the REPL, but it says K not defined.

[Keno Fischer]

Shouldn't it be just

function assign{K, V}(sd :: SortDict{K, V}, value :: V, key :: K) 

	h, c, sd.tree = assign(sd.tree, key, value, sd.cf)
end

--
 
 
 

[tor]

Right, here's what Dict() looks like:

type Dict{K,V} <: Associative{K,V}
<snip>

    Dict() = Dict{K,V}(0)
    function Dict(n::Integer)
<snip>
    end
    function Dict(ks::Tuple, vs::Tuple)
  <snip>
  end
  <snip>
end
Dict() = Dict(0)
Dict(n::Integer) = Dict{Any,Any}(n)


I tried to copy this in several ways, but couldn't replicate the behaviour of the Dict() constructor.

[Stefan Karpinski]

Just leaving the key and value parameters unrestricted is fine. This is what Dict itself does:

function assign{K,V}(h::Dict{K,V}, v, key)

There's a bit of a subtlety here: the values stored in Dict-like structures are of types K and V, but that doesn't mean that key and v need to be of types K and V — they can be values that can be converted to that type — and the way to check for that is just to do the conversion and see if it works. As an example, you can do this:

julia> d = Dict{Int,Int}()

Dict()

julia> d[1.0] = 2.0

2.0

julia> d

{1=>2}

Note that assignment is rigged so that it always evaluates to its RHS, regardless of what the assignment may convert the value to. This is so that chained assignments can't be made to do surprising things based on the implementation of assign. If you try to use a non-integral floating point value for either a key or a value, you'll get an InexactError:

julia> d[1.5] = 2

InexactError()

 in assign at dict.jl:304

julia> d[1.0] = 2.5

InexactError()

 in assign at dict.jl:304

--
 
 
 

[tor]

Thanks, I think that is the solution :)

[Patrick O'Leary]

On Sunday, August 5, 2012 2:55:27 PM UTC-5, Stefan Karpinski wrote:

Dispatch like that doesn't work:

julia> foo(x,y) = false

julia> foo{S,T<:S}(x::S,y::T) = true

S not defined

The RHS of a type bound on a type parameter for a method can't itself be a parameter. That would allow stronger dispatch than just diagonal dispatch.

I thought Julia's dispatch mechanism was made of magic and rainbows! (I think I've actually tried this before in the LRU code while trying to fix that one bug and saw that it didn't work, and realized I could just unrestrict those type parameters, exactly as you suggest. And I now realize I may still be off by some convert() calls in the LRU code. Dangit.)

And to Keno, that's the original code from Tor's repository. The restrictions on the value and key parameters prevent Julia from dispatching if sd::SortDict{Any, Any}, unless value and key have exactly the type Any, which is unlikely.

Moral of the story: you can't use convert() like Scala's implicits, expecting them to be attempted in order to create a match in the dispatch table. They're instead "explicits."