Depth-first search in APL

Channel:Dyalog · Length:11:32 · Published:2014-07-18 · Views:10721

Watch on YouTube

Summary

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 HN recommends it

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

Functional programming · Algorithms & data structures

Subtitles (excerpt)

this tree has 12 vertices or nodes including one root and seven leaves a depth first search or traversal visits the root node and then recursively traverses each subtree in turn hey pl's high order operators take function operand as well as array arguments primitive operators include reduction or fold times reduction each or map reverse each a vector vectors and commute or switch 1 2 join switch 3 4 when defining an operator double Alpha and double Omega refer to its left and right operands and single Alpha and Omega to its argument arrays for example this operator applies its left operand function twice to its right argument array enclose applied twice to a character vector we will Define a two operand operator for a depth first tree search using an informal type notation to declare our intent depth first search will be an operator which takes an initial accumulator value as left argument and a tree as right argument and returns an accumulated value for the whole tree with a left upper end function which takes an accumulator value and a tree node and returns a successor value and a right operand function which takes an accumulator value and a tree node and returns a possibly null Vector of sub

On Hacker News

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 [VIDEO] and if you haven't seen it, you should! — geocar, 2021-12
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 als… — paliilap, 2019-08
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]: [VIDEO] [2]: [LINK] [3]: [LINK] — geocar, 2019-07
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]: [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… — geocar, 2019-12
> 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… — jodrellblank, 2019-05

Related videos