3 ms·

(HN reply speed limitations are silly. :) Right, as you noticed in your second comment, I'm talking about the inner -1, which should never be hit. The issue is

by dilap 6y ago

(HN reply speed limitations are silly. :) Right, as you noticed in your second comment, I'm talking about the inner -1, which should never be hit. The issue is broader than just the specific issue of binary search; it's a question of, which language design features lead you to writing more reliable software, more easily? I'm unconvinced about array access returning Maybe being a good idea, because it's generally a bug, not actual uncertainty. The fact that the usage of the returned maybe value just serves to obscure possible bugs in the implemenatation of binary search is one example of that. At the broadest level, running a program can be thought of as the combination of two things: 1. The program itself 2. The input to the program Now there are two ways your program can encounter an "error". It can be because there is a bug in (1), or it can be because there is bad input in (2). I think as a general rule, to handle (1) you just need to crash gracefully. The program itself has become confused; there is nothing you can do to recover. For (2), the program itself is not confused, and it should handle the data it has been given in the best possible way. Thus, things like sum-types are appropriate for type 2 errors, but not for type 1 errors. (That's my argument, anyway.) (I recommend checking out the Zig language, which gets this exactly right IMO.)

1-more 6y ago
> I'm unconvinced about array access returning Maybe being a good idea, because it's generally a bug, not actual uncertainty. So that's the thing: in JS (where I spend most of my time) I never wrap an array access in a try/catch even though it could throw. Rather, I probably have an if statement that wraps up any array access I'm unsure about. That way I avoid throwing for the out-of-bounds case. So I'm with you there: if I wrote Elm the way I write JS it would be clumsy and redundant. However I don't write Elm the way I write JS. That if-block for safety I mentioned earlier? I usually move that into the Nothing case when my Dict/List/Array access/query came up empty. In Elm you have to consider that the array access could go out of bounds, that you could end up trying to get the head of an empty list, that you could query a Dict with a key it doesn't have. Rather than move those to an if block surrounding same, we usually move those inside. In Haskell you can leave those cases undefined, natch. I like that in Elm there is no such thing as undefined behavior. I've heard some very rad things about Zig so I'll definitely be checking it out soon.
- dilap 6y ago
  > I like that in Elm there is no such thing as undefined behavior. Thanks, that's an interesting perspective to consider. I do know most things I've read about Elm have been very positive, so apparently it does work pretty well in practice!
  - 1-more 6y ago
    WAIT my turn to eat crow here: that "should never happen" -1 return statement actually does happen when the search value is greater than the greatest value in the array: https://ellie-app.com/byQ8vnnGTLba1 https://ellie-app.com/byQ8vnnGTLba1
    - dilap 6y ago
      Ha, you're right! So the algorithm is correct, but I think sort of by accident. If you change the initial check from "if lo > hi then" to "if lo >= hi then", the algorithm remains correct, and does not depend on accessing an out-of-bounds array index. (The input range to the recursive search is half-open, so the check for an empty range should be greater-than-or-equals, not strict-greater-than.)
      - 1-more 6y ago
        Yeah I immediately checked that after commenting since it's exactly the off-by-half thing I never get right without checking and yup, you can end up with a never used code path. What a rollercoaster. Ah well. For this particular thing you do in fact end up with one. In other cases whenever I end up with an unfollowed code path I can usually refactor it out. Non-empty lists are a good way of doing that, for instance.

by dilap 6y ago

1-more 6y ago

> I'm unconvinced about array access returning Maybe being a good idea, because it's generally a bug, not actual uncertainty. So that's the thing: in JS (where I spend most of my time) I never wrap an array access in a try/catch even though it could throw. Rather, I probably have an if statement that wraps up any array access I'm unsure about. That way I avoid throwing for the out-of-bounds case. So I'm with you there: if I wrote Elm the way I write JS it would be clumsy and redundant. However I don't write Elm the way I write JS. That if-block for safety I mentioned earlier? I usually move that into the Nothing case when my Dict/List/Array access/query came up empty. In Elm you have to consider that the array access could go out of bounds, that you could end up trying to get the head of an empty list, that you could query a Dict with a key it doesn't have. Rather than move those to an if block surrounding same, we usually move those inside. In Haskell you can leave those cases undefined, natch. I like that in Elm there is no such thing as undefined behavior. I've heard some very rad things about Zig so I'll definitely be checking it out soon.

dilap 6y ago
> I like that in Elm there is no such thing as undefined behavior. Thanks, that's an interesting perspective to consider. I do know most things I've read about Elm have been very positive, so apparently it does work pretty well in practice!
- 1-more 6y ago
  WAIT my turn to eat crow here: that "should never happen" -1 return statement actually does happen when the search value is greater than the greatest value in the array: https://ellie-app.com/byQ8vnnGTLba1 https://ellie-app.com/byQ8vnnGTLba1
  - dilap 6y ago
    Ha, you're right! So the algorithm is correct, but I think sort of by accident. If you change the initial check from "if lo > hi then" to "if lo >= hi then", the algorithm remains correct, and does not depend on accessing an out-of-bounds array index. (The input range to the recursive search is half-open, so the check for an empty range should be greater-than-or-equals, not strict-greater-than.)
    - 1-more 6y ago
      Yeah I immediately checked that after commenting since it's exactly the off-by-half thing I never get right without checking and yup, you can end up with a never used code path. What a rollercoaster. Ah well. For this particular thing you do in fact end up with one. In other cases whenever I end up with an unfollowed code path I can usually refactor it out. Non-empty lists are a good way of doing that, for instance.