Python函数式编程系列005:离题之定义自然数

郭嘉
• 阅读 1273

前言

在我们已经掌握了那么多建管子的方法之后,我们开始离题,看看我们能用最少的概念做哪些自举产生的事。在这一章中我们讲仅使用字符串"e",函数,if-else分支,=="e"运算,这四个概念来实现一个自然数的概念(实际中还用到了bool值,不过bool本身也可以用"e"f("e")表示)。

皮亚诺公理

我们首先回顾一下,数学如何定义即皮亚诺公理如何定义自然数,事实上,皮亚诺公理定义的是「无限可数集」的概念

  • (1) $$e \in S$$
  • (2) $$(\forall a \in S)(f(a) \in S)$$
  • (3) $$(\forall b \in S)(\forall c \in S)(f(b) = f(c) \rightarrow b = c)$$
  • (4) $$(\forall \in S)(f(a) \ne e)$$
  • (5) $$(\forall A \subseteq S)(((e \in A) \land (\forall a \in A)(f(a) \in A)) \rightarrow (A = S))$$
  • (1) 表示我们需要一个初始值,来表述我们可以从第一个东西开始数数,在这个符号集里叫\(e\)。对应于自然数的「1」的概念。
  • (2) 表示往下数一个数的操作,这个符号集里用\(f\)表述,我们一般也把这个操作叫后继。对应自然数中「加一」/「往下数一」的概念
  • (3) 确定恒等关系。
  • (4) 确定\(e\)不是任何数的后继,保证它是第一个被数的数。
  • (5) 归纳法

实现

我们仅仅需要下面两行代码就已经实现了自然数的全部定义,我们使用递归表示向下数数,用"e"表达了起始值「1」

one = "e" # 1
f = lambda x: lambda : x # 后继

当然,这么一个定义,是没有任何意义的,我们还需要实现判断相等加法乘法这三个最简单的算法。首先判断全等的方法就是我们将两个函数无限地求值下去,看到最后是不是同时得到"e"值,这也是对应了性质(3):

def equal(x, y) -> bool:
    if x =="e" and y =="e":
        return True
    elif x =="e":
        return False
    elif y =="e":
        return False
    else:
        return equal(x(), y())


not_equal = lambda x, y: not(equal(x, y))

注意我在上面的实现中使用了x =="e"这种前面带空格而后面不带空格的写法,其实是为了强调,=="e"是一个一元运算,我们仅使用到了它,而不需要其他概念。而仔细探究这个算式,我们发现其实它也隐式地用到定义(4),只要一个不为"e"我们就可以确定它们是不相等的。

定义加法其实也是一个非常容易的操作,我们只需要让一个参数计算后继,一个参数求值产生前继的概念:

def add(x, y):
    if y =="e":
        return f(x)
    else:
        return add(f(x), y())

最后是乘法的概念,这个我们可以调用add来递归实现:

def multiply(x, y):
    if y =="e":
        return x
    else:
        return add(multiply(x, y()), x)

其实我们也可以同理获得一个自然数求幂的函数,非常类似上面multiply的实现

def power(x, y):
    if y =="e":
        return x
    else:
        return multiply(power(x, y()), x)

这样我们可以非常快速地给20以内的数取名字了:

one = "e"
two = f(one)
three = f(two)
four = f(three)
five= f(four)
six = f(five)
seven = f(six)
eight = f(seven)
nine = f(eight)
ten = f(nine)
eleven = f(ten)
twelve = f(eleven)
thirteen = f(twelve)
fourteen = f(thirteen)
fifteen = f(fourteen)
sixteen = f(fifteen)
seventeen = f(sixteen)
eighteen = f(seventeen)
nineteen = f(eighteen)

OK,最后我们可以通过equal验证我们的算法对不对:

>>> assert equal(add(two, one), three)
>>> assert not_equal(power(two, three), seven)
>>> assert equal(power(two, three), eight)
>>> assert equal(multiply(three, five), fifteen)

结语

这一篇我们偏题地完成了一个「自然数」的定义,目的是为了展现,函数式编程的魅力在于:

  1. 我们可以用非常少的概念(在这个例子中是4个)就可以自举地实现非常多的事情。这个也是早期LISP语言(一种常见的动态函数式语言)会那么在AI领域或者一些对语言内核大小非常敏感的领域的原因。
  2. 因为函数式编程中的函数和数学上的函数非常接近,这使得在数学上使用的代数运算,都可以非常方便的实现(当然这一点我们在后面也会一一例举出来)。
点赞
收藏
评论区
推荐文章
blmius blmius
4年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
7个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Jacquelyn38 Jacquelyn38
4年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
HIVE 时间操作函数
日期函数UNIX时间戳转日期函数: from\_unixtime语法:   from\_unixtime(bigint unixtime\, string format\)返回值: string说明: 转化UNIX时间戳(从19700101 00:00:00 UTC到指定时间的秒数)到当前时区的时间格式举例:hive   selec
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这