4 ms·

I get that, but I feel like the questions I'm curious about have still not been answered... 1. Array out of bounds is different than other types of errors, lik

by dilap 6y ago

I get that, but I feel like the questions I'm curious about have still not been answered... 1. Array out of bounds is different than other types of errors, like e.g. file does not exist: Because the size of the array is entirely controlled by the program, and a non-buggy program can completely avoid array out of bounds, it knows its access to the array will not return None: Array access returning None is not an inherent condition that must be handled by any program. So my question is, what does this look like then in conditions when you know you won't access out of bounds? Specifically, that makes me wonder what a binary search implementation in Elm would look like. Binary search knows it will not access outside the bounds of the array. So how do you handle get returning Maybe? Do you just assert the result is not null? OK, I got curious and searched, and here's one random implementation: https://github.com/terezka/elm-algorithms/blob/master/BinarySearch.elm https://github.com/terezka/elm-algorithms/blob/master/Binary... The answer is it checks for Nothing (which should never happen!) and just returns -1 if it does happen. This does not seem good to me! If Array.get is returning Nothing, this indicates a bug in the binary search implementation. Instead of getting a panic or crash or other indication that a bug has ocurred, the design of get has encouraged the author to silently swallow this condition and return -1. 2. Second question: There are many of other kinds of problems that can happen besides array out of bounds access; it seems unclear to me how you could handle that with Maybe: What if you divide by 0? What if you overflow the range of a type? What if you run write a recursive function that exhausts memory? In summary, Maybe to handle places where the program is genuinely uncertain about something is great, but I'm unconvinced of its value in modeling situations that should never occur in a non-buggy program. I've been playing with the Zig language recently, and I feel like it gets this exactly right. - Optional types for cases where a value might or might not be there - Sum-type with a set of errors and the value for cases where program input may result in an error - Crash with a stacktrace for cases where a bug in the program is detected (e.g., array out of bounds access)

1-more 6y ago
-1 seems ok here. The algo is returning the index at which the array contains the search value; returning -1 is a pretty normal way of indicating that there is no such index. She could of course change the search function to return a Maybe Int, then return Nothing in the case where the array does not contain it. Either way makes sense to me. The -1 value is actually warming on me more and more because if the returned index is later used to access the array, it will definitely return Nothing. But using Maybe.andThen to monadically deal with a Maybe wrapped return value that would also be cool. Float division by zero works the way IEEE floats work: it becomes +/- Infinity. For Integers it actually becomes zero. This makes sense because to me you probably should have handled the case where the denominator was 0 before you got to the point of doing division. Like are you taking the mean of an empty list? What's going on?
- dilap 6y ago
  The -1 will never actually happen though -- it's -1 if the binary search algorithm itself tries to do an out-of-bounds array access. If that happens, your binary search had a bug. So in this case possible bugs are being obscured, rather than surfaced. This is bad. Integer division by 0 defining to 0 is interesting and certainly convenient; arguably you will accidentally end up obscuring bugs, when you didn't intend to divide by 0. The broader point I'm making is it doesn't seem great to me to represent what are basically bugs with Maybe.
  - 1-more 6y ago
    I think you're misreading it. It only returns a value _other_ than -1 when the value at mid is equal to the search value. It returns -1 when the number is not found in the array. See here: https://ellie-app.com/byLXrykwMV4a1 https://ellie-app.com/byLXrykwMV4a1
    - 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.)

by dilap 6y ago

1-more 6y ago

-1 seems ok here. The algo is returning the index at which the array contains the search value; returning -1 is a pretty normal way of indicating that there is no such index. She could of course change the search function to return a Maybe Int, then return Nothing in the case where the array does not contain it. Either way makes sense to me. The -1 value is actually warming on me more and more because if the returned index is later used to access the array, it will definitely return Nothing. But using Maybe.andThen to monadically deal with a Maybe wrapped return value that would also be cool. Float division by zero works the way IEEE floats work: it becomes +/- Infinity. For Integers it actually becomes zero. This makes sense because to me you probably should have handled the case where the denominator was 0 before you got to the point of doing division. Like are you taking the mean of an empty list? What's going on?

dilap 6y ago
The -1 will never actually happen though -- it's -1 if the binary search algorithm itself tries to do an out-of-bounds array access. If that happens, your binary search had a bug. So in this case possible bugs are being obscured, rather than surfaced. This is bad. Integer division by 0 defining to 0 is interesting and certainly convenient; arguably you will accidentally end up obscuring bugs, when you didn't intend to divide by 0. The broader point I'm making is it doesn't seem great to me to represent what are basically bugs with Maybe.
- 1-more 6y ago
  I think you're misreading it. It only returns a value _other_ than -1 when the value at mid is equal to the search value. It returns -1 when the number is not found in the array. See here: https://ellie-app.com/byLXrykwMV4a1 https://ellie-app.com/byLXrykwMV4a1
  - 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.)