面向中年的lisp教程

too cool to be aging
第0推在这里:

[Shengyi Wang @txyyss]

连 Racket 语言今天的启动画面都变成了心形…… #情人节

[面向中年的lisp教程 @height]

@wangpei #100DaysOfCode

面向中年的Lisp教程[3].函数
https://t.co/tKhm7Xj4Op

[面向中年的lisp教程 @height]

@wangpei 先把以前写好的继续整理成moments：

面向中年的Lisp教程[2].基本运算
https://t.co/HXucJtKZh0

[面向中年的lisp教程 @height]

照着Racket的方式写了一个python的cons/car /cdr
也可以用, 好玩. 只要你用的语言可以将函数作为函数的返回值就可以实现.

https://t.co/pRWn25wokl

[面向中年的lisp教程 @height]

cons/car/cdr大概是我觉得最无中生有的结构了.
cons可以用一段代码做出来, 而不依赖程序内置的cons结构. 这可是最基本的数据结构, 但却是可以用其他代码写出来的.

这一段代码我背不下来, 从SICP上抄下来的
https://t.co/5Yad7bX0T6

[面向中年的lisp教程 @height]

愿lisp可以在这个寒冷的冬天里给你一点点安慰

[面向中年的lisp教程 @height]

在racket中, 还可以使用list这个关键词来定义,
比如
(list 1 2)
返回的结果
'(1 2)
跟
(cons 1 2)差不多
'(1 . 2)

[面向中年的lisp教程 @height]

这个结构看似简单, 实际很强大.
首先cons只是规定了一对参数, 并没有限定参数中必须是同样类型的,
比如:
(define x (cons 1 "a”))是完全合法的.
其次, cons可以嵌套cons. 比如
(define x (cons (cons 1 2) (cons 3 4))), 这就不仅仅是个列表, 而是一个树了

[面向中年的lisp教程 @height]

LISP的list结构一共三句,
cons, car, cdr.
cons, 就是建立一个list,
car, list中的第一个.
cdr, list中的后一个. (读could-er)
(define x (cons 1 2))
(car x) -> 1
(cdr x) -> 2

[面向中年的lisp教程 @height]

之前已经学习了racket基本的语句, 定义个函数也不太困难了. 接下来就要向更复杂的数据结构进发了.
欢迎来到LISP神奇的列表.
其实LISP的全称, LISt Processor, 就是列表处理机.

[面向中年的lisp教程 @height]

很久没有更新了, 因为我最近睡得比较早. 所以作为催眠项目的racket学习反而停顿了.
这几天生活终于重回正轨, 所以又开始学racket了

[面向中年的lisp教程 @height]

因为是把SICP当作睡前读物, 所以电子版很重要, 因为用iPad看不用开灯了.
这里有几个不错的版本, 主要是公式排版很清楚, 推荐一下:
https://t.co/dpOmR6ZDEv
适合各种阅读器的版本都有, 还有习题答案

[面向中年的lisp教程 @height]

这个用费马小定理检验质数的方法当然也是在SICP上看到的. 不过我是看完书以后背着写下来的哦. 是在理解的基础上重现的. 应该是一种不错的对待例题的方式吧.

[面向中年的lisp教程 @height]

一次检测当然不靠谱, 那给定T次检测吧, T这个数就由用户给吧.
那么如果一旦出现检测没通过, 就赶紧退出报错, 嘿, 这不是个质数. 如果检测通过了, 那就再来一次, 直到把T次检测机会都用完.
把几部分串在一起, 哒哒, 就完成了. 据说这个检测的复杂度是O(logN)呢

[面向中年的lisp教程 @height]

用来测试的a应该是一个在1到n之间的随机数. Racket用(random x)产生一个<x的随机数, 所以+1 -1一下:
(define (rand_test n)
(core_test n
(+ 1 (random (- n 1)))))

[面向中年的lisp教程 @height]

所以检测的核心是:
(define (core_test n a)
(=
(remainder (expt a n) n)
a
))
给定一个被检测数n, 和一个用来测试的数a, 计算a^n/n的余数是否=a

[面向中年的lisp教程 @height]

如果余数不等于a, 那么n肯定不是质数. 但反过来不一定成立, 于是还要多测试几次, 如果很多次测试都通过了, 那么n"很可能"是质数.
是的, 这不是个确定性的检测, 不过速度很快, 一是(expt a n)可以优化, 二是求同余这个过程也可能优化

[面向中年的lisp教程 @height]

这个用费马小定理来做质数检验的方法太好玩了. 定理是这样的:
如果n是一个质数, a是<n的正整数, 那么a^n / n的余数=a.
于是测试一个数n是否是质数的方法可以是从<n里面随机挑正整数a, 然后求
(remainder (expt a n) n)

[面向中年的lisp教程 @height]

SICP把后一种阶乘的算法叫做迭代, 虽然它的写法是递归的, 也就是有自己调用自己. 不过我暂时觉得区分概念意思不大.

跟for循环类似的阶乘算法, 关键是在每次计算的时候要把运算结果传递给下一次运算. 这样就省去了需要等待递归边界再传回来的过程.