#dev 按照预期，今天晚上我还会讲关于我这周一个 Infix 链解析优化的算法、关于 RangeMap 的扩展 — OverlapRangeMap 的一些实现 note。

本周 #school 是月假；本来是还要写 Montage 图 Python 和 Dijkstra 同类的算法的，但是由于 Parser.kt 和 Binarie 更为重要，所以我不保证它们可以被有效执行。
不过我得先分享一些东西 — 比较方便的 IDEA 快捷键

== 代码浏览
上/下个方法: (Alt+ArrowUp / Alt+ArrowDown)
查看文档: Ctrl + Q
查看简明实现: Ctrl+Shift + I
查看表达式类型: Ctrl+Shift + P
跳转到符号: Ctrl + MouseL, Ctrl + B
跳转到类型定义: Ctrl+Shift + B
跳转到测试: Ctrl + T

== IDE 基本
文件菜单: Alt + F
Search everywhere: Ctrl + N
执行当前任务: Shift+F10
调试当前任务: Shift+F9

== Editor 基本
indent:
-: Shift + Tab
+: Tab （皆可按选区操作）
dup line: Ctrl + D
join lines: Ctrl+Shift + J

== 代码
快速模板: Ctrl + J
以快速模板包围: Ctrl+Alt + J
自动缩进/优化导入: (Ctrl+Alt + I / Ctrl+Alt + O)
自动布局: Alt+Shift + R

自动包围: Ctrl+Alt + T
自动去除包围: Ctrl+Alt+Shift + T

自动生成: Alt+Insert
自动重写/实现: (Ctrl+O / Ctrl+I)

手动唤起自动补齐: Ctrl + Space
类型敏感自动补齐: Ctrl+Shift + Space

== 重构
快捷菜单: Ctrl+Alt+Shift+T
上/下移语句: (Ctrl+Shift + ArrowUp / Ctrl+Shift + ArrowDown)
重命名: Shift+F6
改变方法签名: Ctrl+6
到变量/方法: (Alt+Shift+V / Ctrl+Alt+M)

== 分析
文件树: Ctrl + 0
继承树: Ctrl + H
方法调用树: Ctrl + Alt + H
查找引用: Alt+Shift + 7

如果你实在记不住，应当先记这些：

== 基础浏览和编辑
Alt+Up/Alt+Down
Ctrl+D/Ctrl+J
Ctrl+Space
Ctrl+T
Ctrl+N

== 文档
Ctrl+Q
Ctrl+Shift+I
Ctrl+Shift+P

== 模板
Ctrl+J / Ctrl+Alt+J
Ctrl+Alt+T
Alt+Insert

== 基本重构
Ctrl+F6
Ctrl+6
Ctrl+Alt+Shift+T
Ctrl+Shift+Up / Ctrl+Shift+Down
Alt+Shift+V / Ctrl+Alt+M

== 基本分析
Ctrl+0
Ctrl+Alt+H

== IDE 任务
Ctrl+9
Shift+F10
Shift+F9

当然这些都是可以自定义的，我说的是默认布局。

ParserKt 已经在设计上准备好进行第一次重写，这次重写会包含以下内容：

+ 针对 BulkFeeder 什么的；lineNumber 只能是 LF/CR/CRLF 中的一种，不可能在 Feeder 层面同时兼容
+ 对类似 ParsingFeeder、TreeRangeMap 的结构，开放一些辅助方法的覆写以提升代码重用性
+ 提供 reduceOr 和 leftrec 特性（左递归文法支持）
+ 针对基于 Buffer 的 MarkReset，它的 stack 必须是 lazily evaluated [newBuffer()]，这意味着 Parser.tryRun(Feeder) 的子解析器如果没有实际上 consume() 一些项目，就不会有调用架构器的开销
+ takeWhile 和 dropWhile 会被重命名为 takeTerminate; skipTerminate，FeederOpt 里的 takeUntilIn, skipWhileIn 重命名。
+ Folder 架构会有更多实例，比如 asHist(), asCount()
+ 很多原子解析器都会被重命名: char(_), anyChar, charSatisfies, charIn, charseq…
基本的原子解析器会被定义为内联的
+ 会加入很多扩展的内联解析修饰 (pre, effect, …)
+ Box<T> （就是可空版的 Maybe）会被正式包装好，也包括 map/flatMap 操作

在我证明了它可以解析 JSON 和 Kotlin 之后，我就会抛弃现在叫 jison 的 ParserKt；完全重写 ParserKt
新的库会更加模块化、更简单，并且会实现这次没有实现的 source map 和 clamDown 镇定解析策略。

整个测试，都是笑话；好了睡觉。

老版本的 ParserKt 不会维持多久的，它有太多的问题；尽管有不少代码都是好的，但是依然需要彻底脱胎重构、去除冗杂和莫名其妙的设计

#Haskell 里定义类型的一些方式：

type Ints = [Int] — type synonym

newtype User = User (String, Int) — newtype

newtype 就是「new」了的「type synonym」，exactly one constructor, exactly one field.
当然，一般它是和 Record 架解构同用的

newtype User = User { name :: String, age :: Int }

不要把它和 Monad 扯上关系。

data User = User String Int | Monkey Int — data declaration
这是代数数据类型 (Algebraic Data Types)

id (User name age) = User name age

解构等式定义，等号后面访问到的 name 是 User 的第一个 field (name :: String)、age :: Int
(\(User no yo) -> (no, yo)) :: User -> (String, Int)
这样的 Lambda 看起来是这样…… 当然也可以 let (no, yo) = user in … 解构

data Link a where
  Cons :: a -> Link a -> Link a
  Nil :: Link a

这是 GADT (-XGADTs)
(Generalized Algebraic DataTypes，也就是「广义」的代数数据类型)
它有两个架构器 (Cons h tail) 和 Nil （对面向对象来说就是子类型的架构器……）

最基本的情况，GADT 允许你直接写明架构器们的类型，当然这对类型系统是有用的，一般用来实现EDSL(Embedded Domain Specific Language)的AST(Abstract Syntax Tree)，不过是受更强类型检查的那种。

data Link a = Cons a (Link a) | Nil

对于这种情况 (Kotlin)
sealed class Link<out T> {
data class Cons(val head: T, val tail: Link<T>): Link<T>()
object Nil: Link<Nothing>()
}
(Scala)

trait Link[+T]
case class Cons[T](x: T) extends Link[T]
case object Nil extends Link[Nothing]

不过这里我们没直接用 GADT 们独有的特性，只是说，Link[T] 的这个 type variable T
被人称为「phantom type variable」(dummy 的 typevar)
它的意思是，T 只是用来确定 Link 里那个 T，和后面它的子类架构器的各种 T 无关：

{-# LANGUAGE GADTs #-}
data Ast a where
  I :: Int -> Ast Int
  P :: Bool -> Ast Bool
  And :: Ast a -> Ast a -> Ast a

（差点忍不住手痒把 type InfixCons t = t -> t -> t 抽提了…… Kotlin 里面可没有 Higher Kinds, type constructors 这么方便的东西啊，只能参数化多态）

所以我们的 (I 1) :: Ast Int，但 (And (I 1) (I 2)) 也是 Ast Int……（跑
如果不呢？

data Ast a = I Int | P Bool | And (Ast a) (Ast a)

And :: forall a. Ast a -> Ast a -> Ast a

(P True, I 2) 是什么？如果把他们取一个并集(union) 你会发现他们都是 forall a. Ast a…… 这个该死的 "unbound" 类型变量 a
And (P True) (I 2) :: Ast a 于是，你就可以得到一个完全无关的 Ast 类型
因为没有限制你也不可以保证 And (P p0) (I x) 不出现，Haskell 的 type checker 也不能保证（定义解构函数的时候）
实际上 (P True) :: (Ast String) 都可以，因为你 :type P 会发现它只是 forall a. P :: Bool -> Ast a，这是属于比较骚操作的情况了。
这就是 GADT 的作用，当然在 Kotlin 的类型系统里是不存在这类问题的，除非你要 Cons<T>(…): Link<out Nothing>()

以上描述会比
https://blog.hoshino9.org/2019/07/26/how-to-create-a-wonderful-type.html
的直白一些，用的概念也都是 Haskell 原生的（数据、数据架构器），而不是从 C++ 系套过来方便理解的（枚举…）

因为一方面，我觉得你把『类型』视为它『数据实例』的集合，然后取交(&,inersection)并(|,union)都不会的话，也就不要学 Haskell 了……
另一方面，从引文也可以看到如果要用 C++ 那一套的话，你会像数学一样弄出一大堆 XX类型 这种带修饰的名词…… 比如『枚举数据类型』、『只有一个值的枚举类型』、『带有参数的枚举类型』……
甚至你还可以弄出『带参数且只有一个值和一个case的枚举类型』……
说实话，这就是基本编程思想问题而已：是用 Desc(x: String?) 还是 Desc(x: String) | NoDesc？我觉得必须看情况来择一而取。
当然 Haskell 里的是最直白的，Haskell 的类型就是单纯的类型…… 不要把你用 data 定义的那一套当作『类型』…… 因为 Haskell 还有很多种『类型』足够打脸……

https://blog.hoshino9.org/2019/08/25/just-dependent-type.html
这是hoshi9对这个问题的解释，这篇文章他把Phantom type翻译为『幻影类型』

然后他还讲了 Data Kinds / Type Families 这些依赖类型的东西（这 Kotlin 就没法写了，因为它只是多态而没有 Kinds），这个我之前是不知道的，不过讲得很好也没必要再说一遍了。

Hoshi9大佬是女生啊 emmm 🌚???
不愧是女程序员呢…… Ada级别的啊

星野（我看了一点简单的日语，所以知道 hoshi ほし是繁星的意思，虽然冰封说是叫什么）大佬写的东西还真不错，很容易理解
虽然 Haskell 嘛，尤其是一些名字上的东西需要注意到，并且逐渐去熟悉，要不然看不懂在写什么的（自然语言也是一样嘛）

不过比起写 Monad，我觉得还是先写点工程能用的东西好一些。
用 Monad Transformers 真的是把 PLT 的问题都算法化了，可是如果要用 Haskell 写，当然 Haskell 比 Kotlin 高级啊，可是代码就难看很多
毕竟写什么东西用什么语言的
而现在我打算写的东西暂时碰不上 Haskell

我还是更想在一些所有人都能弄懂的地方创新，毕竟他们写的算法上多一些（虽然我现在算法上也不是设计不出……何况有Algorithms这本书作资源呢）
可是我觉得，他们还不够简单…… 还不够友好……

就是这样，暂时继续用 Kotlin 写一个简单的小东西再配上友好的接口，而不是 Scala/Haskell 加上 Dependent Types 解决许多工程不重视但是 PLT 重视的问题。

『盒子(不能直接取出内部物品的)』的比喻对范畴论来说虽然很不正确（因为盒子只是有封闭律和结合律、identity的图），但你会发现没有这个『盒子』的理解和举例，你根本不会理解 Functor, Applicative, Monad, State, 甚至只是 Identity/Maybe 那一套；即便别人解释得再简单、再可视化也不行，所以说知识到底还是要『讲』出重点的。

好比我开始想Dijkstra算法基本思路的时候，肯定要问『为什么每次要选余下节点里最小的更新权重，如果选中位数、极大(Max)值，甚至干脆随便选会怎么样？』这个问题，要不然你肯定无法理解算法需要输入数据满足的性质和它做的断言、不会知道为什么不能有『负权边』。
— 因为它做了一个断言：『任何可能是某点前驱的节点，其距离绝对小于该点』，这是为了在不连续的搜索过程中保证从『当前搜索路径』一直能够得到等价的新源点、保证一个点的距离被传递前它的所有可能路径均已经求得最短，所以不能有负权边。

可见对知识的第一印象是很重要的，错的第一印象看起来会导致谬误，但是没有能让人理解的第一印象就没有进步。
所以比起老是对『知识不准确』患得患失，不如踏踏实实先学一个不恰当的比喻，然后在以后的实践和学习中慢慢加深自己的理解，才可以做到大团圆的结局。

1+1=2？ - 孔良的文章 - 知乎
https://zhuanlan.zhihu.com/p/91153185 #FP
这篇文章是讲范畴论的

前置知识：De Bruijn Index - Trebor的文章 - 知乎
https://zhuanlan.zhihu.com/p/94601499 #PLT #FP

#Java 不能实现真正泛型的原因是什么？ - RednaxelaFX的回答 - 知乎
https://www.zhihu.com/question/28665443/answer/118148143

#dalao 叉姐是谁？ - 程序猴子的回答 - 知乎
https://www.zhihu.com/question/27295079/answer/36054398