面向中年的lisp教程 أُعيد تغريده
面向中年的lisp教程
61 posts
面向中年的lisp教程
@height
too cool to be aging 第0推在这里: https://t.co/cMtwU8PW9K
انضم Eylül 2007
0 يتبع30 المتابعون
@wangpei 先把以前写好的继续整理成moments：
面向中年的Lisp教程[2].基本运算
twitter.com/i/moments/1123…
中文
照着Racket的方式写了一个python的cons/car /cdr
也可以用, 好玩. 只要你用的语言可以将函数作为函数的返回值就可以实现.
@lisp4middleAge/cons-car-cdr-in-python" target="_blank" rel="nofollow noopener">repl.it/@lisp4middleAg…
中文
cons/car/cdr大概是我觉得最无中生有的结构了.
cons可以用一段代码做出来, 而不依赖程序内置的cons结构. 这可是最基本的数据结构, 但却是可以用其他代码写出来的.
这一段代码我背不下来, 从SICP上抄下来的
@lisp4middleAge/conscarcdr" target="_blank" rel="nofollow noopener">repl.it/@lisp4middleAg…
中文
在racket中, 还可以使用list这个关键词来定义,
比如
(list 1 2)
返回的结果
'(1 2)
跟
(cons 1 2)差不多
'(1 . 2)
中文
这个结构看似简单, 实际很强大.
首先cons只是规定了一对参数, 并没有限定参数中必须是同样类型的,
比如:
(define x (cons 1 "a”))是完全合法的.
其次, cons可以嵌套cons. 比如
(define x (cons (cons 1 2) (cons 3 4))), 这就不仅仅是个列表, 而是一个树了
中文
LISP的list结构一共三句,
cons, car, cdr.
cons, 就是建立一个list,
car, list中的第一个.
cdr, list中的后一个. (读could-er)
(define x (cons 1 2))
(car x) -> 1
(cdr x) -> 2
中文
之前已经学习了racket基本的语句, 定义个函数也不太困难了. 接下来就要向更复杂的数据结构进发了.
欢迎来到LISP神奇的列表.
其实LISP的全称, LISt Processor, 就是列表处理机.
中文
因为是把SICP当作睡前读物, 所以电子版很重要, 因为用iPad看不用开灯了.
这里有几个不错的版本, 主要是公式排版很清楚, 推荐一下:
github.com/sarabander
适合各种阅读器的版本都有, 还有习题答案
中文
这个用费马小定理检验质数的方法当然也是在SICP上看到的. 不过我是看完书以后背着写下来的哦. 是在理解的基础上重现的. 应该是一种不错的对待例题的方式吧.
中文
一次检测当然不靠谱, 那给定T次检测吧, T这个数就由用户给吧.
那么如果一旦出现检测没通过, 就赶紧退出报错, 嘿, 这不是个质数. 如果检测通过了, 那就再来一次, 直到把T次检测机会都用完.
把几部分串在一起, 哒哒, 就完成了. 据说这个检测的复杂度是O(logN)呢
中文
用来测试的a应该是一个在1到n之间的随机数. Racket用(random x)产生一个<x的随机数, 所以+1 -1一下:
(define (rand_test n)
(core_test n
(+ 1 (random (- n 1)))))
中文
所以检测的核心是:
(define (core_test n a)
(=
(remainder (expt a n) n)
a
))
给定一个被检测数n, 和一个用来测试的数a, 计算a^n/n的余数是否=a
中文
如果余数不等于a, 那么n肯定不是质数. 但反过来不一定成立, 于是还要多测试几次, 如果很多次测试都通过了, 那么n"很可能"是质数.
是的, 这不是个确定性的检测, 不过速度很快, 一是(expt a n)可以优化, 二是求同余这个过程也可能优化
中文
这个用费马小定理来做质数检验的方法太好玩了. 定理是这样的:
如果n是一个质数, a是<n的正整数, 那么a^n / n的余数=a.
于是测试一个数n是否是质数的方法可以是从<n里面随机挑正整数a, 然后求
(remainder (expt a n) n)
中文
SICP把后一种阶乘的算法叫做迭代, 虽然它的写法是递归的, 也就是有自己调用自己. 不过我暂时觉得区分概念意思不大.
跟for循环类似的阶乘算法, 关键是在每次计算的时候要把运算结果传递给下一次运算. 这样就省去了需要等待递归边界再传回来的过程.
中文