I searched in the book for the passage the GP mentioned. It is on page 2, the 6th step in solving an interview problem. The steps are outlined in the book, and the code snippet for each listed. Here they are:
1- Scanning an array x and finding the running maximum is expressed by |\x (read “max scan of x”), the highest altitude to the West.
2- Reversing an array is achieved by inserting a | (“reverse”) before the array. ||\|x (“reverse max scan of reverse x”) will give us the highest altitude to the East.
3- Comparing two vectors element-wise is done with the & (“min”) operation, this is the water level.
4- The element-wise subtraction is -. Adding parentheses to ensure correct sequence of evaluation, and brackets to make it a function that takes an argument, results in {((|\x)&||\|x)-x}. This is a function that returns the height of the column of water at every point.
5- Using this function, we can easily get derived results, for example for the maximum height we can use |/ (“max over”), resulting in |/{((|\x)&||\|x)-x}.
6- For total water we can use +/ (“sum over”), resulting in +/{((|\x)&||\|x)-x}
Maybe you find this satisfying, I find it horrendous.
Your Python solution is very deeply coupled with this specific problem, more than half of the code consists of names taken directly from the problem description. I don't think it is equivalent with the K solution. You could add names in a similar manner to it and they would be more equivalent.
For me a nice thing about the Iverson languages is that idiomatic programs tend to be mathematically general and explain the problem in more general terms than a naive, immediate solution in a more popular scripting language.
Doesn't work on empty arrays, whereas the K does and gives the reasonable result of 0 (for total water) and -inf for maximum height. Maybe it doesn't matter, but sensible defaults are a good thing!
Edit: didn't look at the error closely enough to see that the only thing that breaks is the maximum height. That's not that bad, but still not ideal imo.
The result may be reasonable, but this is just a fluke.
Numpy complains that: "ValueError: zero-size array to reduction operation maximum which has no identity".
This error makes sense. The only meaningful result for the maximum of an empty array would be minus infinity. It should not be zero. If it's zero, it means the programming language makes the silent assumption that the elements are non-negative.
I very much prefer to have the code throw back a meaningful error at me than a reasonably looking result, and then fail silently in a different situation.
Would you agree with the statement, "the maximum of an array should be contained in that array?" That seems like a reasonable constraint that most languages uphold.
No. I think the maximum of (x:xs) should be equal to max x (maximum xs). (Using haskell notation). Logically this implies maximum [] should be -infinity if it is defined. On finite lists, maximum is also the same as the supremum, and on infinite sets the supremum doesn't necessarily have to be contained in the set. So there's at least some precedent for not having the maximum in the list.
Going by your definition, max (x:xs) = max x (max xs) = max x (max (head xs) (tail xs)) = ... ad infinitum. The basic problem with that definition is that it only really defines max for non-empty lists, otherwise the pattern-matching against (x:xs) will throw an exception.
In mathematics maximum and minimum of a set are elements of said set. So the empty set has neither a maximum nor a minimum.
There is another pair of terms that obeys the rules you want max and min to obey: supremum and infimum: <https://en.wikipedia.org/wiki/Infimum_and_supremum>. And indeed supremum of the empty set is -inf. And infimum of the empty set is +inf. That’s because supremum and infimum of a set don’t need to belong to said set. They only need to belong to the set of bounds (upper for supremum; lower for infimum) of said set.
That definition strikes me as intellectually satisfying but less useful for engineering software systems around (for the same reasons as the other commenter). But maybe it's more appropriate in the domains K is used for, I wouldn't know.
Adding to RodgerTheGreat's comment: for me, k's power is its rich set of adverbs that are convenient to write.
Notice that aside from reverse (monadic |), all verb symbols in the above code are in most other languages (max as |, min as &, plus as +, minus as -). Adverbs (such as / for reduce and \ for scan-reduce) make the symbols we already have more generally applicable.
I think a language could go a long way with a small set of basic arithmetic symbols alongside a rich set of adverb symbols.
And perhaps further worth noting, the reason K uses dyadic & and | for minimum and maximum (respectively) is because logical AND and logical OR are identical to minimum and maximum if the arguments happen to be boolean (0/1). The notation and selection of primitives illustrate a useful and memorable symmetry.
Just for reference, and since I work with Trino these days.
The benefit it gives me is that I almost never have to care about RAM or CPU. It just scales in all directions.
The negative compared to vector languages is that order is not guaranteed (as can be seen)
And the other negative of course is that it is not possible to write generalized functions.
I am not saying it is better, but I'll leave it here.
And yeah, it does not work with empty arrays. But this is my lunch break!
WITH measurements AS
(
SELECT index, m
FROM UNNEST (ARRAY[3, 2, 5, 5, 3, 6, 5, 7, 2, 9, 2, 6, 1, 7, 2, 6, 9, 1, 1, 4, 2, 9, 2]) WITH ORDINALITY as t(m, index)
),
tmp AS
(
SELECT index,
m,
LEAST(MAX(m) OVER ( ORDER BY index), MAX(m) OVER( ORDER BY index DESC)) - m as water_level
FROM measurements
)
SELECT MAX(water_level) as max_level,
SUM(water_level) as total_water
FROM tmp
And they say Perl is bad.