函数式编程

原文：Folding in Parallel 作者：Oleg Kiselyov 本文描述了一种有趣的方法，用 map 和幺半群 reduce 来表述顺序执行的 fold。这样一来，某些看似有顺序的算法不仅可以并行运行，甚至还拥有美妙的并行性质：我们可以将输入序列任意分割给工作单元（如有必要，甚至可以递归地分割出子部分），并让工作单元并行运行——没有竞态条件、数据依赖，甚至不会有内存 bank 冲突。这种美妙的并行性质是多核、GPU 或分布式计算的理想选择。 这种方法的内在原理早已人尽皆知，但同样众所周知的是：将原理应用到具体案例需要独创性。 导言：fold vs. 幺半群 reduce Guy Style 在二〇〇九年的 ICFP 会议上发表了一篇题为 «foldl and foldr considered slightly harmful» 的主题演讲1。在演讲中，他提倡用 (map)reduce 取代 fold。 回想一下，序列上的 fold 本质上是一种带状态的按顺序累加；为具体起见，我们在列表上定义 fold_left : ('z -> 'a -> 'z) -> 'z -> 'a list -> 'z fold_right : ('a -> 'z -> 'z) -> 'a list -> 'z -> 'z 有一说一，现在我们有两种 fold：左 fold 与右 fold。下面的例子应该可以清楚地看出它们对应的语义...

原文标题：Similarity between instruction scheduling and imperative functional programming 作者：Oleg Kiselyov 原文链接：https://okmij.org/ftp/Haskell/fp-arrays-assembly.txt 将「典型的命令式编程代码」转换为函数式编程代码的过程，似乎有些类似于现代 CPU 编译器中使用的数据流和控制流依赖分析——所谓典型命令式代码，就是涉及了嵌套循环和可变数组的「典型数值计算」代码。下面将考虑三个此类转换的例子。 第一个例子在本主题之前的回帖中就已经讨论过，为了使该代码的内循环更有意义，这里对其稍作修改。该示例的命令式形式为 for(int i=1; i<=zx; i++) for(int j=1, a=i+1, b=i*j; j<=zx; j+=1, a+=1, b+=1) for(z=j; z<=zu; z+=2) array[z] = a, array[z+1] = b; 这个例子其实很简单。我们注意到代码只会写入 array，而不会读取 array，也没有控制流分支，唯一需要担心的就是更新 array 操作的顺序性问题。那么，解决方案就呼之欲出了——首先生成一个「更新列表」，这个列表告诉我们应该将数组的某个元素设置为某个值；生成列表之后，我们再按列表执行更新。我们可以用函数式编程生成这样的列表，然后用命令式编程——Monad 来执行。而且由于 Haskell 的惰性求值特性，我们可以一边生成更新列表的元素，一边执行。 下面是对应的 Haskell 代码 import ST -- 提取代码中所有更新数组的操作 ex1_update_list zx zu = concat $ [ [(z,a), (z+1,b)] | i <- [1..zx], (j,a,b) <- takeWhile (\(j,_,_) -> j<=zx) $ iterate (\(j,a,b) -> (j+1,a+1,b+1)) (1,i+1,i*i), z <- [j,j+2....

译自 Free and Freer Monads: Put Monad Back into Closet 简介 编写 Monad（现在还包括 Applicative 和 Functor）的实例，并确保实例符合 Monad 定律不但是定义 Monad 的重要部分，同时也是数量正在以指数级膨胀的「Monad 教程」的重要部分。而本文认为所有这些实例都不过是 boilerplate－－可以避免的 boilerplate！或许是因为听起来像拉丁语的名字和其引起的人们对顶尖数学的兴趣，这些琐碎的 boilerplate，琐碎的 Monad 定律，毫无新意的「管道」吸引了过多的关注。如果我们能直接思考副作用本身而非这些管道的工作原理，难道不让人耳目一新吗？ Free Monad，以及我们正要提到的 Freer Monad 将把我们从 boilerplate 中解放出来，从而专注于副作用的本质。有了它，我们就可以将解释器这一在编程语言研究和实践中的大杀器引入到副作用编程中－－为副作用定义解释器。 目前，已经有了许多关于 Free Monad 的精彩解释，这些解释往往援引了幺半群、普适代数和范畴论的观点。但最近流行的 Freer Monad 却给我们带来了困境：它的定位是什么？它能让我们更清晰地思考副作用吗？它也是『自由』的吗？如果是，为什么这些数学上的解释都没有预言 Freer Monad 的存在呢？本文接下来将解决这些问题，但唯独最后一个问题，我只能说，人们几次发现 Free Monad 都不是通过范畴论。（事后来看，范畴论上的联系确实存在，而且确实有洞见性）。与许多已有的解释不同，本文采取了通俗的方法，通过具体的例子而非抽象的代数解释 Free Monad（有关范畴论的内容将仅在括号中提及）。 经典 Monad 我们用耳熟能详的 State Monad 举例，该 Monad 代表『访问或更新一个可变状态』的副作用。常见的实现将这个可变状态作为返回值和参数沿着程序传递，然后通过 get 和 put 两个原语来获取/更新变量。 newtype State s a = State{unState :: s -> (a,s)} get :: State s s get = State $ \s -> (s,s) put :: s -> State s () put s = State $ \_ -> ((),s) runState :: State s a -> s -> (a,s) runState = unState get 和 put 操作，State s 蕴涵的定律以及解释器 runState，没有这三者，State s 就不能够作为真正的可变状态副作用计算使用。然而，为了在 Haskell 程序中方便地使用这些操作，我们要编写以下代码。...

第二节： Spore：【译】shift/reset 编程入门 (2)：应用 3 Delimited Continuation 操作符的理论基础 本节对 delimited continuation 操作符 shift/reset 的理论基础进行概述。我们使用的语言是一个从左到右求值1的 call-by-value λ 演算，并加入了多态的 let 和 shift/reset 操作符。 3.1 语法 $$\begin{alignat}{1} \text{(value)}& \quad V& \quad::=&\quad x \ | \ \lambda x. M \\ \text{(term)}& \quad M& \quad::=&\quad V \ | \ M~M \ | \ \mathsf{let}~x = M~\mathsf{in}~M \ | \ \mathcal{S}k.M \ | \ \langle M \rangle \\ \text{(pure evaluation context)}& \quad F& \quad::=&\quad [~] \ | \ F~M \ | \ V~F \ | \ \mathsf{let}~x = F~\mathsf{in}~M \\ \text{(evaluation context)}& \quad E& \quad::= &\quad [~] \ | \ E~M \ | \ V~E \ | \ \mathsf{let}~x = E~\mathsf{in}~M \ | \ \langle E \rangle \end{alignat} \\$$其中，shift (fun k -> M) 记作 $\mathcal{S}k....

0 译者前言 本文译自浅井健一先生的《shift/reset プログラミング入門（Introduction to Programming with Shift and Reset）》。找了一圈之后发现整个知乎上都没人教怎么使用 delimited continuation，遂翻译。 一些说明： 虽然文中说有任意函数式编程语言的经验即可，但例子和练习题用的是一个 Caml 变体，所以想要获得最佳阅读体验还是要了解 OCaml 或其他 ML 系编程语言的基础语法。 Rust 不算。 译文同时参考日语和英语版本，两版本如有不同则以正确/易懂一方为准。 部分译者的评论或解释用〔〕标注。原文的引用和注释则尽量还原（但由于知乎的限制只能混在一起了）。 译者翻译相关文献的经验并不丰富，如有任何错漏或可改进处请务必指出。 接下来开始正文内容。 摘要 Continuation 是在各种编程语言中都普遍存在的概念。条件语句是根据条件从两个 continuation（未来）中选择一个的操作，异常则可看作是丢弃一部分 continuation 的操作。还有，尾调用（goto 语句）就是执行 continuation 的操作。尽管 continuation 是这样一个无处不在的、十分自然的概念，目前为止，显式地使用 continuation 编程仍然一直被认为是困难的。 本教程使用 delimited continuation 操作符 shift 和 reset 来演示如何显式地使用 continuation，从零开始讲解关于 continuation 的基础知识，并在过程中指导读者实现简单的协程和非确定性搜索。本教程同时也能作为 CW 2011 演讲内容的引子。 本教程需要读者熟悉 OCaml、Standard ML、Scheme 或 Haskell 等函数式编程语言，但不需要读者在阅读本文前有任何有关 continuation 的知识。教程中穿插了各种练习问题，推荐读者随读随做。 1 引言 Continuation 就是表示「之后的计算」的概念。它可以看作是异常处理的一种推广，但远比异常处理要强力。实现复杂的计算时，实现者有时会发现需要使用在通常的程序结构中难以写出的控制结构。如果能操作 continuation，则可以在不影响程序整体可读性的前提下实现它们。 想要显式地使用 continuation，一种传统的方式是对整个程序进行 CPS1变换〔continuation passing style，指把 continuation 作为参数显式传递的编程风格〕，但这样就不能保留程序的原有结构。为了在引入 continuation 的同时保持程序的正常结构，我们就需要使用 continuation 操作符。...

第一节： Spore：【译】shift/reset 编程入门 (0)&(1)：前言和概述 2 shift/reset 编程 2.1 什么是 Continuation Continuation，简而言之就是「之后的计算」。程序的执行过程就是选出要执行的部分（称作 redex〔reducible expression，可归约表达式〕），对它求值，再使用它的结果来进行之后的计算。这里的「之后的计算」就是指 continuation。因此，continuation 是任何程序执行时都存在的基本概念。 为了展示 continuation 具体是什么，我们用 $[\,... ]$（称作 hole）来表示一段程序接下来要执行的部分。比如 $3 + 5 * 2 - 1$ 这一算式中，如果接下来要执行的部分是 $5 * 2$ 的话就可以写作 $3 + [5 * 2] - 1$，而这时的 continuation 就是 $3 + [~\cdot~] - 1$。总之，得到 $[~\cdot~]$ 的值（$5 * 2$ 的结果 $10$）之后，「给这个得到的结果加上 $3$ 减去 $1$」就是整个式子当前的 continuation。从「接受 hole 的值之后用它进行计算」这方面来看，continuation 和函数是相似的。 也可以用「抛出异常时扔掉的那部分程序」来看待 continuation。例如，把上述例子中 $[~\cdot~]$ 的部分换成 raise Abort，让它抛出异常，这时候被抛弃的部分 $3 + [~\cdot~] - 1$ 就是 continuation。...

Relens to Lens 之前也写过一篇lens的文章，学了新知识之后，现在看起来觉得不满意，于是打算重新再写一篇。 脚趾头：First Lens to Lenses Lens的设计十分的精妙，是数学指导编程的一个非常典型的案例。 Lens要解决的问题 在Haskell中，只提供了模式匹配的语法来操作数据，操作深层的是一个非常麻烦的事情。比如我们要操作以下数据： data Point = Point { positionX :: Double , positionY :: Double } deriving (Show, Eq) data Segment = Segment { segmentStart :: Point , segmentEnd :: Point } deriving (Show, Eq) p1 = Point 1 2 p2 = Point 3 4 l1 = Segment p1 p2 我们要修改l1的第二个端点的横坐标： l1 {segmentEnd = (segmentEnd l1) {positionX = 10}} -- 如果没有部分修改record的语法，这样的工作会更麻烦，只能用模式匹配一项项填 如果数据结构更加复杂的时候，代码就会变得更冗长。但如果用lens，刚刚的表达式就可以重写为：...

前言 Haskell中有一个很强大的库，叫做Lens。 在Haskell中，只提供了「模式匹配」的语法来访问/修改数据结构。于是处理深层的数据就成为了老大难的问题。 比如在这样的数据结构里： data Point = Point { positionX :: Double , positionY :: Double } deriving (Show, Eq) data Segment = Segment { segmentStart :: Point , segmentEnd :: Point } deriving (Show, Eq) p1 = Point 1 2 p2 = Point 3 4 l1 = Segment p1 p2 我们要修改l1的第二个端点的横坐标： l1 {segmentEnd = (segmentEnd l1) {positionX = 10}} 如果数据结构更加复杂的时候，代码就会变得更冗长。 这时候Lens库就出场了,刚刚那段代码等价于： l1 & endLens . xLens .~ 10 其中endLens ....

因为我太菜了，虽然其实第一部分都做出来了，但也就想好第一题比较理想的 tacit 解 {(⌽⍣(⍺<0))(⍺↑⍵)(⍺↓⍵)} 显然的解。 APLcart 给了个 tacit idiom, 注意用到了 18.0 新出的 Over operator，在 17.1 只能用 $\{\alpha\; \omega\}$ Is(↑,⍥⊂↓)Y ⍝ ←→ Is (↑{⍺ ⍵}↓) Y ←→ Is {(⍺↑⍵)(⍺↓⍵)} Y 但不能直接用上去，因为在 $\alpha$ 是负数的时，结果和要求是反向的 ¯3 (↑,⍥⊂↓) 'FooBar' ┌───┬───┐ │Bar│Foo│ └───┴───┘ 这就是为啥我用了 reverse，并用 power operator 控制，对应 $\alpha <0, \alpha >0$ 两个 case。但用了 power operator 就很难转成 tacit form 了。那么上面的答案要如何写成 tacit 呢。 可以換个角度，在负数时转成正数。假设有 f 做了这个工作，那么 {(a↑⍵)((a←⍺ f ⍵)↓⍵)} ⍝ ←→ {(⍺ f ⍵)(↑,⍥⊂↓)⍵} ←→ f(↑,⍥⊂↓)⊢ 那么 f 是什么呢，是这个么？...

本人有个小小的习惯，就是在学习一门语言的开始，为了熟悉这门语言的基础设施，我都会写一个最最简单的parserc（当然那些9012年都没有支持泛型的语言，就不写了）。 这次就试着用Rust来写一个。 从Iterator中来 用过Rust的Iterator的人，一定会觉得这用起来十分的愉悦，这说明Iterator设计得很不错。而parserc的使用方式其实和使用Rust的Iterator的方式十分相似的——先将小的组合子构造成大的组合子，然后再使用，parserc是.parse()，Iterator是.next()。 所以借鉴一下Iterator的思路，Rust版parserc也试着由这几部分构成： parser的trait 一些adapter 自定义一些combinator 组合出来的一些combinator 用起来大概是这样： // a+(b|c) fn aaab_c() -> impl Parser<Target=()> { char('a').some() .and(char('b').or(char('c'))) .map(|_| ()) } fn main() { let mut src = ParseState::new("aaab"); let res = aaab_c().parse(&mut src); assert_eq!(res, Some(())); } Parser trait 先定义parser的一般行为parse，“照搬”Iterator的结构。 #[derive(Clone, Debug)] pub struct ParseState<'a> { src: Chars<'a>, pub col: usize, pub row: usize, } pub trait Parser { type Target; fn parse<'a>(&self, state: &mut ParseState<'a>) -> Option<Self::Target>; } 在Haskell中，最简单的parse function的类型是String -> Maybe (a, String)：吞进去一个String，得到解析结果a，还有未匹配的字符串，或者没有结果，也就是匹配失败。这里也采用了类似的结构，有所不同的是，因为Rust是有mut的，可以直接改变状态，于是可以去掉用返回值表示的状态，改为可变引用；然后，parse的状态加上了行和列，为了方便，用字符迭代器表示要解析的字符串。...