Depth-first search in APL
Channel:Dyalog · Length:11:32 · Published:2014-07-18 · Views:10721
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
- A Sudoku Solver in APL · Dyalog · 9:43
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- The Soul of Erlang and Elixir • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- "Simple Made Easy" - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- "Making Impossible States Impossible" by Richard Feldman · elm-conf · 25:06
- William Byrd on "The Most Beautiful Program Ever Written" [PWL NYC] · PapersWeLove · 1:31:05
- The Value of Values with Rich Hickey · InfoQ · 31:43
- Why Isn't Functional Programming the Norm? – Richard Feldman · Metosin · 46:09
- Maybe Not - Rich Hickey · ClojureTV · 1:03:28
- Solving Problems the Clojure Way - Rafal Dittwald · Clojure/north · 1:02:26
- Lecture 1A: Overview and Introduction to Lisp · MIT OpenCourseWare · 1:12:55
- Conway's Game Of Life in APL · Dyalog · 7:47
- Lecture 1A | MIT 6.001 Structure and Interpretation, 1986 · MIT OpenCourseWare · 1:12:55
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” · CppCon · 59:33
- Effective Programs - 10 Years of Clojure - Rich Hickey · ClojureTV · 1:14:51
- Erlang Factory 2014 - That's 'Billion' with a 'B': Scaling to the Next Level at WhatsApp · Erlang Solutions · 49:15