Frame from Depth-first search in APL Plays with YouTube's privacy-enhanced embed

Depth-first search in APL

Open on YouTube First HN thread

2 HN users recommended this tutorial in 3 different months between 2019 and 2021.

2007–2026
3 strong recommendations 2 citations HackerTube score 4.5

HN commenters call it a beautiful, brilliant demonstration of APL's expressiveness and a model of clear narration.

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.

Also tagged: apl programming, apl, depth-first search, higher-order functions, array programming, dyalog

What Hacker News said

5 labeled comments from the HN archive; up to 20 are kept per video, favoring different commenters. Each one links back to the original thread.

Strongly recommends geocar July 2019 under Non-English-based programming languages
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]
Strongly recommends paliilap August 2019 under J can look like APL or English
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]
Strongly recommends geocar December 2021 under Show HN: KatLang – Language for Calculations
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!

Citations, criticism and jokes

Cites it jodrellblank May 2019 under A final proposal for Rust await syntax
Comment is about APL versus Python; video link is incidental.
Read the full comment
> 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
Cites it geocar December 2019 under Bryan Cantrill interviews Arthur Whitney (2009)
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

Keyboard shortcuts

/
Search
j k
Next / previous video in a list
Enter
Open the focused video
l
Like (on a video page)
w
Watch later (on a video page)
?
This help
Esc
Close