3 ms·

One example I like for K is: Maximum subarray sum[0]. The canonical K solution (sorry, my APL is too rusty to translate) is |/0(0|+)\ Yes, this is the com

by beagle3 10y ago

One example I like for K is: Maximum subarray sum[0]. The canonical K solution (sorry, my APL is too rusty to translate) is |/0(0|+)\ Yes, this is the complete function, and it is the efficient O(n) solution; A K programmer is likely to recognize it immediately (using eyes for pattern recognition). Now, if I were to rewrite it in infix/paren syntax, it would become: mss(x):=fold(max,0,scan(lambda(a,b) max(0,a+b), 0, x)) This is not at all more readable (arguably less readable) than the K version, and it's inherent, in the sense that the K uses your organic pattern matcher (supplied by eyes and brain) much better than a haskell/lisp version ever will. Similarly, ,// Is flatten; If you were to write it verbosely, it would be flatten(x):=converge(fold(concatenate,x)) While this may be more readable, the K syntax (as does the APL one) gives you a concise, well defined, pattern matchable version. (Which doesn't actually need documentation - the implementation is 3 chars, so if you want to know how it behaves on an empty list -- just read the implementation!) [0] https://en.wikipedia.org/wiki/Maximum_subarray_problem https://en.wikipedia.org/wiki/Maximum_subarray_problem

arcfide 10y ago
I believe the translation of |/0(0|+)\ is ⌈/0,(0⌈+)\
- Avshalom 10y ago
  K does a thing (like J I think?) where it's scan/reduce returns each subsequence/intermediate-value as it goes which is what makes that problem so trivial in K.
  - RodgerTheGreat 10y ago
    The K "over" adverb (/) is like a conventional reduce/accumulate/fold. The K "scan" adverb (\) produces a list of the intermediate results. Having both is extremely handy. If the verb argument of over/scan takes a single argument (rather than two), the adverbs will iterate to a fixed point. As before, "/" will return the final result and "\" returns all the intermediates. For example: +/1 2 3 6 +\1 2 3 1 3 6 *:/,,,0 0 *:\,,,0 (,,,0 ,,0 ,0 0)
    - arcfide 10y ago
      Oh wait, so you're not preserving the subsequence, you just preserving the sum. So it's a standard scan. So my original translation is correct, my subsequence preserving version is doing a bit more than this by preserving the subarray as well as the sum.
  - arcfide 10y ago
    Ah, if we have to preserve the sequence: ((⊃∘⍒0⌷⍉)⌷⊢)(+\,∘⍪,\)
- beagle3 10y ago
  I think this gives the correct answer, but the computation is different (which is fine - we're only looking at the answer); K over/scan go left-to-right, and if I'm not mistaken, APL and J go right to left, that is, in K: +/!5 equals ((((1+2)+3)+4)+5) which is not 1+2+3+4+5 whereas in APL/J it is +/iota5 equals (1+(2+(3+(4+5)))) which is 1+2+3+4+5 I find the APL approach mathematically consistent and elegant, but the K approach is more practical - it makes over and scan useful for state machines, parsing, and many other uses without having to reverse anything twice. But often, as in this case (or the flatten case) it doesn't matter which direction you start folding from.
kazinator 10y ago
Why don't you just learn the vocabulary of patterns used in a compressed representation, like LZ77? Then you can condense any language to make it more readable for your "organic pattern matcher" just by passing the source through gzip. Here is the thing: I have a pretty good idea of what flatten(x):=converge(fold(concatenate,x)) does without knowing what exact language it is written in, or having to crack open a reference manual for it. This is not so of your sample of puerlile line noise, which is completely arbitary. If we feed it to, say Golfscript, it will do something completely different. Also, if I delete a ) character from the above expression, I can guess that it is probably not well-formed: flatten(x:=converge(fold(concatenate,x)) ^ not matched flatten(x):=converge(fold(concatenate,x) ^ not matched Then names like flatten and converge are atoms. We could condense this code by giving them single-character names (using some Unicode glyphs perhaps or whatever). Let's just use roman capitals: F(x):=V(R(C,x)) It's not actually that long in the number of tokens or atoms. Anyway, most computer scientists and software engineers stop measuring code by character count by the time they get out of puberty.
- arcfide 10y ago
  Nobody wants to write proofs as English prose like they did when first proving basic algebraic properties. Yet those proofs are much easier to guess at the meaning of, even if you don't fully get it, than using our standard mathematical notation. Of course, it just so happens that our mathematical notation allows middle schoolers and high schoolers to think of these proofs as obvious and trivial, whereas they would have no idea what to make of the English proofs that are more "natural" to the English speaker. Of course, that notation that they use with such facility (even if they aren't particularly competent with it and just learned it last week) has no relation and no intuition at all to the English language, and makes no attempt to do so. Yet, I challenge you to back up your statement about character counting by showing me a Computer Scientist and a Software Engineer who no longer writes or uses traditional mathematical notation for anything, but has systematically moved over to the more intuitive and natural programming language of their choice, such as Scheme, C, or Haskell. APL is a suitable replacement for Mathematical notation and was designed as such. Other programming languages are not. That's a very important element. It's not about character counting. See Iverson's Notation as a Tool of Thought Turing Award lecture. You might have a stronger case if, since the advent of computing programming languages, which are demonstrably capable of representing a whole host of mathematical ideas and concepts directly, people have begun flocking to programming languages to replace their mathematical notation in the communication of ideas in non-computer science contexts. However, people rarely consider a programming language equivalent to be better/superior to traditional mathematical notation when they are talking amongst themselves in front of a whiteboard.

by beagle3 10y ago

arcfide 10y ago

I believe the translation of |/0(0|+)\ is ⌈/0,(0⌈+)\

Avshalom 10y ago
K does a thing (like J I think?) where it's scan/reduce returns each subsequence/intermediate-value as it goes which is what makes that problem so trivial in K.
- RodgerTheGreat 10y ago
  The K "over" adverb (/) is like a conventional reduce/accumulate/fold. The K "scan" adverb (\) produces a list of the intermediate results. Having both is extremely handy. If the verb argument of over/scan takes a single argument (rather than two), the adverbs will iterate to a fixed point. As before, "/" will return the final result and "\" returns all the intermediates. For example: +/1 2 3 6 +\1 2 3 1 3 6 *:/,,,0 0 *:\,,,0 (,,,0 ,,0 ,0 0)
  - arcfide 10y ago
    Oh wait, so you're not preserving the subsequence, you just preserving the sum. So it's a standard scan. So my original translation is correct, my subsequence preserving version is doing a bit more than this by preserving the subarray as well as the sum.
- arcfide 10y ago
  Ah, if we have to preserve the sequence: ((⊃∘⍒0⌷⍉)⌷⊢)(+\,∘⍪,\)
beagle3 10y ago
I think this gives the correct answer, but the computation is different (which is fine - we're only looking at the answer); K over/scan go left-to-right, and if I'm not mistaken, APL and J go right to left, that is, in K: +/!5 equals ((((1+2)+3)+4)+5) which is not 1+2+3+4+5 whereas in APL/J it is +/iota5 equals (1+(2+(3+(4+5)))) which is 1+2+3+4+5 I find the APL approach mathematically consistent and elegant, but the K approach is more practical - it makes over and scan useful for state machines, parsing, and many other uses without having to reverse anything twice. But often, as in this case (or the flatten case) it doesn't matter which direction you start folding from.

kazinator 10y ago

Why don't you just learn the vocabulary of patterns used in a compressed representation, like LZ77? Then you can condense any language to make it more readable for your "organic pattern matcher" just by passing the source through gzip. Here is the thing: I have a pretty good idea of what flatten(x):=converge(fold(concatenate,x)) does without knowing what exact language it is written in, or having to crack open a reference manual for it. This is not so of your sample of puerlile line noise, which is completely arbitary. If we feed it to, say Golfscript, it will do something completely different. Also, if I delete a ) character from the above expression, I can guess that it is probably not well-formed: flatten(x:=converge(fold(concatenate,x)) ^ not matched flatten(x):=converge(fold(concatenate,x) ^ not matched Then names like flatten and converge are atoms. We could condense this code by giving them single-character names (using some Unicode glyphs perhaps or whatever). Let's just use roman capitals: F(x):=V(R(C,x)) It's not actually that long in the number of tokens or atoms. Anyway, most computer scientists and software engineers stop measuring code by character count by the time they get out of puberty.

arcfide 10y ago
Nobody wants to write proofs as English prose like they did when first proving basic algebraic properties. Yet those proofs are much easier to guess at the meaning of, even if you don't fully get it, than using our standard mathematical notation. Of course, it just so happens that our mathematical notation allows middle schoolers and high schoolers to think of these proofs as obvious and trivial, whereas they would have no idea what to make of the English proofs that are more "natural" to the English speaker. Of course, that notation that they use with such facility (even if they aren't particularly competent with it and just learned it last week) has no relation and no intuition at all to the English language, and makes no attempt to do so. Yet, I challenge you to back up your statement about character counting by showing me a Computer Scientist and a Software Engineer who no longer writes or uses traditional mathematical notation for anything, but has systematically moved over to the more intuitive and natural programming language of their choice, such as Scheme, C, or Haskell. APL is a suitable replacement for Mathematical notation and was designed as such. Other programming languages are not. That's a very important element. It's not about character counting. See Iverson's Notation as a Tool of Thought Turing Award lecture. You might have a stronger case if, since the advent of computing programming languages, which are demonstrably capable of representing a whole host of mathematical ideas and concepts directly, people have begun flocking to programming languages to replace their mathematical notation in the communication of ideas in non-computer science contexts. However, people rarely consider a programming language equivalent to be better/superior to traditional mathematical notation when they are talking amongst themselves in front of a whiteboard.