Crystal: why ruby and crystal are giving completly different result when using bsearch ?

[unplugandplay]

This is my program:

statuses = ["Cancelled", "Completed", "Open", "Optional", "Shipped"]
p %{bsearch  s <=> "Completed"}
p statuses.bsearch{|s| s <=> "Completed"}
p "     ------   "
p %{ bsearch "Completed" <=> s}
p statuses.bsearch{|s| "Completed" <=> s}
p "     ------   "
p %{ bsearch s == "Open"}
p statuses.bsearch{|s| s == "Open"}
p "     ------   "
p %{ bsearch s == "Completed"}
p statuses.bsearch{|s| s == "Completed"}
p "     ------   "
p %{ bsearch "Completed" == s}
p statuses.bsearch{|s| "Completed" == s}
p "     ******   "
p "     ------   "
p %{ bsearch_index  s <=> "Completed"}
p statuses.bsearch_index { |s, i|  s <=> "Completed"}
p "     ------   "
p %{ bsearch_index  "Completed" <=> s}
p statuses.bsearch_index { |s, i|  "Completed" <=> s}
p "     ------   "
p %{ bsearch_index s == "Open"}
p statuses.bsearch_index{|s,i| s == "Open"}
p "     ------   "
p %{ bsearch_index s == "Completed"}
p statuses.bsearch_index{|s,i| s == "Completed"}

Result with ruby:

"bsearch  s <=> \"Completed\""
nil
"     ------   "
" bsearch \"Completed\" <=> s"
"Completed"
"     ------   "
" bsearch s == \"Open\""
"Open"
"     ------   "
" bsearch s == \"Completed\""
nil
"     ------   "
" bsearch \"Completed\" == s"
nil
"     ******   "
"     ------   "
" bsearch_index  s <=> \"Completed\""
nil
"     ------   "
" bsearch_index  \"Completed\" <=> s"
1
"     ------   "
" bsearch_index s == \"Open\""
2
"     ------   "
" bsearch_index s == \"Completed\""
nil

Result with crystal:

"bsearch  s <=> \"Completed\""
"Cancelled"
"     ------   "
" bsearch \"Completed\" <=> s"
"Cancelled"
"     ------   "
" bsearch s == \"Open\""
"Open"
"     ------   "
" bsearch s == \"Completed\""
nil
"     ------   "
" bsearch \"Completed\" == s"
nil
"     ******   "
"     ------   "
" bsearch_index  s <=> \"Completed\""
0
"     ------   "
" bsearch_index  \"Completed\" <=> s"
0
"     ------   "
" bsearch_index s == \"Open\""
2
"     ------   "
" bsearch_index s == \"Completed\""
nil

Can anyone tell me which language has it right, and why, or are implementations of bsearch doing it right but with completly different intents ;)

[straight-shoota]

It seems the Ruby implementation ensures that the block return value is actually a boolean true/false value, whereas the Crystal implementation accepts any truthy value as true and any falsey value as false.

The return type of s <=> "Completed" is Int32 which is always truthy, so the bsearch algorithm will always return the first entry / first index.

I'm pretty sure this behaviour of the Crystal implementation is unintended.
When the return type of the block is not Bool, an error should be raised on compile time. Nilable type Bool? should be allowed, but when the return value is nil, this should be a runtime error.

[oprypin]

I really want to agree with @straight-shoota here, but I'm afraid it's not that simple because the current behavior is inherent to so many places in Crystal, and likely intentionally so.

[oprypin]

Meh, then I guess it would just need to be a more global change.
Regarding Bool | Nil - that shouldn't be a special case, the same should apply to any union

[straight-shoota]

The documentation of #bsearch already explicitly mentions true and false values. The behaviour for any other value is not defined. I think we should help enforce not using any other values.

[asterite]

Ruby's bsearch works in two modes, check the docs: you can either always return true/false or always return a number. The second mode is not available in Crystal, only the first one, and any value can act as true/false using truhiness.

[98-f355-f1]

@unplugandplay

In MRI Ruby, you shouldn't use "==" or the spaceship operator, it will most likely return nil, use "<=" or ">=", it's not very clear in the documentation.

Personally, I don't like the bsearch output and the way to use it, I usually will always write my own bsearch if neccessary... I guess that if we were searching for any first value that fit the condition then it is ok, but when I use it, I'd like to know if the item exists or not... or what is the value at a certain index.

[RX14]

For now, we should specify the return type of the block such that this fails to compile.

[unplugandplay]

@98-f355-f1 thx, I think it is the best way for now, so I can simply relicate ruby way

[asterite]

I guess this is something to improve (maybe having the two modes like in Ruby is fine).

[unplugandplay]

Ok, then maybe shall I try to push one pull request of modified code in the next few days ;)

[straight-shoota]

This still needs to be fixed.

[asterite]

@unplugandplay You can try, I'm not sure if it's possible to do (we don't have overloads based on a block's type, but maybe there's a way around it).

[98-f355-f1]

@straight-shoota

This still needs to be fixed.

What is your intended output or solution. The Crystal behavior is similar to MRI and the algorithm is pretty good as it shows an Agner type optimization. My only complaint is that it is difficult to read without the atypical lo and hi and other parameter names. It could be optimized a little more if it didn't have to worm around the indexable library, then into it's own file and through macros.

Part of the optimization would be to include the bsearch method within each class Array, String and that was implementation specific to that class, that is what Java does, it would save a few bytes and instructions, thus leading to slightly faster results, not that it's slow right now however.

If I had a suggestion, just add where you can bsearch for the specific value with a single T type overload, as well as the required block... in order to get the behavior I desired as a new overload of

Array(T).bsearch(value : T) : T

[1, 2, 3, 4, 5, 6, 7, 8].bsearch(4) # => 4 or nil if not present.

Otherwise, it doesn't need to be rewritten.

[straight-shoota]

@asterite

def bsearch
  bsearch_impl(typeof(yield)) { yield }
end

private def bsearch_impl(type : Bool.class)
  # ...
end

private def bsearch_impl(type : Int.class)
  # ...
end

I'm not sure if we need the Int mode operation. Is this really useful? Currently, this is not supported in Crystal and we can do without it (at least for now).
The only immediate action would be to ensure that the blocks's return type is Bool (or Bool | Nil in order to be able to search types which are only partially comparable).

[asterite]

@straight-shoota I agree