APL 中的深度优先搜索
Depth-first search in APL
频道:Dyalog · 时长:11:32 · 发布:2014-07-18 · 播放:10721
简介
John Scholes 在 Dyalog APL 会话中逐步构建了一个深度优先树搜索操作符。涵盖了高阶函数,并在 N 皇后问题上运行了搜索。
HN 为什么推荐
HN 评论者称其为 APL 表达力的美丽、精彩演示,以及清晰叙述的典范。
中文字幕节选
这棵树有12个顶点或节点,包括一个根和七个 叶子。深度优先搜索或遍历先访问根节点,然后递归地 依次遍历每个子树。 嘿,APL的高阶运算符接受函数操作数以及 数组参数。原始运算符包括归约或 折叠、乘法归约、每个或映射、反转 每个、一个向量 向量和交换或切换1 2、连接、切换3 4。定义运算符时,双Alpha和双 Omega指其左操作数和右操作数,单Alpha和Omega指 其参数数组。例如,这个运算符将其左操作数 函数应用两次到其右参数数组。enclose应用两次 到一个字符向量。我们将定义一个双操作数 运算符用于深度优先树搜索,使用非正式类型表示法来 声明我们的意图。深度优先搜索将是一个运算符,它接受一个 初始累加器值作为左参数,一棵树作为右参数,并返回 整棵树的累加值。左操作数是一个函数 它接受一个累加器值和树节点,并返回一个后继 值,右操作数是一个函数,它接受一个累加器值和树 节点,并返回一个可能为空的子树 向量。编写我们的运算符。左操作数函数 双Alpha访问no Omega,返回累加器的后继 值,将其封闭以形成单个数组项,该项连接到 右操作数函数双Omega访问节点后返回的子树 向量。搜索递归应用。Dell指绑定其 操作数函数的运算符,在节点的值 和其每个子树之间进行累加归约。APL的原始归约运算符从 右侧折叠,所以我们必须反转其参数向量并交换 递归调用的参数。最后我们公开得到的累加器 项。我们不需要对递归的基本情况显式测试。如果子树 向量为空,归约应用于单个项,即叶节点的值 它直接返回作为结果。树表示 这个嵌套向量有七个节点:一个根、两个分支和 四个叶子。让我们搜索这棵树。给定一棵树 Omega,右操作数函数必须返回一个可能为空的子树 向量。布尔0等于节点的数组深度,叶子情况。丢弃子树 向量。正是右操作数函数单独 将树类型投影到携带运算符的主题数组上。其右 操作数派生出一个单操作数运算符,它遍历特定类型的 树,应用其左操作数函数。尝试各种 累加函数,我们可以计算树的节点数,从初始 值零开始。只计算叶子,其中0等于节点的数组 深度,或者将叶子列入一个向量。从 空向量作为累加器开始,并 连接,只取叶子项。在这些例子中注意 一个零或空身份项如何被呈现给原始累加函数 加法和连接,用于排除的情况。 然而,将嵌套数组列入是如此常见的需求,以至于APL 将其作为原始操作提供。树可以是上面的具体形式,或者子 树可以由右操作数函数即时实现。例如,当 搜索像数独或国际象棋 谜题这样的问题的解决方案时。挑战是将八个皇后放在棋盘上,使得没有 棋子攻击任何其他棋子。让我们实验。 给定一个向量,表示皇后在前三行中相隔马步放置的列位置, 我们可以在哪些列放置一个皇后在 第四行?皇后攻击这些列在 第四行沿着右 对角线 或者一般来说,对于任意行数,形状的索引的反转 Omega向量,以及这些列在第四行
HN 上的讨论
你可能会喜欢看看Dyalog如何处理高阶函数;John Scholes真的做了一个漂亮的演示,关于将它们用作深度优先搜索的可重用函数[VIDEO],如果你还没看过,你应该看看! — geocar, 2021-12
1975年的APL演示非常棒。Dyalog和GNU APL保留了许多内容——看到核心APL函数如此永恒不变,真的很有趣。我非常喜欢已故的John Scholes的一系列视频,他逐步讲解APL解决方案,包括著名的APL中Conway生命游戏的演示(0)。他关于深度优先搜索(1)和解决数独(2)的视频也很精彩。(0) [LINK] (1) [VIDEO] (2) [LINK] — paliilap, 2019-08
APL很棒。如果你没见过,已故的约翰·斯科尔斯做了许多绝对美丽的APL编程演示[1],[2],[3]。[1]:[VIDEO] [2]:[LINK] [3]:[LINK] — geocar, 2019-07
如果你的图中有环,你可以从索引向量构建一棵树,或者作为父/子节点键的表。前者是John Scholes所做的[1],后者有很多常见的SQL示例。 [1]: [VIDEO] 如果你有一个非循环树(例如256叉树),你可以直接嵌套它:@/ 将遍历到节点,而COW可以防止更新过多地破坏内存。然而树很少是最佳数据结构:在排序列表上进行二分搜索可以击败B树,仅仅因为搜索的末尾已经在缓存中,所以对于IP地址范围的路由表,我使用类似这样的东西: ipStart where ipStart bin x — geocar, 2019-12
> 还要注意,你对Python不公平。列表推导式、数组索引表示法和numpy方法几乎涵盖了你提到的APL中的所有内容。所有这些只覆盖了大约十个符号。指出这是复杂性的巨大差异,有人需要从头学习才能做到这些,这对Python不公平吗? > 这又回到了我之前说的:如果我想要一个强大的数组操作DSL,我仍然拥有它,但我不受其限制。这很好。只是数组操作DSL的少数操作比我预期的要强大得多。我知道APL不会是用来实现WireShark或Halo vNext的语言。第二段中的大问题是“如果我的对象支持那个”;是的,在APL中你必须做一些更复杂的事情。但不会/太/复杂。在Python中,你需要理解类、魔术方法和重载,然后才能编写那个重载的加法——并且要理解CPython内部、C和NumPy才能将其添加到NumPy对象中,我想。我怀疑你能在APL中完成所有这些,但话又说回来,如果我正确理解了l2范数加法,… — jodrellblank, 2019-05
相关视频
- APL中的数独求解器 · Dyalog · 9:43
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- Erlang和Elixir的灵魂 • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- “简单造就易用” - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- Richard Feldman 谈“让不可能的状态不可能” · elm-conf · 25:06
- William Byrd 谈“有史以来最美丽的程序” [PWL NYC] · PapersWeLove · 1:31:05
- Rich Hickey 谈价值的价值 · InfoQ · 31:43
- 为什么函数式编程没有成为主流?—— Richard Feldman · Metosin · 46:09
- 也许不 - Rich Hickey · ClojureTV · 1:03:28
- 用 Clojure 的方式解决问题 - Rafal Dittwald · Clojure/north · 1:02:26
- 第一讲A:Lisp概述与简介 · MIT OpenCourseWare · 1:12:55
- APL中的康威生命游戏 · Dyalog · 7:47
- 讲座 1A | MIT 6.001 计算机程序的构造和解释,1986 · MIT OpenCourseWare · 1:12:55
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- 高效程序 - Clojure 10年 - Rich Hickey · ClojureTV · 1:14:51
- Erlang Factory 2014 - 那是带 'B' 的 'Billion':在 WhatsApp 扩展到下一个级别 · Erlang Solutions · 49:15