Re: [julia-users] The unique function and iterables of custom composite types

[Stefan Karpinski]

I just tried it on that exact version and do not see that behavior:

julia> versioninfo()
Julia Version 0.4.0-dev+5587
Commit 78760e2 (2015-06-25 14:27 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin14.3.0)
  CPU: Intel(R) Core(TM) M-5Y71 CPU @ 1.20GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Prescott)
  LAPACK: libopenblas
  LIBM: libopenlibm
  LLVM: libLLVM-3.3

julia> type Foo
           x::Int
       end

julia> ==(f1::Foo, f2::Foo) = f1.x == f2.x
== (generic function with 108 methods)

julia> foos = [Foo(4), Foo(4)]
2-element Array{Foo,1}:
 Foo(4)
 Foo(4)

julia> unique(foos)
2-element Array{Foo,1}:
 Foo(4)
 Foo(4)


If you look at the definition of unique, it doesn't see like it could
possibly do that without defining a hash method for Foo:

function unique(C)
    out = Array(eltype(C),0)
    seen = Set{eltype(C)}()
    for x in C
        if !in(x, seen)
            push!(seen, x)
            push!(out, x)
        end
    end
    out
end


The only way I can think of that this might occur is if you happen to get a
hash collision with the default hashing function – which actually has about
a 1/16 chance of happening. Makes me wonder if we shouldn't check both hash
values and equality in our Dict implementation. Saving hash values is
actually fairly common in hash table implementations since it allows
rehashing the table without actually recomputing the hash of every key.

On Thu, Jul 16, 2015 at 11:02 AM, Seth <catch...@bromberger.com> wrote:

> I can confirm this works as described by milktrader on 0.4.0-dev+5860
> (2015-07-08 20:57 UTC) Commit 7fa43ed (7 days old master).
>
> julia> unique(foos)
> 1-element Array{Foo,1}:
>  Foo(4)
>
>
> On Thursday, July 16, 2015 at 7:52:03 AM UTC-7, Stefan Karpinski wrote:
>>
>> I don't see that on 0.4-dev – it also doesn't seem possible without
>> having defined a hash method since unique is implemented with a dict.
>>
>> On Thu, Jul 16, 2015 at 10:29 AM, milktrader <milkt...@gmail.com> wrote:
>>
>>> Julia 0.4- has different behavior ...
>>>
>>> First, with 0.3.9
>>>
>>> julia> versioninfo()
>>> Julia Version 0.3.9
>>> Commit 31efe69 (2015-05-30 11:24 UTC)
>>> Platform Info:
>>>   System: Darwin (x86_64-apple-darwin13.4.0)
>>>   CPU: Intel(R) Core(TM)2 Duo CPU     P7350  @ 2.00GHz
>>>   WORD_SIZE: 64
>>>   BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Penryn)
>>>   LAPACK: libopenblas
>>>   LIBM: libopenlibm
>>>   LLVM: libLLVM-3.3
>>>
>>> julia> type Foo
>>>             x::Int
>>>             end
>>>
>>> julia> import Base: ==
>>>
>>> julia> ==(f1::Foo, f2::Foo) = f1.x == f2.x
>>> == (generic function with 80 methods)
>>>
>>> julia> foos = [Foo(4), Foo(4)]
>>> 2-element Array{Foo,1}:
>>>  Foo(4)
>>>  Foo(4)
>>>
>>> julia> unique(foos)
>>> 2-element Array{Foo,1}:
>>>  Foo(4)
>>>  Foo(4)
>>>
>>> julia> unique(foos)[1] == unique(foos)[2]
>>> true
>>>
>>> And now 0.4-dev
>>>
>>> julia> versioninfo()
>>> Julia Version 0.4.0-dev+5587
>>> Commit 78760e2 (2015-06-25 14:27 UTC)
>>> Platform Info:
>>>   System: Darwin (x86_64-apple-darwin13.4.0)
>>>   CPU: Intel(R) Core(TM)2 Duo CPU     P7350  @ 2.00GHz
>>>   WORD_SIZE: 64
>>>   BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Penryn)
>>>   LAPACK: libopenblas
>>>   LIBM: libopenlibm
>>>   LLVM: libLLVM-3.3
>>>
>>> julia> type Foo
>>>             x::Int
>>>             end
>>>
>>> julia> import Base: ==
>>>
>>> julia> ==(f1::Foo, f2::Foo) = f1.x == f2.x
>>> == (generic function with 108 methods)
>>>
>>> julia> foos = [Foo(4), Foo(4)]
>>> 2-element Array{Foo,1}:
>>>  Foo(4)
>>>  Foo(4)
>>>
>>> julia> unique(foos)
>>> 1-element Array{Foo,1}:
>>>  Foo(4)
>>>
>>> julia> unique(foos)[1] == unique(foos)[2]
>>> ERROR: BoundsError: attempt to access 1-element Array{Foo,1}:
>>>  Foo(4)
>>>   at index [2]
>>>  in getindex at array.jl:292
>>>
>>>
>>>
>>> On Thursday, July 16, 2015 at 9:36:21 AM UTC-4, Stefan Karpinski wrote:
>>>>
>>>> You need to also define a hash method for this type.
>>>>
>>>>
>>>> On Jul 16, 2015, at 9:16 AM, Marc Gallant <marc.j....@gmail.com> wrote:
>>>>
>>>> The unique function doesn't appear to work using iterables of custom
>>>> composite types, e.g.,
>>>>
>>>> julia> type Foo
>>>>        x::Int
>>>>        end
>>>>
>>>> julia> import Base: ==
>>>>
>>>> julia> ==(f1::Foo, f2::Foo) = f1.x == f2.x
>>>> == (generic function with 85 methods)
>>>>
>>>> julia> unique(foos)
>>>> 2-element Array{Foo,1}:
>>>>  Foo(4)
>>>>  Foo(4)
>>>>
>>>> julia> unique(foos)[1] == unique(foos)[2]
>>>> true
>>>>
>>>>
>>>> Is this the intended behaviour?
>>>>
>>>>
>>