duangsuse::Echo

#DB 同意。如果王垠真的是那么说的，那么我觉得他错了，他的理解太偏向结构化编程范式了，无视了数据库的确只是为应用提供数据持久化、查询等操作的服务，不是什么结构体(C Struct)、数据项目实例和一大堆函数接口，那就把数据库当成 GC 堆了。

“就是C的struct，就是指针, 为什么不能RPC” 这句话... 不是很容易理解，我的理解是：为什么关系型数据库的『记录』上的操作不能直接被拿来当成远端过程调用去实现而非得 SQL，那显然就混淆了操作界面（接口）和实现，在面向侧面编程（AOP）甚至模块化里这是大忌，管你的理论学的再好，也永远有你没有学到的理论。

数据库系统也是信息技术应用的重要组成部分，虽然学 PLT （程序设计语言理论）的人一般看什么都会开明一些，但有时候还真是会有些许误解。

王垠开篇便开始详尽叙述数据结构和数据库的相同之处，如何“一个表本质上是一个数组”等等。

... 这不用我说肯定是不对的吧？关系表的本质并不是数组，而是抽象『元组』的集合

可以说，“只告诉它 What，而不是告诉它 How”，只是一个不切实际的妄想，而且它并不是 SQL 首创的想法

怎么可能呢？有的时候书上的东西也只是误会了而已，比如说所谓的 4GL（第四代计算机语言），其实这个概念根本不应该存在，
因为自存储程序型计算机开始，我们只是一直在提升抽象层次而已，从机器代码到它的助记符汇编（这里注意汇编不是一个特指，比如它不一定得是 x86 汇编），
到 Fortran, Basic, C, C++, 、上面的 Lua, Java, Python, Haskell、Agda, Coq, Prolog 什么的，甚至各种 DSL，甚至可以说 TensorFlow, PyTorch, Theano 都是编程语言，因为他们是描述计算的方式，而计算和描述方式可以有很多种，这怎么可能是空想呢？它当然不是 SQL 首创，因为 1920 年组合子逻辑（被证明和 Lambda 演算等价）就已经是一个例子了。这是 PLT 领域一直在变为现实的事情。
回答者对这个的观点我举双手赞成。

Prolog （miniKanren）的性能问题在 SQL 里面得到了部分的缓解，这是因为 SQL 对于基本的数据结构进行了“索引”

作者只回答了后半句，我对逻辑那边的东西也不是多熟悉，毕竟我工程得先过了再说。
然后这个索引我也不知道是怎么回事... 大概就是 SQL PRIMRY KEY 吧，考虑一下 hash table，我们可以通过先利用 int hashcode 的方式进行第一次剪枝排除，有冲突才需要 O(n) 再线性或者二分（如果冲突表是 Ordered, 有序的）查找

然而 SQL 的表达力也受到比 Prolog 更大的限制。很多 Prolog 可以表达的问题，SQL 没法表示。所以后来你就发现，SQL 其实只能用于非常简单的，适合会计等人员使用的查询操作。一旦遇到程序员需要的，稍微复杂一点的数据结构，它就会引起诸多的性能问题。

那 Agda 可以表达的类型问题

data forall {i l} {l : Nat} (a : Type i) Vec a l : Type i where
  nil : Vec a

 0
  _cat_ : a -> Vec a l' -> Vec a (suc l'')

啊写的好难看，而且我这里没有 Agda，那就照抄原文算了

data Vec {i} (A : Type i): Nat -> Type i where
  [] : Vec A 0
  _cat_ : forall {n} -> A -> Vec A n -> Vec A (S n)

那 Haskell 的 fold operator 和一些应用

foldr :: (a -> b -> b) -> b -> (a -> b)
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

递归的基线条件是 arg2 为 nil []；每层递归等待直到基线条件，回溯时第二个分支的最后一层先被 (f x v) :: b 调用，之前的结果被归纳直到彻底完成。

应用比如

product xs = foldr (*) 1 xs
sum = (foldr (+) 0) :: [Int] -> Int
filter p xs = foldr (\x rec -> if p x then x:xs else xs) [] xs


dropWhile p [] = []
dropWhile p (x:xs) = if p x then dropWhile p xs else x:xs

dropWhile' p xs = let (res, _) = foldr (\x (rec, sav) -> (if p x then rec else x:sav, x:sav)) ([], []) xs in res

这个就不那么 trivial 一点，然后我自己也想了很久，从这里扒的。

那就简单说，(\x -> lessThan 2 x) 这个

dropWhile' (<2) [9,0,1,2,3,4]

实际上递归
4 -> ([4], [4])
3 -> ([3, 4], [3, 4]) 👆 (cons sav, cons)
2 -> ([2, 3, 4], [2, 3, 4]) 👆 (cons sav, cons)
1 -> ([2, 3, 4], [1, 2, 3, 4]) 👆 (id, cons)
0 -> ([2, 3, 4], [0, 1, 2, 3, 4]) 👆 (id, cons)
9 -> ([9, 0, 1, 2, 3, 4], [0, 1, 2, 3, 4]) 👆 (cons sav, cons)
... -> （依此类推）

是不是我 SQL 不能表达就是我贫瘠 🌚???

更要命的是，这种性能问题的来源是根本性的，不可解决的，而不只是因为某些数据库的 SQL 编译器不够“智能”。很多人不理解这一点，总是辩论说“我们为何需要 Java 而不是写汇编，也就是我们为何需要 SQL。”然而，把 Java 编译成高效的汇编，和把 SQL 编译成高效的汇编，是两种本质上不同的问题。前者可以比较容易的解决，而后者是不可能的（除了非常个别的情况）。

首先：SQL 不一定需要编译器，它只需要实现查询操作并且给出结果就可以了。

“我们为何需要 Java 而不是写汇编，也就是我们为何需要 SQL。”

然而这个言论明显就是正常的，因为它把 SQL 当成了好用的工具，而 SQL 本身作为工具就很好用。
当然 SQL 也不一定得编译成汇编，其次，这里用“机器代码”更为合适吧，再其次，『为了自己能开心地去游乐园玩一趟而费重金弄一架私人飞机』这种事也不太实际吧，为什么我非得为实现查询语义来刻意去编译 SQL 本身？即使 SQL 可以根据数据库管理系统的信息被翻译成等价的查询程序？

我只举一个例子来说明这个问题。如果你需要迅速地在地图上找到一个点附近的城市，SQL 无法自动在平面点集上建造像 KD-tree 那样的数据结构。这是很显然的，因为 SQL 根本就不知道你的数据所表示的是平面上的点集，也不理解平面几何的公理和定理。跟 B-tree 类似，知道什么时候需要这种特殊的索引结构，需要非常多的潜在数学知识（比如高等平面几何），所以你肯定需要手动的建立这种数据结构

这是当然的啊，你不告诉 GHC dropWhile 的定义，只给类型人家自然也没办法弄出个你要的实现出来，数据可能有很多种，人家怎么能通过有限的数据和计算能力猜测你想要什么。

type Point2D = (Float, Float)

那即便不使用 kD-Tree 算法也是可以简单判断 filter 一下 floating point range 就可以得到 Rect 范围内的城市了... 但是要再优化为什么不写 C 扩展？这是它的错吗？

你发现了吗，你其实已经失去了所谓的“描述性”语言带来的好处

没有啊，而且你说的(描述性语言⇔逻辑式语言)
从某种意义上 SQL 还真的可以算是“逻辑式”，不过是 1 级的逻辑式（它不能组合操作成非线性
而且很多人并不认为它是逻辑式语言，只是觉得它是 "4GL" 而已

Baidu

组合子逻辑

组合子逻辑是 Moses Schönfinkel 和哈斯凯尔·加里介入的一种符号系统，用来消除数理逻辑中对变量的需要。

48 viewsduangsuse /'dʊɔːŋ sjuːz/ | [⃪PLD, FPλ], edited 14:01