Things I Learned

Pearl 1: 给定一个自然数的有限集X, 计算不属于X的最小自然数. X表示为不包含重复元素的无序列表. 时间复杂度要求$O(n)$. Type: minfree :: [Int] -> Int(也可以额外的定义自然数类型, 不过这不是我们的重点) “Pearls of Functional Algorithm Design"的第一章, 其描述了一个分治的算法和一个基于array的算法, 这里按个人的思路讲解一下基于分治的算法, 基于array的算法具体可以查阅原文. 首先拿到这个问题, 我觉得最直接的想法就是 Base Solution: minfree xs = head $ [0..] \\ xs 然而这和要求的线性时间复杂度不符. 第二个想法就是设计一个fold的函数遍历一遍列表, 这样时间复杂度符合要求. 但是越来越多的边界条件让我意识到思路不对. 看了原文才发现忽略了解题的一个重要条件. Fact: [0..n]中的所有自然数不可能都在X(xs)中, 其中n = length xs. 这也很容易证明, 因为$ n + 1 = length\ [0..n] > n $, 因此不属于集合X的最小自然数就是[0..n]中不属于X的最小自然数. 至此,该问题很容易解决, 只需要一个marked的array来表示[0,,n]中的自然数是否在X中即可. 下面描述基于分治的算法, 首先给出一个基本的结论. Theorem: (as ++ bs) \\ (us ++ vs) == (as \\ us) ++ (bs \\ vs), 如果as \\ vs == as && bs \\ us == bs. ...

之前在"Essentials of Programming Languages"中学习过CPS(Continuation Passing Style), 而笔记在blog改版后被丢弃, 故在这篇文章中重新详细的探讨下CPS以及尾递归, 就当是温故而知新. Continuation 在理解什么是"Continuation Passing Style"之前, 我们首先需要定义Continuation(惭愧的是我都不知道中文叫啥, 查了下好像是"续延"). Continuation是计算机程序控制状态的抽象表示, 换言之, 其就是一种表示程序执行中间某一计算步骤的控制上下文的数据结构, 即表示某一计算的未来. 一个形象的例子是阶乘函数: 1 2 3 4 let rec fact n = if n = 0 then 1 else n * (fact (n - 1)) 当我们计算(fact 4)时, 其执行过程为(用lisp的形式是因为更加形象): 1 2 3 4 5 6 7 8 9 10 (fact 4) => (* 4 (fact 3)) => (* 4 (* 3 (fact 2))) => (* 4 (* 3 (* 2 (fact 1)))) => (* 4 (* 3 (* 2 (* 1 (fact 0))))) => (* 4 (* 3 (* 2 (* 1 1)))) => (* 4 (* 3 (* 2 1))) => (* 4 (* 3 2)) => (* 4 6) => 24 这过程中, (* 4 #)就是一个continuation, 是(fact 3)的控制上下文, 等待着(fact 3)的计算结果传入我们的"#", (* 4 (* 3 #))也是一个continuation. 容易看到的是在这样一个计算过程中, continuation在不断增长, 因为调用栈在不断增长, 程序不得不保存*的左操作数, 计算右操作数. 接下来, 我们来看fact的尾递归版本, 所谓的尾递归(tail recursion)指的是递归函数的递归调用部分只有函数调用, 即: ...

近来想于函数式编程中寻找类似与双向链表的数据结构, 结果找到了Zipper. Zipper中文为拉链, 泛指一类常在函数式编程中使用的聚合数据结构, 其加强了原有的数据结构, 使得能够遍历或更新原有数据结构的任意部分. zipper的关键思想是将目前需要处理的部分和不需要处理的部分分开, 同时保存目前不需要的部分, 也可以将其形象的理解为光标. 本文首先介绍了如何在list的基础上构建zipper, 随后将其扩展到二叉树上. list的例子 定义zipper list或者说是单向链表, 是函数式编程中最负盛名的结构, 其既简单又实用. 当我们需要修改list中的一部分时, 例如将[1 2 3 4 5]中的[3 4 5]替换为[5 6], list就带来了问题. 这时候一个简单的做法是: 1 2 3 4 5 6 let rec changeTailOfList l1 idx l2 = match l1 with | [] -> l2 // 忽略了idx大于0的情况 | x::xs -> if idx = 0 then l2 else x :: (changeTailOfList xs (idx - 1) l2) changeTailOfList [1; 2; 3; 4; 5] 2 [5; 6] // [1; 2; 5; 6] 看起来好像挺不错, 而这时候如果我们想要修改刚刚添加的内容, 例如在上面的例子中, 我们把5替换为[7 8], 这时候同样可以采取和changeTailOfList一样的做法, 从头开始遍历列表, 在目标位置进行更改. 显而易见, 在需要频繁修改某一部分的场合下, list是不适用的(虽然list本身就不是为了频繁修改某一部分而设计的). 然而, 这种需求是确实存在的, 在可变的条件下, 我们很容易想到双向链表, 设定一个指针指向我们当前操作的位置便可以方便的进行前向或后向修改. 那我们要如何在不可变的条件下满足这一需求呢? zipper正是为了解决这一类问题. 首先我们来定义list上的zipper: 1 2 3 type 'a ListZipper = ListZipper of 'a list * 'a list let zipper l1 = ListZipper (l1, []) 对于list而言, 我们需要处理的部分总是位于某个子列表的头部, 而需要保存的部分则是目标位置前面的部分, 因此我们可以用俩个列表, 一个表示目前正在处理的部分, 另一个表示之前的部分. ...

Bitwise tricks 近来翻到一本"Hackers Delight"的书, 其主要介绍基于二进制运算的算法. 初读来大感震撼, 其结果之巧妙,过程之精简, 于仅仅是了解计算机数是用补码所表示, 并未深入了解过二进制运算的人而言不可谓不精美. 正如Dijkstra所言, 计算机程序是集逻辑美感与机械实现的矛盾体. 本文姑且将其中的一些皮毛摘录如下, 以便日后之使用, 目前倒是难以得到应用. 使最右位的1变成0 1 2 3 // 01011000 -> 01010000 // if no one then return 0 x & (x - 1) 上式也可以用来判断一个无符号的整数是否是$ 2^n $的形式. 使最右位的0变成1 1 2 3 // 10100111 -> 10101111 // if no zero then return -1 x | (x + 1) 使尾部的1变成0 1 2 3 // 10100111 -> 10100000 // if no trailing 1s then identity x & (x + 1) 上式也可以用来判断一个无符号的整数是否是$ 2^n - 1 $的形式. ...

Value Restriction是什么？ Value restriction是用于控制类型推断能否对值声明进行多态泛化的规则（MLton原文：“The value restriction is a rule that governs when type inference is allowed to polymorphically generalize a value declaration.”）。常出现在ML系的语言中，如SML，OCaml，F#中，其实value restriction产生的本质原因是为了保证类型系统在结合参数多态与命令式特性（imperative feature，如ref）时候的可靠性（soundness）。一个典型的例子就是： 1 2 3 4 5 6 // 如果没有value restriction let x = ref None // 'a option ref let y: int option ref = x // type checked let z: string option ref = x // type checked let () = y := Some 2 // type checked let v: string = !z // 破坏了类型安全 限制了什么？ 简单来讲，value restriction限制了类型泛化只能发生在表达式的右边是句法意义上的值。那么什么是句法意义上的值呢，SML的语言规范上明确给出了什么样的表达式是句法意义上的值（准确来说是non-expansive）: 常量，如13，"string" 变量，如x,y 函数，如fn x => e 除了ref以外的构造函数在值上的调用，如Foo v 类型上受约束的值，如v: t 每一个元素都是值的tuple, 如(v1, v2, v3) 每一个字段都是值的record, 如{l1 = v1, l2 = v2} 每一个元素都是值的list, 如[v1, v2, v3] 确切的来讲，只要是协变（covariant）的类型并且不和可变的特性相结合，那么它总是可以类型安全的泛化（OCaml manual原文：“As a corollary, covariant variables will never denote mutable locations and can be safely generalized.”）。即： ...

Monad是Haskell中讨论最多的结构, 需要更详细的探讨其相关内容, 即使它对于Haskell而言不是必须的:(. 参考: All about Monads Monad Support 除了之前介绍过的一些基本函数, Haskell本身定义了一些辅助函数配合Monad一起使用: sequence 1 2 3 4 -- 任意一个fail会导致整个fail sequence :: Monad m => [m a] -> m [a] sequence = foldr mcons (return []) where mcons p q = p >>= \x -> q >>= \y -> return (x : y) sequence_和sequence类似但其不返回值, 在只关心序列的副作用时其非常有用. 1 2 sequence_ :: Monad m => [m a] -> m () sequence_ = flodr (>>) (return ()) mapM其由sequence和map定义 1 2 mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f as = sequence $ map f as mapM_, 类似的使用sequence_定义 1 2 mapM_ :: Monad m => (a -> m b) -> [a] -> m () mapM_ f as = sequence_ $ map f as =<<是>>=调换参数位置的版本 1 2 (=<<) :: Monad m => (a -> m b) -> m a -> m b f =<< x = x >>= f 上面提到的函数都是standard prelude中定义的, Haskell在Control.Monad模块中定义了更多函数. 下面是一些列表函数的Monad版本: foldM 1 2 3 foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a foldM f a [] = return a foldM f a (x:xs) = f a x >>= \y -> foldM f y xs filterM 1 2 3 4 5 filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] filterM p [] = return [] filterM p (x:xs) = do b <- p x ys <- filterM p xs return (if b then (x:ys) else ys) zipWithM和zipWithM_ ...

Semigroup 半群即一个集合以及在之上定义的一个满足结合律的二元运算, 在Haskell中定义为(部分): 1 2 3 class Semigroup where (<>) :: a -> a -> a {-# MINIMAL (<>) #-} Laws 1 2 -- associativity a <> (b <> c) = (a <> b) <> c Monoid “A monoid is a binary associative operation with an identity”, 在Haskell中定义为(部分): 1 2 3 4 5 6 class Monoid m where mempty :: m mappend :: m -> m -> m mconcat :: [m] -> m mconcat = foldr mappend mempty {-# MINIMAL mempty #-} Laws 1 2 3 4 5 6 7 8 -- left identity mappend menpty x = x -- right identity mappend x mempty = x -- associativity mappend x (mappend y z) = mappend (mappend x y) z 这和数学上带幺半群所满足的性质是一致的, 带幺半群即一个包含单位元的半群. ...

在考虑标识符和绑定(bindings)的时候, 关键在于区分标识符和它们所引用的对象, 以及以下事件: 对象的创建 绑定的创建 所有使用绑定的情况, 诸如引用变量, 子程序, 类型等 停用和重用那些暂时没有用的绑定 绑定的析构(destruction) 对象的析构 绑定的生命周期指的是这个绑定从创建到析构的整个过程, 类似的可以定义对象的生命周期. 通常情况下, 一个对象的生命周期可能会大于对应的绑定的生命周期, 即当 标识符不再引用该对象时, 该对象依然存在(例如在子程序中传入某个对象的引用, 如C++中的&参数). 当然, 一个绑定的生命周期也有可能大于对应对象的生命周期, 虽然这通常被认为是一个BUG. 对象的生命周期通常与以下内存分配(storage allocation)机制有关: 静态(static)对象会在程序的整个运行过程中被分配一个绝对地址. 栈(stack)对象随着子程序的调用和返回而被创建以及按照LIFO的顺序析构. 堆(heap)对象可以在任何时候创建和析构, 其额外要求更加通用和昂贵的内存分配算法. 静态分配(static allocation) 静态分配最明显的例子就是全局对象, 当然全局对象不是唯一的例子. 构成程序机器语言翻译的指令也可以认为是静态分配的变量; 数字和字符串的常量当然也是静态分配 的; 另外很多编译器会产生一系列的表用于支持运行时的debug, 动态类型检查, 垃圾回收, 异常处理等, 这些表也都是静态分配的. 静态分配的对象通常希望它们的值 不在变化, 因此经常被分配在被保护的只读的内存中以方便在试图修改其值产生中断并抛出运行时错误. 在很多语言中,一个具名常量通常要求有一个能够在编译期确定的初始值. 通常这些初始值都被限制在那些已知的常量以及内置的函数. 这些具名常量加上字面常量通常被 叫做表现常量(manifest constants)或者编译期常量(compile-time constants). 在某些语言中(C, Ada), 常量仅仅只是那些无法在elaboration time之后改变的值, 这些值可能依赖与其他在运行时才能确定的值. 这些elaboration-time的常量在作为递归函数的局部变量时必须要分配在栈上. C#显示提供了 声明两种常量的方法, 即const和readonly关键字. 另外编译器通常对于子程序的某些值采用特定的分配策略: 参数和返回值, 编译器通常会尽可能的将这些值存在寄存器中. 临时变量, 通常是那些复杂计算过程的中间值, 一个优秀的编译器也会将它们保存在寄存器内. bookkeeping information, 这些通常包含子程序的返回地址. 基于栈的分配(stack-based allocation) 一门语言如果想要支持递归, 那么在局部变量上采用静态分配的策略将不再适用(Fortran90之前不支持递归), 因为需要变量的个数是未知的. 所幸的是递归天然地适用 于栈结构的分配策略. 每一个子程序在运行时都有一个栈帧(frame, 或者称为活动记录, activation record), 包含了传入参数, 局部变量, 临时变量, 以及 bookkeeping信息. 通常传入参数位于帧的顶部, 方便被调用者定位参数, 而其他的布局则依赖于实现. 栈的维护是子程序调用序列的责任, 即调用者在调用前(序言, prologue)和调用后(尾声, epilogue)执行的代码. 通常有一个帧指针(frame pointer)来保存当前帧的地址, 在大多数语言的实现中, 栈都是往地址减 小的方向增长的. 在这样的实现方式下, 局部变量, 临时变量, bookkeeping信息对于帧指针有一个负的偏移, 而传入参数和返回对于帧指针则有一个正的偏移, 因为 这些都保存在调用者的帧上. ...