Memoization是动态规划(Dynamic Programming)中自顶向下处理问题采用的策略, 其基本想法是通过将子问题的解保存起来避免重复计算来优化算法. 这个概念本身很简单, 在其他有明显mutable语义的语言中, 实现起来也非常简单. 但是在Haskell中问题就变的复杂了不少, 对于一个原始的函数f :: a -> b你如果要用ref, 比如说IORef, 你必须要把它放到IO monad中, 你的memoize函数就变成了... -> IO (a -> b). 我们希望是能够找到一个memoize :: ... -> (a -> b), 这样memoize之后得到的和原函数类型是一致的. 为了讨论的方便, 我们主要关注两个例子的memoization, 一个是经典的Fibonacci数列: 1 2 3 4 fib :: Int -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1) 另一个则是动态规划(自底向上)中典型的最小编辑距离的问题, 所谓的最小编辑距离就是一个字符串通过增加, 删除, 替换的操作得到另一个字符串所需要的操作次数: 1 2 3 4 5 6 minEditDist :: String -> String -> Int minEditDist [] [] = 0 minEditDist s [] = length s minEditDist [] s = length s minEditDist (x:xs) (y:ys) | x == y = minEditDist xs ys | otherwise = 1 + minimum [minEditDist xs ys, minEditDist xs (y:ys), minEditDist (x:xs) ys] Memoizing with specific problem 首先来看fib的问题, wiki给出了一个非常elegant的解(就fib本身而言, 还有更经典的解, fib = (fibs !!) where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)): ...

Pearl 2: 给定一个长度大于1的列表, 计算其元素的最大surpasser count, 要求算法复杂度 $O(n log n)$. Type: msc: Ord a => [a] -> Int “Pearls of functional algorithm design"的第二章, 我们先来看surpasser的定义 Definition surpasser: 称列表中$X[j]$是$X[i]$的surpasser, 如果$X[i] < X[j]$且$i < j$. 因此一个元素的surpasser count就是其surpasser的数目. 同样, 一个naive的实现很容易: 1 2 3 4 msc :: Ord a => [a] -> Int msc xs = maximum [scount z zs | z:zs <- tails xs] scount :: Ord a => a -> [a] -> Int scount x xs = length $ filter (> x) xs 同时也很容易看到, 这个实现的时间复杂度是 $O(n^2)$, 不符合要求的 $O(n log n)$. 为了达到 $O(n log n)$ 的时间复杂度, 我们希望有个函数f能够递归的处理xs = us ++ vs, 并且存在一个线性复杂度的函数join, 使得f xs = join (f us) (f vs), 这样整体的复杂度满足 $T(n)=2 T(n/2)+O(n)=O(n log n)$. 原文中, 作者利用分治的思想通过一步步地推导获得了线性时间的join, 这里也仅仅是类似于复读的"再解释”. ...

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.”）。即： ...

之前一直有使用Hexo来生成静态博客，如今将博客迁移到了Hugo下。两种工具总体而言各有优势，个人此次转移到hugo的主要原因大概是希望能够重拾写博客的习惯，本文主要介绍了使用Hugo的大致流程。首先给出个人博客的文件结构： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Root # blog根目录 | +-- archetypes +-- content |-- posts # 博客目录 |-- _index.md # 主页 +-- data +-- layouts +-- ox-hugo # org文件位置 |-- messy.org # category为Others的org文件 +-- public # submodule +-- resource +-- static +-- themes |-- xxx # 主题文件夹, submodule +-- .git +-- config.toml +-- .dir-locals.el # 自动将org文件转为markdown配置文件 +-- .gitmodules 其中只有 ox-hugo 为自定义文件夹, .dir-locals 为ox-hugo自动转换的配置文件，其他都是自动生成的。接下来个人就hugo生成博客关键部分展开介绍下。 ...