再谈函数和一等公民

栏目: 数据库 · 发布时间: 5年前

内容简介:本文首发自本人博客写篇文章再谈谈函数和一等公民,因为我发现了些有趣的东西。先前想在自己的

本文首发自本人博客 eczn.github.io/blog/cc2509… 以下是原文:

写篇文章再谈谈函数和一等公民,因为我发现了些有趣的东西。

先前想在自己的 函数式方言解释器 里实现 元组 这种数据结构,但是没有什么方向,就去看了下 Scheme 的语法,看了下 Wiki,然后不知不觉间,看到了用 Lisp 实现 Pair。

Lisp 你可能听过,这里我们不需要它,但后面的 Pair 是啥,它其实是一种很简单的数据结构,类似这样,用 TyepScript 表示就是这样:

// 创建一个 pair
function cons(l: number, r: number) {
    return [l, r]
}

// 取出 pair 的左边 
function car(my_pair: number[]) {
    return my_pair[0]; 
}

// 取出右边 
function cdr(my_pair: number[]) {
    return my_pair[1]; 
}
复制代码

闲话一下,scheme 里创建 pair 的函数名就是 cons,还有它的两个操作 car 和 cdr 也是这个名字,因此本文也都用这个名字。

好吧,进入正题,形如上面这种样子的数据结构,叫做 Pair ,在很多 js 库里也有它的存在,比如 React.useState 返回的是左边是值,右边是 dispatcher 的 pair。

但我们这里讨论的是利用了数组去实现的,有没有别的方法去实现这种数据结构呢?答案当然是有的啦,下文将会给出仅利用函数的方式来实现这种数据结构,以及仅用函数去实现链表、二叉树。

Pair 的函数式实现

因为本人一开始是想在自己写的的一个函数式方言的解释器里加上 pair 这个类型的,因此看了 Pair 的函数式实现,如下:

;; 代码从 Wiki 摘录
;; https://en.wikipedia.org/wiki/Cons

(define (cons x y)
    (lambda (m) (m x y)))

(define (car z)
    (z (lambda (p q) p)))

(define (cdr z)
    (z (lambda (p q) q)))
复制代码

翻译成 TypeScript 就是这样:

// 姑且把 Pair 这种数据结构类型定义为函数
type Pair = Function; 

// 创建一个 cons
function cons(x: number, y: number): Pair {
    return (how_to_do_it: Function) => {
        return how_to_do_it(x, y); 
    }
}

// 取出 pair 的左值
function car(pair: Pair) {
    return pair((l, r) => l)
}

// 取出 pair 的右值
function cdr(pair: Pair) {
    return pair((l, r) => r)
}

const xy = cons(1, 2); 
// 调用 cons 返回一个函数

const x = car(xy); 
// => 1 

const y = cdr(xy); 
// => 2
复制代码

以上代码完美的体现了函数是一等公民这个概念,因为我们仅利用了函数去实现数据结构,这才是一等公民背后的意义。

挑战:函数式链表

现在,我们有了 Pair,它有两个值,此外,这两个值也是有序的,它可以用来构造链表吗?

当然可以,因为我们没有考虑到它有两个值里的值是啥。Pair 里的左值右值,既可以是数字,也可以是另一个 Pair,也就是说,Pair 里可以嵌套 Pair,据此可以递归地定义链表:

Pair(number, number | Pair | null) 当且仅当右值为 null 的时候,我们才认为链表到达了尽头

由上面的讨论可以很容易的利用 Pair 递归地构造出链表,也就是说,可以仅用函数实现链表。

或许你还没理解所谓递归地定义链表是啥意思,你可以看看下面的代码形式,便一目了然:

cons(1, cons(2, cons(3))) 1 -> 2 -> 3

根据上面的讨论,其 TypeScript 实现如下:

type Pair = Function;

function cons(x: number, y?: number | Pair): Pair {
    return (how_to_do_it: Function) => {
        return how_to_do_it(x, y); 
    }
}

function car(pair: Pair) {
    return pair((l, r) => l)
}

function cdr(pair: Pair) {
    return pair((l, r) => r)
}

// 取出链表的第 n 个
function nth(pair: Pair, n: number) {
    if (n === 0) {
        return car(pair); 
    } else {
        return nth(cdr(pair), n - 1); 
    }
}

const lst = cons(1, cons(2, cons(3)))
// 1 -> 2 -> 3 

const number = nth(lst, 0); 
// => 1 
复制代码

可以看到,cons 的 y 可以为空或者也是一个 pair 了,这里存在递归,因此取链表的时候用递归实现比较容易。

挑战:函数式二叉树

上面的讨论已经实现了链表,而链表里一个最特殊的地方便是引用,如果引用变成两个,链表就可以推广成二叉树。

以下是我的实现:

// 在把函数作为一等公民的语言里,
// 函数是一种数据类型/结构
type Tree = Function;

// 函数式二叉树
// 如果不指定范型,则认为树上存的值是数字; 
function Tree<T = number>(v: T, l?: Tree, r?: Tree): Tree {
    return (how_to_do_it: Function) => {
        return how_to_do_it(v, l, r); 
    }
}

// 取左子树
function lchild(tree: Tree) {
    return tree((v, l, r) => l);
}

// 取右子树
function rchild(tree: Tree) {
    return tree((v, l, r) => r); 
}

// 取值 
function valOf(tree: Tree) {
    return tree((v, l, r) => v); 
}

// 函数式二叉树的前序遍历
function traversal(t?: Tree) {
    if (!t) return;

    const l = lchild(t); 
    const r = rchild(t); 
    const v = valOf(t); 

    console.log(v); 
    
    traversal(l); 
    traversal(r); 
}

// 创建一棵树。。。
// 虽然有点绕... 
const t = 
               Tree(1,
    Tree(2, 
Tree(3), Tree(4)), Tree(5, Tree(6)))
// 结构如下: 
//        1
//     /    \
//   2       5 
//  / \     /
// 3   4   6 


// 先序遍历结果
traversal(t); 
// => 打印:123456
复制代码

上面的代码实现了二叉树的表示,并给出了二叉树的先序遍历方式。

那么,什么是函数呢?

我还不知道 233,不过时断时续的学习函数式语言,每次都有不同的收获是真。

上面的说明里可以窥见,所谓函数是一等公民,其实意味着函数可以实现编程语言里的其他事物,如数据结构。

这部分涉及到了 Lambda Calculus 这方面我学习的不深。。。。不展开了。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

机器学习

机器学习

(美)Tom Mitchell / 曾华军、张银奎、等 / 机械工业出版社 / 2008-3 / 35.00元

《机器学习》展示了机器学习中核心的算法和理论,并阐明了算法的运行过程。《机器学习》综合了许多的研究成果,例如统计学、人工智能、哲学、信息论、生物学、认知科学、计算复杂性和控制论等,并以此来理解问题的背景、算法和其中的隐含假定。《机器学习》可作为计算机专业 本科生、研究生教材,也可作为相关领域研究人员、教师的参考书。一起来看看 《机器学习》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具