{ functional programming }

  • 如何编译函数闭包

    |

    // 知乎不仅不给我开专栏还说我这篇文章zz敏感,破网站吃枣药丸

    闭包(英语:Closure),又称词法闭包(Lexical Closure)或函数闭包(function closures),是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外。所以,有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体。闭包在运行时可以有多个实例,不同的引用环境和相同的函数组合可以产生不同的实例。

    想要实现一个同时支持词法作用域与 first-class function 的编程语言,一个重要的转换就是所谓的 lambda-lifting:把嵌套函数定义(包括匿名函数)转换为独立的全局函数定义;把自由变量的引用转换为参数传递。

  • 什么是函数式编程思维?

    |

    我为什么要把我的知乎回答搬到这里呢……大概是太久没发东西了来凑数吧。

    作者:nameoverflow

    链接:https://www.zhihu.com/question/28292740/answer/100284611

    来源:知乎

    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    函数式编程与命令式编程最大的不同其实在于:

    函数式编程关心数据的映射,命令式编程关心解决问题的步骤

    这里的映射就是数学上“函数”的概念——一种东西和另一种东西之间的对应关系。

    这也是为什么“函数式编程”叫做“函数式编程”。

    这是什么意思呢?

    假如,现在你来到 google 面试,面试官让你把二叉树镜像反转一下(大雾

    几乎不假思索的,就可以写出这样的 Python 代码:


    def invertTree(root):

    if root is None:

    return None

    if root.left:

    invertTree(root.left)

    if root.right:

    invertTree(root.right)

    root.left, root.right = root.right, root.left

    return root

    好了,现在停下来看看这段代码究竟代表着什么——

    它的含义是:首先判断节点是否为空;然后翻转左树;然后翻转右树;最后左右互换。

    这就是命令式编程——你要做什么事情,你得把达到目的的步骤详细的描述出来,然后交给机器去运行。

    这也正是命令式编程的理论模型——图灵机的特点。一条写满数据的纸带,一条根据纸带内容运动的机器,机器每动一步都需要纸带上写着如何达到。

    那么,不用这种方式,如何翻转二叉树呢?

    函数式思维提供了另一种思维的途径——

    所谓“翻转二叉树”,可以看做是要得到一颗和原来二叉树对称的新二叉树。

    这颗新二叉树的特点是每一个节点都递归地和原树相反。

    用 haskell 代码表达出来就是:

    data Tree a = Nil | Node a (Tree a) (Tree a)
    deriving (Show, Eq)

    invert :: Tree a -> Tree a
    invert Nil = Nil
    invert (Node v l r) = Node v (invert r) (invert l)

    (防止看不懂,翻译成等价的 python )


    def invert(node):

    if node is None:

    return None

    else

    return Tree(node.value, invert(node.right), invert(node.left))

    这段代码体现的思维,就是旧树到新树的映射——对一颗二叉树而言,它的镜像树就是左右节点递归镜像的树。

    这段代码最终达到的目的同样是翻转二叉树,但是它得到结果的方式和 python 代码有着本质的差别:通过描述一个 旧树->新树 的映射,而不是描述“从旧树得到新树应该怎样做”来达到目的。

    那么这样思考有什么好处呢?

    首先,最直观的角度来说,函数式风格的代码可以写得很精简,大大减少了键盘的损耗(

    更重要的是,函数式的代码是“对映射的描述”,它不仅可以描述二叉树这样的数据结构之间的对应关系,任何能在计算机中体现的东西之间的对应关系都可以描述——比如函数和函数之间的映射(比如 functor);比如外部操作到 GUI 之间的映射(就是现在前端热炒的所谓 FRP)。它的抽象程度可以很高,这就意味着函数式的代码可以更方便的复用。

    同时,将代码写成这种样子可以方便用数学的方法进行研究(这就是为什么可以扯上“___范畴上的___”这种数学上的高深概念)

    至于什么科里化、什么数据不可变,都只是外延体现而已。

  • Haskeller 的 PureScript 试水

    |

    – 讲道理虽然自称 Haskeller ,但是其实我根本不会 Haskell(

    为什么我要尝试 PureScript ?

    因为它是 Haskell 和 JavaScript 生的娃啊。

    Facebook 的 React.js 可以说是给 JavaScript 社区带来了一次 functional programming 的热潮。然而 JavaScript 毕竟不是真正的函数式编程语言——虽然有着 closure 等特性让它可以支持这种独特的范式,但是整体而言它还是基于顺序指令和事件回调的语言。

    PureScript 是一门年轻的语言——现在在 github 上可以查到的最早提交来自于 30 Sep 2013 。它致力于创造一种“类似 haskell 的编程体验”和“生成可读的 JavaScript 代码”。于是,有了它,我们终于可以在项目前端部分中愉快的写“ monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor ”了(