函数式编程

函数式的动态规划 动态规划是一类很常用的算法，在C/C++/Java中一般使用于数组进行记忆化。而函数式编程语言一般无法方便地操作数组这些依赖副作用的数据结构，函数式的记忆化便要另寻他法。 本文就是一个简单的笔记，用一些代码片段展示我所知的函数式动态规划的技巧。 （2020/5/17，时隔五个月后的更新，新增Memocombinators） Course-of-Values Recursion Course-of-Values Recursion是我认为最直观的一种技巧，就是将遍历过的结果当作返回值的一部分保留下来，在递归的时候可以取得运算过的值。 对于递归函数f，定义一个辅助的函数bar $\begin{align} \overline{f}(n) = [f(n), f(n-1),...,f(0)] \end{align}$ 则原递归函数f可以用bar表示出来： $head(\overline{f}(n))$ 斐波那契数列： fibBar :: Int -> [Int] fibBar 0 = [0] fibBar 1 = 1:fibBar 0 fibBar n = let course = fibBar (n-1) in -- [fib(n-1)..fib(0)] let p = course !! 0 in -- fib(n-1) let pp = course !! 1 in -- fib(n-2) p + pp : course -- >>> fibBar 10 -- [55,34,21,13,8,5,3,2,1,1,0] -- Binary Partitions：...

看到一篇反映了一些多数人对 APL 的误解的 art，决定写点文章让更多人了解真正的 APL。 bhuztez：函数式-21天入门教程 在原始APL里，求平均数，通常的写法是 $avg\leftarrow \{(+\omega)\div\not\equiv \omega\}$ 我不知道原始的 APL 指的是啥，不过 direct definition (用 {} 定义匿名函数， $\alpha\ \omega$ 指代参数) 是 Dyalog 搞的，叫 D-function，后來改叫 dfns，然後其它如 GNU APL 仿了 Dyalog 的这个feature，而且这个实现的历史可沒那么早 你看，2010 年的 APLX1 都压根不支持 dfns。(APLX 是比較接近 APL2 的，不过 IBM 的 APL22 当然是最标准的，可惜我沒有 mainframe 可以用) 可以查到的是 These ideas were first presented in the Dyadic Vendor Forum at APL96 where they appeared to meet with general approval. Dfns were introduced with APL/W version 8....

几天前，我的一个朋友给了我一个Haskell问题 Hey, MK，假设我有个BNF，并且我在Haskell中有个这个BNF的parser。 现在，我想给这个BNF改一行，有没有办法不用动这个BNF parser的代码（因为是其他人写的），而是对这parser进行扩展呢？ 这问题挺有趣的，也不算难。 这问题说是extensibility problem，其实有两个地方需要扩展。 0：Parser需要用open recursion之类的方法扩展 1：Parse出来的ADT也需要可扩展性 后半个需求见多了，Final Tagless，DTALC，Tree that grow，Recursion scheme style fix。。。于是放下不表，我们来处理前一个。 前半个。。Haskell’s Overlooked Object System就搞过，当然他们有点heavy weight，打算随手弄一个超级轻量级的：5行就够了，多一行是小莎莎。 Ready？ data Object x = MkObject (x -> x) 1。Inheritance is not subtyping式的Object=recursive type。为了简易性（反正也不需要多高的扩展性）就不model真。recursive type，而只有recursive dependency。 use :: Object x -> x use (MkObject x) = let res = x res in res 2。3。最典型的tying the knot。其实就是fix了。 我们想想，这个x是什么variant的呢？covariant还是contravariant？ inherit :: (a -> b) -> (b -> a) -> Object a -> Object b inherit ab ba (MkObject aa) = MkObject (ab ....

什么是Tail Call？ Tail Call（尾调用）指，我们调用一个函数后，立刻返回。 def triple(x): # 返回的不是函数 return x * 3 def is_tail_call(x): # 是尾调用，因为我们调用后就返回了 return triple(x) def not_tail_call(x): # 不是尾调用，因为我们调用完还要1 + result return 1 + triple(x) def half_tail_call(x): # 外面的是尾调用，里面的不是 return triple(triple(x)) 在以上例子中，is_tail_call的triple，跟half_tail_call的外面的triple，是tail call。 为什么Tail Call很重要？ 因为Tail Call提供了很好的优化。 假设我们是register machine，return address存在一个register里面，如果我们tail call，我们需要：把argument放对位置，然后goto function就可以了！ 如果是non tail call，我们需要把argument放对位置，保存旧的return address（比如说塞上stack），设定return address为下一行，goto function，把旧的return address restore掉，然后该干啥干啥。 这样，我们额外的多做了一push一pop，space & time overhead一下子上来了，怪不得60~70年代的人不肯用函数。。 当我们递归的时候，不做这个优化导致了big O上的空间差距 - 一个要不停的push stack，一个说，stack是啥？ 另一点是，当递归的时候，argument的位置是对的，‘放对位置’这一步就没有了，于是就成为了一个goto self - 也就是loop。 尾递归优化，其实就是Tail Call Optimization在taill call self下的优化。（见Debunking the ‘Expensive Procedure Call’ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO）...

大家520快乐！祝各位都能跟心仪的另一半进行crossover，产生fitness更高的后代哦~ 蛤？你没有另一半？没关系，本小编发现了一个库，用了这个库，你就能跟心仪的数据结构进行交合了哦~ 更厉害的是，交合对象跟你种类不一样也可以呢。甚至，多p交合也是小事一桩哦~ 你还在等什么，快来implement你内心深处的privateの梦吧！ http://okmij.org/ftp/Haskell/extensible/#crossover Extensible Effect旨在解决一个问题：如何Extensible的添加新Effect（这不废话吗） 我们的老朋友Data Type A La Carte酱尽管对Extensible挺能干的，但在这其实挺苦手的 - DTALC并不能Extensible的改变返回值，而每次新增Effect都需要这样做。 在Generic Crossover中，Oleg用Extensible Effect实现了一个State，一个Coroutine，然后就可以用两个effect来（加上SYB）作任意crossover 圆角骑士魔理沙：一招鲜，吃遍天 里面Session Type作法也很漂亮 - 更准确的说，看OK大法（final tagless，eff）的时候都会觉得像他那样做是正当作法，很trivial/natural，但是往往他本人也要一段时间才找得出来（可以看看eff的前身，当时还依赖奇奇怪怪的Request） 顺带一提，我很喜欢PL的原因是，概念是高度Composable的，新的概念往往可以用毫不相干的旧概念实现 - Generic Crossover用了Eff跟SYB，SYB自身又依赖于Typing Dynamic Typing这种做法，更极端的情况我觉得可以看EK这个comment： https://www.reddit.com/r/haskell/comments/387ex0/are_extensible_effects_a_complete_replacement_for/crt1pzm/ 更具体讲，一半lambda the ultimate一半growing a language呢。 http://library.readscheme.org/page1.html https://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf 另：The Reluctant Heroes莫名的好听 另另：知乎你们搞什么鬼，NLP做得这么烂，默认文章问题有生物学就算了，蔡英文跟马英九什么鬼，好歹要加入用户历史数据作prior啊

在Haskell等语言中，有datatype generic的概念：对于各种各样的ADT，都可以表示成一系列的Sum type 跟 Product type（因为这是ADT的定义），所以理论上，只要你能处理ADT的通用定义，你就能写一个对所有ADT适用的函数。其实这就是当你写deriving Show/Eq/Ord的时候发生的情况。generic，又称polytypic programming，就是把这理论变成现实的特性。注意这跟type generic是两码事。 这里面的Notable Work包括Scrap Your Boilerplate：把一定的类型信息塞到运行时，（Typable），然后就可以对某个类型做一种东西，而其他类型不变。然后可以写个高阶函数，对该类型做action，其他类型（wrapper，比如list/sum/either/whatever）就默认map进去，这样就可以给[Either [Double] Double]之类的type里面的所有Double翻倍，或者加起来返回。 GHC.generic做的是另外的东西，把一个类型表现成Sum type/Product type/Metadata（我们称作Rep），然后所有ADT都可以转化成这类型。然后加上把某类型变成它Rep的方法，就可以写function on all ADT，然后也可以写deriving等 True Sum Of Product就在GHC.generic上面做了层抽象，不用ADT来表示Rep，而是表示成[[*]] （类型的列表的列表）。然后有多参Product/Sum (可以想象成NProduct :: [*] -> *，其实具体情况复杂点），就可以直接组合/Map/Fold Product/Sum来完成generic programming，而无需在GHC.generic中递归，因为Sum type里面可能有Product type，然后里面再有Sum type。。。而这在True Sum Of Produt中不可能发生 然后还有Generic Generic Programming，因为有很多套Generic Library，每套都不一样，所以就搞出了个东西unify之。。。什么鬼 Generic Paper合集

今天发现了篇paper，http://brics.dk/RS/05/3/BRICS-RS-05-3.pdf 就是一个小trick，可以用于在2n pattern match下算出zip l (rev r) 看完以后觉得很简单啊，一点都不像某SM（Selection Monad（特大雾 不过为啥想不到呢，orz 最后：

这星期的文章是 http://cs.brynmawr.edu/~rae/papers/2012/singletons/paper.pdf。 这paper在codewars上，可以做做看：Singletons | Codewars 这文章在说两件事情： 0：用一种design pattern来做DT 1：这个design pattern可以用库automate一大部分 0： 假设我们有普普通通的data Nat = Z | S Nat。 首先，如果我们要把这用上type level（因为dependent type就是value可以在typelevel使用），我们需要额外的两个类型，一个ZType :: *，一个SType :: * -> *，来表示Nat的type level表示。然后，type level的Nat函数，可以用type family写出。 然后，可以用GADT表示inductive dependent type，比如Vec之类的。如果不支持GADT（什么鬼，不支持还想玩奇怪特性）可以考虑考虑用gadtless programming，换句话说用Leibniz Equality手动解constraint。。。 但是，由于parametricity，这无法做到：给入一个type level Nat，输出一个该长度的Vec。。。所以，做法是，再弄一个GADT inductive type，这个GADT的value是indexed on type level nat的。换言之，每一个type level nat，都能在这个GADT中找到一个unique的对应值。这就叫singleton 最后，很多时候singleton可以隐式推出，所以可以弄成一个constraint。 总结，一个datatype有4种做法：普通的，type level的，singleton，singleton变成constraint（换句话说，typeclass）。 1： type level的可以由GHC的DataKinds扩展自动生成。 singleton constraint可以统一到一个typeclass 由template haskell可以从普通函数生成singleton函数跟type level函数（type family） 最后：singleton constraint跟Data.Constraint有异曲同工之妙:) 还有，下期想看啥接着私信我。。。no monad tutorial，no 女装=/=

由于一直没找到好的并且能答得上的问题，以后打算时不时往这发点paper，然后对之进行一定的解释，练练手&降低阅读门槛（希望）。 这次的是 Embedded Probabilistic Programming 建议前置知识：Probability Distribution，Monad，Continuation P1-P6：我们想造一个编程语言，在这语言里面，所有变量都不是传统意义上的变量，而是Probability Distribution（PD）。 在本文中，一个a的PD可以看成一个List (probability, a)，其中，probability（简称prob）是double的别名，一个PD的元素，(probability, a)，代表在该概率下a的可能性是多小（这文章不考虑无限&连续的PD） 一个PD要满足两个条件：所有prob加起来是1，所有不同元素的a都不一样 在这定义下，我们可以定义多个PD下的函数：（此文皆为伪代码） return : a -> PD a，接受一个非随机的值，变成一个PD return x = [(1.0, x)] （这个随机变量只可能取一个值，就是传进来的那个） map : (a -> b) -> (PD a -> PD b)，把PD里的所有a 都变成b map f [] = [] map f ((prob, value):: rest) = (prob, f value):: map f rest join : PD (PD a) -> PD a，把一个概率分布的概率分布变成概率分布 join [] = [] join (prob_of_prob, prob_value): rest = loop prob_value ++join rest...

最近刚刚看完了Proof and Refutation，好长。。。 讲的是数学界各种对Proof，对Conjecture的看法，很喜欢，不过竟然没有怎么提公理体系，仅仅是一笔带过，这就有点不懂了= = 另：作者好强的文笔，竟然能同时驾驭这么多观点迥异的人物，还能描述他们的发展。。。我然后查了下wiki，好像是个很厉害的人。。。什么时候接着爬下他的work 最后，link： Proofs and Refutations (I) Proofs and Refutations (II) Proofs and Refutations (III) Proofs and Refutations (IV)还有这在CS的应用 Proof-Directed Debugging‘Proof-directed debugging’ revisited for a first-order version 去掉上面的Continuation，更加新手友好 （对于你打算教的人，对你更难了） Proof-Directed Debugging and Repair 试图把Proof-Directed Debugging搞成程序