# Unique doesn't seem to obey == definitions

**URL:** <https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455>\
**Category:** General Usage\
**Created:** [September 29, 2020, 1:39am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455 "2020-09-29T01:39:03Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![pengwyn](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pengwyn/32/6961_2.png) [@pengwyn](https://discourse.julialang.org/u/pengwyn)\
**Post date:** [September 29, 2020, 1:39am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/1 "2020-09-29T01:39:03Z")

</div>

The behaviour for `unique(itr)` doesn’t seem to follow the documentation which specifies items are compared using an `isequal` check.

This got me when I have a custom struct, e.g.

```julia
mutable struct A
x
end
Base.var"=="(one::A, two::A) = (one.x == two.x)

```

and then wanted to do something like:

```julia
temp = [A(1), A(2), A(1)]
temp[1] == temp[3] # returns true
unique(temp) # returns three elements not [A(1), A(2)] as expected

```

Is there something trivial I am forgetting here?

Digging deeper into this, it seems that all variants of `unique` eventually call `hash` to figure out whether two objects are the same. In the case of a generic iterate, this happens in the check `!in(x, seen)` where `seen` is a `Set` which uses hashes. In the case of an `AbstractArray` hashes are used directly.

So I presume this means I am required to implement `hash` as well as `==` to use `unique`? Should the documentation be updated to reflect this?

I should add, that in my current case implementing a `hash` is difficult whereas `==` is trivial, because I am using CxxWrap.jl objects.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [September 29, 2020, 1:49am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/2 "2020-09-29T01:49:13Z")

</div>

> [This typically means that types for which a custom `==` or `isequal` method exists must implement a corresponding `hash` method (and vice versa). Collections typically implement `isequal` by calling `isequal` recursively on all contents.](https://docs.julialang.org/en/v1/base/base/#Base.isequal)

There is already a cross reference though adding emphasis might be OK.

---

<div class="post-metadata">

**Author:** ![pengwyn](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pengwyn/32/6961_2.png) [@pengwyn](https://discourse.julialang.org/u/pengwyn)\
**Post date:** [September 29, 2020, 1:55am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/3 "2020-09-29T01:55:45Z")

</div>

Oh I see - I didn’t dig down into the `isequal` documentation once I had read that `unique` uses `isequal` and verified that `isequal` was behaving correctly at the REPL.

That makes sense now. However, I think the documentation of `unique` is then just plain wrong. The implementation of `unique` never calls `isequal`, it only uses `hash`. Maybe the [`unique` documentation](https://docs.julialang.org/en/v1/base/collections/#Base.unique) could be changed to read:

> Return an array containing only the unique elements of collection itr, as determined by **hash** , in the order that …

Does that sound right?

Edit: I realise I forgot to ask, should I submit a PR for this?

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [October 10, 2020, 12:15am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/4 "2020-10-10T00:15:52Z")

</div>

> [@pengwyn](#):
>
> However, I think the documentation of `unique` is then just plain wrong

No the document is not wrong and `unique` does call `isequal`.

---

<div class="post-metadata">

**Author:** ![pengwyn](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pengwyn/32/6961_2.png) [@pengwyn](https://discourse.julialang.org/u/pengwyn)\
**Post date:** [October 10, 2020, 12:28am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/5 "2020-10-10T00:28:02Z")

</div>

In the implementation in [https://github.com/JuliaLang/julia/blob/7f7ab69fd30e7ea57ffc1c6a8c803826bf02f838/base/set.jl#L122](https://github.com/JuliaLang/julia/blob/7f7ab69fd30e7ea57ffc1c6a8c803826bf02f838/base/set.jl#L122) which is for the generic iterator, `unique` does **not** call `isequal`. It instead constructs a `Set` which uses `hash`.

The only call to `isequal` that I can see relevant to isunique is in `_groupedunique!` which is only called from the `unique!` entrypoint and only if the first argument is a Vector of reals and is already sorted.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [October 10, 2020, 12:49am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/6 "2020-10-10T00:49:16Z")

</div>

> [@pengwyn](#):
>
> It instead constructs a `Set` which uses `hash` .

The `hash` function [is required](https://docs.julialang.org/en/v1/base/base/#Base.hash) to produce equal hashes for `isequal` values. Moreover `Set` (which is [implemented using `Dict`](https://github.com/JuliaLang/julia/blob/7f7ab69fd30e7ea57ffc1c6a8c803826bf02f838/base/set.jl#L4)) _may_ [check `isequal`](https://github.com/JuliaLang/julia/blob/7f7ab69fd30e7ea57ffc1c6a8c803826bf02f838/base/dict.jl#L291) (since explicit equality checks are ultimately necessary for [hash collision resolution](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution)).

---

<div class="post-metadata">

**Author:** ![pengwyn](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pengwyn/32/6961_2.png) [@pengwyn](https://discourse.julialang.org/u/pengwyn)\
**Post date:** [October 10, 2020, 1:19am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/7 "2020-10-10T01:19:05Z")

</div>

Oh I think I see the issue now. Thinking from the point of view of `unique` and pretending I don’t know it uses a `Set/Dict` internally, I can think of it as:

1. Check if hashes differ - if so then items are different.
2. Otherwise, check `isequal` between the items.

So `hash` acts as a shortcircuit.

Thanks @yuyichao and @stevengj for the explanations!

---

<div class="post-metadata">

**Author:** ![pengwyn](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pengwyn/32/6961_2.png) [@pengwyn](https://discourse.julialang.org/u/pengwyn)\
**Post date:** [October 10, 2020, 2:07am UTC](https://discourse.julialang.org/t/unique-doesnt-seem-to-obey-definitions/47455/8 "2020-10-10T02:07:22Z")

</div>

From a comment by @yuyichao in the GH PR, it finally clicked for me that `unique` is a function that acts on sets, which makes perfect sense for where it is defined in `set.jl`.

But this makes me realise that I need a function `unique` which never tries to hash the items in the list. I pretty much need a function that relies only on transitivity of `==`. This might be best explained as a “group by” operation followed by selecting one element from each group. Here’s a crappy implementation:

```julia
function group_by(itr ; by=Base.:(==))

    groups = Vector{Any}[]

    for item in itr
        ind = findfirst(x -> by(x, first(g)), groups)
        if ind === nothing
            push!(groups, Any[item])
        else
            push!(groups[ind], item)
        end
    end

    groups
end

function unique_by(itr ; by=Base.:(==))
    groups = group_by(itr ; by)
    return first.(groups)
end

```

This kind of unique does not have any guarantees over which item is returned, as all of the items in each group may contain hidden state (e.g. I could have just as easily used `last` instead of `first`). But every item in each group must satisfy `x == y`.

To bring this back to my use case, I have objects that have been wrapped by `CxxWrap.jl` and so are only pointers. I can invoke a C++ function `a == b` but I don’t have any sensible way to give these objects a hash.

The `unique_by` above could be made more efficient (it doesn’t need to form the groups first) but I think this is illustrating the difference between a `Dict` and a set of lists.