[beagle3]

> I think with a language like k or q, which appears to be purpose-built for certain types of problems,

The thing is, it's not purpose built, and it doesn't even appear to be if you suspend your disbelief. The only reason you'd think it is purpose built is because "well, it can't be this short if it wasn't purpose built". But if you go over the manual, and find special built operators, please tell us what they are.

e.g., to compute an average, you can use the function avg:{(+/x)%#x} - with the exception of parentheses, every character has an orthogonal function. Similarly, the maximum subarray sum solution mss:|/0(0|+)\ ; and there are many others. And it's not just math stuff - http://nsl.com has lots of other examples of many kinds -- and most importantly -- is an operating system + GUI not general enough?

[robryk]

How would you represent a graph and implement DFS in K?

[beagle3]

If you are really interested, http://nsl.com/ is a treasure trove - quite a few of the examples are extremely well documented, some or not, but there's a wealth of information there.

Specifically about graphs, you can look at:

http://nsl.com/papers/order.htm - topological sorting

http://nsl.com/k/tarjan.q - strongly connected components

http://nsl.com/k/loop.q - find loops in graphs

I think in all of these the graph is represented either as a list of edges or a dictionary of node->(list of nodes that it has edges to)

[robryk]

Thanks, I've missed the SCC one. I will try to understand it. (The reason I've asked about DFS in particular is that it is inherently sequential. This SCC algorithm probably encapsulates some kind of DFS.)

[beagle3]

K has interesting sequential goodies as well: over ("fold" in Lisp/Haskell, "reduce" in python), and scan (same, with all intermediate results returned as well). But it also has the unary ("monadic" in APL terminology) counterparts to these essentially binary operators, which I don't remember from Lisp or Haskell (but I'm neither a Lisper or a Haskellite, they probably are there somewhere..)

Unary over is the "fixed point"/"converge" adverb, which does

    x <- f(x)

until x stabilizes (to within floating point tolerance if it is a float), returns to its first value, or goes through a requested number of iterations.

The best example of this that I can think off is the K "flatten" idiom:

   ,//

read: "concat over, converge". That is, given a general list, it concatenates all its items promoting atoms to one-element lists - thus, flattening one level of the list; And then applies it again and again until there is no further change, thus flattening successive levels of the list.

Is this the most efficient way to do this? No! in fact, for an unbalanced one sided list it will do O(n^2) where n is the number of items, with a best (and idiomatic Lisp/Haskell) solution being O(n), although it's usually 100 chars rather than 3.

But the actual code orchestrated by these 3 chars behind the scenes is all tight C loops, so for small n it will beat complex solutions. And it is all of 3 self-describing, easily remembered, easily recognized, easily optimized (if Arthur ever cared ...) characters. If you care about worst case, you can easily code the standard Lisp/Haskell solution just as you would in those languages. See [0] for more.

The underlying computational model fits sequential, parallel, SIMD, and almost every other paradigm much better than all the popular programming languages. Unfortunately, there's a learning curve that puts of most people (and is perhaps insurmountable to some people who have no problem with Python, Java, C or PHP) - it's much more Math-oriented.

[0] http://www.math.bas.bg/bantchev/place/k.html

edit: added [0] link and ref

[fidotron]

Numbers in arrays can be treated as pointers, into that same array, giving a graph. It's just a question of context. If you were storing RDF triples in K you'd simply have an array for subjects, one for objects, one for predicates, and one of the URIs/text. Simply store the index of the URI/text item in each of the subject, object and predicate columns. An individual triple would be formed by the same index applied to the subject, object and predicate arrays.

DFS is then a variation of the more familiar functional style of tackling the problem where you have your end condition (i.e. something that matches what you're looking for) and failing that do something else (typically recursion).

I can't recall enough of the K syntax these days to actually implement that right now though, or if K has TCO.