Am I using max correctly?

#1

Doesn’t work: https://play.crystal-lang.org/#/r/6kor/edit

struct Item
end

test = Hash(Int32, Item).new
test[1] = Item.new
test[5] = Item.new
test[2] = Item.new
test[25] = Item.new

puts test.max[0]

Works: https://play.crystal-lang.org/#/r/6kot

test = Hash(Int32, Int32).new

test[1] = 0
test[5] = 0
test[2] = 0
test[25] = 0

puts test.max[0]

Is this a bug, or am I doing it wrong? :)

0 Likes

#2

When using a struct, the error is:

in macro 'macro_94090632191376' /usr/lib/crystal/tuple.cr:293, line 5:

   1. 
   2.       cmp = self[0] <=> other[0]
   3.       return cmp unless cmp == 0
   4.     
>  5.       cmp = self[1] <=> other[1]
   6.       return cmp unless cmp == 0
   7.     

undefined method '<=>' for Item

However… max doesn’t check against the values, it checks against the keys, right? So why is it complaining about Item? In fact, it doesn’t even sort by the values.

If it did, https://play.crystal-lang.org/#/r/6koy/edit would return {2, 5}, not {25, 4}? It sorts by the keys!?

0 Likes

#3

Hash(K,V) type includes Enumerable({K,V}). And #max method is defined in Enumerable.

This means targets of the comparison for #max(or #min) are not values of that hash, but tuple of key and value({key, value})

Therefore, test.max in the last example will return the maximum object in {1, 1}, {5, 2}, {2, 5} and {25, 4}.

That is {25, 4}, because that the comparison of two tuples compares the first element of both tuples at first.

If you want to get the key of the max value of that hash, you can use #max_by like https://play.crystal-lang.org/#/r/6kp7 .

1 Like

#4

Yeah, but it’s using [0] (which is the key) to sort them right? So why is it saying it has a problem with Item? Which is the value ([1]). If the comparison is using [0], the value shouldn’t have any effect on what the max is?

0 Likes

#5

The Enumerable#max is not only for Hash.

When the #max method is called for {0, 1} and {0, 2}, the comparison of the second value of both tuples will be needed.

Actually, there cannot be duplicate keys in the Hash.

But compiler cannot know that.

This is why the compiler requires #<=> method to the type of the hash value.

0 Likes

#6

Interesting, thanks @arcage!

I’m still puzzled on https://play.crystal-lang.org/#/r/6kpg, it shows {25, 4} ? If the second value of both tuples are required for the comparison, why doesn’t it return {2, 52}?

0 Likes

#7

The second value(value of Hash) of the tuples will be compared only when the first value(key of Hash) of the tuples are same.

In the case of Hash, keys are always different values.

But for the compiler, this is not a comparison of “tuple of key and value of the Hash” but only of just “tuple of Int32 and Int32 object”.

Because the compiler cannot know the first values are always different, the compiler think that “When the first values are same, I probably need the second value comparison”.

1 Like

#8

@gring max[0] is not “compute the maximum value of the first element”. It’s “compute the maximum, then give me the first element”. I guess you want max_by &.[0]. But please also learn about how Enumerable works, how Hash is an Enumerable of Tuple, and how tuples are sorted, as arcage explains.

0 Likes

#9

I created an issue here, https://github.com/crystal-lang/crystal/issues/7585

Thanks for your attention

0 Likes

#10

Just note that it’s not an issue. It’s how things work if you combine what the Enumerable module does with how Hash includes Enumerable.

0 Likes

#11

I closed it. I think i’m getting too involved with code that is beyond the scope of my knowledge, apologies

0 Likes

#12

@girng I’ll try to explain it briefly.

There’s the Enumerable(T) module. It depends on an abstract each method whose job is to yield elements of type T to a block. Array(T) for example includes Enumerable(T), meaning that each will yield all of the array’s elements in order to the block. Relying on the each method we can define many more methods: select (use each and just keep the ones that the block given to select return true), all? (use each and determine if all the elements yielded to the block given to all? return true), etc. max is also defined in terms of each: traverse all elements and find the one with the maximum value. I suggest you take a look at Enumerable’s source code.

Now, Hash(K, V) includes Enumerable({K, V}). What that means is that if you do:

h = {1 => 'a', 2 => 'b'}
h.each do |x|
  p x
end

then x will be of type {Int32, Char}, which is syntax sugar for Tuple(Int32, Char). That is, a Hash can be seen as a sequence of key-value tuples.

Then you can do hash.max and that will return the tuple with the maximum value, considering a hash as a sequence of tuples. Comparing two tuples is comparing their elements in order, the greater one is greater, so {2, 1} is greater than {1, 10} (2 > 1), but less than {10, 1} (2 < 10) and than {2, 3} (2 == 2 so we move on to the second element and we have that 1 < 10).

Now, there’s something else. You can do:

h = {1 => 'a', 2 => 'b'}
h.each do |key, value|
  #  ...
end

Huh? But Hash#each is supposedly yielding a single tuple with two elements, how come it seems it’s yielding two elements? That’s another feature of Crystal, similar to what Ruby does (Ruby does it only for Array, Crystal only for Tuple) where if a block yields a tuple you can unpack the tuple elements in the block like that. So this works too:

a = [{1, 2}, {3, 4}]
a.each do |x, y|
  # x, y == 1, 2
  # x, y == 3, 4
  # ...
end

Letting Hash be Enumerable is great because it means we can apply a lot of methods like max, select, all?, etc., to it.

I hope this explained a bit of what’s going on with the max method on Hash.

2 Likes

#13

OHHHH <light-bulb moment>, ding

Yeah, I think I get it now!! So the magic happens on that comparison operator (>)
Line 772:

 if i == 0 || value > max

If it’s just an Array, it’s comparing just the value. If it’s iterating a Hash, the comparison operator now uses the Tuple’s ELEMENTS, in order. In my case, it would be {Int32, Item}. Since my Item struct doesn’t have a comparison method overload, the compiler is going to error!

I hope I got that right?!

1 Like

#14

@girng That’s correct! :slight_smile:

1 Like

#15

HAHA. This is pretty sneaky though!!

Check this out

test = Hash(Int32, Int32).new

test[26] = 3
test[2] = 1
test[26] = 1

puts test.max

Output: {26, 1}

However…

test = Hash(Int32, Int32).new

test[26] = 1
test[2] = 1
test[26] = 3

puts test.max

Output: {26, 3}

Order matters!


With that said, for my case, I should use test.keys.max? Which means I don’t have to add an operator comparison overload to my Item struct.

0 Likes

#16

Sweet! I was pulling my hair out bawhaha

That was pretty cool cause I read your post, then it clicked in my brain “oh wow”. I then started replying what I “now know”, but it felt like I was plagiarizing you… That’s a weird phenomena, whatever it is

edit: I guess it’s called LEARNING lol

2 Likes

#17

Hi,

With this code it worked :slight_smile:

struct Item
  def <=>(other)
  	0
  end
end


test = Hash(Int32, Item).new


test[1] = Item.new
test[5] = Item.new
test[2] = Item.new
test[25] = Item.new


puts test.max[0]

https://play.crystal-lang.org/#/r/6l88

1 Like