2 ms·

Interesting takeaway (paraphrased): >Algorithms are not programs and should not be written in programming languages and can/should be simple, while programs ha

Interesting takeaway (paraphrased): >Algorithms are not programs and should not be written in programming languages and can/should be simple, while programs have to be complex due to the need to execute quickly on potentially large datasets. Specifically discussed in the context of concurrent programs executing on multiple CPUs due to order of execution differing. Defining programs as: >Any piece of code that requires thinking before coding >Any piece of code to be used by someone who doesn't want to read the code Apparently he has been giving this talk for a while: https://www.youtube.com/watch?v=uyLy7Fu4FB4 https://www.youtube.com/watch?v=uyLy7Fu4FB4 (previous discussions of it here?) Interesting that the solid example of simplifying finding the smallest item in a set to finding the smallest value equal to or less than that value and starting the search with the value negative infinity was exactly "Define Errors Out of Existence" from John Ousterhout's book: https://www.goodreads.com/book/show/39996759-a-philosophy-of-software-design https://www.goodreads.com/book/show/39996759-a-philosophy-of... as discussed here previously: https://news.ycombinator.com/item?id=27686818 https://news.ycombinator.com/item?id=27686818 (but of course, as an old (La)TeX guy, I'm favourably disposed towards anything Leslie (La)mport brings up)

MrMcCall 2y ago
> starting the search with the value negative infinity But then there is no differentiation between the result of the empty set and a set containing only negative infinities. I consider them separate conditions and would therefore make them separate return values. That's why I would prefer returning a tuple of a bool hasMax and an int maxV, where maxV's int value is only meaningful if hasMax is true, meaning that the set is non-empty. Another way of doing such would be passing in an int defMax that is returned for the empty set, but that runs into the same problem should the set's actual max value be that defVal. Anyway, I typed it up differently in my other toplevel comment in this thread.
- ndriscoll 2y ago
  Abstractly dealing with a problem where there's already a negative infinity is no problem. e.g. you can just add another negative infinity that's even smaller. That negative infinity can also be your error value; concretely you might do that by writing a generic algorithm that operates on any Ordered type, and then provide an Ordering instance on Result[E,A] where an E is less than all A. `A` could be some extended number type, or another `Result[E,A']`, or whatever thing with its own `Ordering`.
- aragilar 2y ago
  But why do you care that the set is empty (in the abstract, obviously if there was a reason you'd expect the set to be non-empty, that's a different thing)? The trick is to think about invariants and state, which if you frame it that way, the empty set case implies there is only a single state.

MrMcCall 2y ago

> starting the search with the value negative infinity But then there is no differentiation between the result of the empty set and a set containing only negative infinities. I consider them separate conditions and would therefore make them separate return values. That's why I would prefer returning a tuple of a bool hasMax and an int maxV, where maxV's int value is only meaningful if hasMax is true, meaning that the set is non-empty. Another way of doing such would be passing in an int defMax that is returned for the empty set, but that runs into the same problem should the set's actual max value be that defVal. Anyway, I typed it up differently in my other toplevel comment in this thread.

ndriscoll 2y ago
Abstractly dealing with a problem where there's already a negative infinity is no problem. e.g. you can just add another negative infinity that's even smaller. That negative infinity can also be your error value; concretely you might do that by writing a generic algorithm that operates on any Ordered type, and then provide an Ordering instance on Result[E,A] where an E is less than all A. `A` could be some extended number type, or another `Result[E,A']`, or whatever thing with its own `Ordering`.
aragilar 2y ago
But why do you care that the set is empty (in the abstract, obviously if there was a reason you'd expect the set to be non-empty, that's a different thing)? The trick is to think about invariants and state, which if you frame it that way, the empty set case implies there is only a single state.