11K views · Jul 18, 2014 · 11:32 · 2 HN recommenders · 5 mentions · discussed 2019–2021
John Scholes builds a depth-first tree-search operator step by step in a Dyalog APL session. It covers higher-order functions and runs the search on the N-Queens problem.
Why Hacker News points people here: HN commenters call it a beautiful, brilliant demonstration of APL's expressiveness and a model of clear narration.
Beautiful APL programming demonstration by the late John Scholes.
APL is great. If you haven't seen them, the late John Scholes did a number of absolutely beautiful demonstrations programming in APL[1], [2], [3]. [1]: this video [2]: link [3]: link
Brilliant step-by-step APL depth-first search narration by John Scholes.
That 1975 APL demonstration is lovely. Much has been preserved in Dyalog and GNU APL - it's very interesting to see how timeless the core APL functions are. I'm very fond of a number of videos by the late John Scholes narrating APL solutions step by step, including the well-known demonstration of Conway's Game of Life in APL (0). His videos on depth-first search (1) and solving sudoku (2) are also brilliant. (0) link (1) this video (2) link
Beautiful presentation on higher-order functions for reusable depth-first search; should be seen.
You might like looking at how Dyalog handles higher-order functions; John Scholes really put this beautiful presentation together about using them as a depth-first search reusable function this video and if you haven't seen it, you should!
Comment is about APL versus Python; video link is incidental.
> Note also that you're being unfair to Python. List comprehensions, array index notation, and numpy methods cover pretty much everything you've mentioned in apl. All of that to cover ~ten symbols. Is it unfair to Python to point out that this is a huge difference in complexity that someone needs to learn to be able to do those things from scratch? > Which brings me back to what I said before: if I want a powerful array manipulation dsl, I still have it, but I'm not limited by it. Which is fine. It's just that the few operations of array manipulation DSL go so much farther than I expected they would. I do know that APL is not going to be the language to implement WireShark or Halo vNext. The big catch in paragraph two is "if my objects support that"; yes you would have to do something more complex in APL. But not /much/ more complex. In Python you'd need to understand classes and magic methods and overloading before you could write that overloaded addition - and understand CPython internals, C and NumPy to add it to NumPy objects, I imagine. I doubt you can do that all in APL, but then again if I'm correctly reading what l2 norm addition is, Pythagorean square-root-of-sum-of-squares including complex numbers, it's not a lot of code to write that anyway: values ← 4J3 ¯2J8 10 20 abs ← |values squared ← abs * 2 sum ← +/squared sqrt ← squared * 0.5 or without the temporary variables which don't add much clarity: ( +/ (|values) * 2 ) * 0.5 ⍨ is a cool operator which lets you swap
Cited as John Scholes's approach to tree representation with index vectors.
If you have cycles in your graph, you can build a tree out of a vector of indices, or as a table of parent/child node keys. The former is what John Scholes does[1], and the latter has plenty of common SQL examples. [1]: this video If you have a non-cyclic tree (e.g. a 256-trie) you can nest it directly: @/ will traverse to nodes, and COW keeps updates from trashing memory too much. However trees are rarely the best data structure: Binary search on a sorted list can beat b-trees simply because the end of the search will already be in cache, so for a routing table of IP address ranges, I use something like: ipStart where ipStart bin x
