首页 > 其他分享 >sicp每日一题[2.6]

sicp每日一题[2.6]

时间:2024-09-12 11:02:54浏览次数:10  
标签:square 函数 zero 每日 sicp add define 2.6 lambda

Exercise2.6

In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as $Church numerals$, after its inventor, Alonzo Church, the logician who invented the λ calculus.
Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).


这个题太难理解了,题目里的两个函数,zero 我搞明白了,也勉强能接受它跟 0 的作用相同,但是我始终理解不了为啥 add-1 的作用是加一,明明是 (f x) 啊。

; 任何数加 0 都等于它本身。所以,表示 0 的函数,无论你给它传入什么函数 f 和参数 x,它都直接返回 x,相当于什么都不做。
; (lambda (f) ...) 定义了一个匿名函数,它接受一个函数 f 作为参数,并返回 (lambda (x) x)。
; (lambda (x) x) 定义了另一个匿名函数,它接受一个参数 x,并直接返回 x。
; 组合起来:zero 函数本质上就是一个恒等函数,无论你给它传入什么函数 f,它都会返回一个新的函数,这个新函数会直接返回它的输入 x。
; 这符合我们对 0 的理解————任何数加 0 等于它本身。
(define zero (lambda (f) (lambda (x) x)))

; 1. 把 (lambda (x) (square x)) 传给 zero 作为参数,返回新的函数 (lambda (x) x)
; 2. 再把 10 传给 (lambda (x) x),得到原数 10
(display ((zero (lambda (x) (square x))) 10))    ; 输出是 10
(newline)

; n 必须是 Church Numeral,比如说上面定义的 zero
; 返回值是一个新的 Church Numeral,表示的值为 n + 1
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))


(display (((add-1 zero) square) 10))    ; 输出是 100
(newline)

; 1. 先用 f1 表示匿名函数 (lambda (x) (+ x 1)),则原式变为 ((zero f1) 0)
; 2. 把 zero 函数用它的定义替代,得到 (((lambda (f) (lambda (x) x)) f1) 0)
; 3. 把 f1 带入到 zero 的返回值函数,得到 ((lambda (x) x) 0)
; 4. (lambda (x) x) 函数会返回传入的参数,也就是0
((zero (lambda (x) (+ x 1))) 0)    ; 输出是 0

; 1. 把 zero 作为参数传入,得到 (lambda (f) (lambda (x) (f ((zero f) x))))
; 2. 先处理 (zero f),根据上面我们对 zero 函数的分析,无论传入什么函数作为参数,它都返回 (lambda (x) x)
; 3. 则 ((zero f) x) 就是 x,(lambda (f) (lambda (x) (f x))),也就是无论传入什么 f 和 x,都会返回 (f x)
(define one (add-1 zero))

; 根据上面的分析,下面的程序相当于执行 ((lambda (x) (+ x 1)) 0), 也就是 0 + 1
((one (lambda (x) (+ x 1))) 0)    ; 输出是 1

; 1. 把 one 作为参数传入,得到 (lambda (f) (lambda (x) (f ((one f) x))))
; 2. 根据上面的分析,((one f) x) 会返回 (f x)
; 3. 所以下面的函数无论传入什么 f 和 x,都会返回 (f (f x))
(define two (add-1 one))

; 根据上面的分析,下面的程序相当于执行 ((lambda (x) (+ x 1)) ((lambda (x) (+ x 1)) 0)), 也就是 ((0 + 1) + 1)
((two (lambda (x) (+ x 1))) 0)    ; 输出是 2

; 以此类推,可以用如下方式直接定义 one, two, three
(define new-one (lambda (f) (lambda (x) (f x)))) 
(define new-two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x)))))) 

; 虽然不理解为啥 add-1 可以表示加一,但是按照上面的规律,加法可以按下面的函数来定义
(define (add a b) 
  (lambda (f) 
    (lambda (x) ((a f) ((b f) x)))))

; 下面的程序相当于 ((two square) (square 2))
; 进一步替代得到 (square (square (square 2)))
(((add two one) square) 2)      ; 输出是 256

; 执行结果
10
100
0
1
2
256

标签:square,函数,zero,每日,sicp,add,define,2.6,lambda
From: https://www.cnblogs.com/think2times/p/18409778

相关文章

  • 每日OJ_牛客_合唱团(打家劫舍dp)
    目录牛客_合唱团(打家劫舍dp)解析代码1解析代码2牛客_合唱团(打家劫舍dp)合唱团__牛客网        有n个学生站成一排,每个学生有一个能力值,牛牛想从这n个学生中按照顺序选取k名学生,要求相邻两个学生的位置编号的差不超过d,使得这k个学生的能力值的乘积最大,......
  • SolidJS-每日小知识(9/11)
    知识介绍对指定SVG元素实现滚轮zoom代码分析1.对指定SVG元素实现滚轮zoom设置viewBox属性{x,y,w,h}以及缩放系数scale为信号量const[scale,setScale]=createSignal(1);//初始缩放比例const[boxLocation,setboxLocation]=createSignal({x:0,y:0});......
  • sicp每日一题[2.5]
    Exercise2.5Showthatwecanrepresentpairsofnonnegativeintegersusingonlynumbersandarithmeticoperationsifwerepresentthepairaandbastheintegerthatistheproduct2a3b.Givethecorrespondingdefinitionsoftheprocedurescons,car,a......
  • 小说推文:每日三位数收益轻松实现,稳定回报持久保障!
    该项目操作简便,仅需制作和发布视频即可,且全程可通过AI工具完成。项目潜力巨大,短视频平台用户基础广泛,覆盖面广。此外,同一视频可发布至多个平台,不会被判定为非原创。随着短视频平台的持续发展和用户基数的增长,小说推文项目依然具有很大的发展潜力。我们希望更多的人能发现并......
  • 小说推文:每日三位数收益轻松实现,稳定回报持久保障!
    该项目操作简便,仅需制作和发布视频即可,且全程可通过AI工具完成。项目潜力巨大,短视频平台用户基础广泛,覆盖面广。此外,同一视频可发布至多个平台,不会被判定为非原创。随着短视频平台的持续发展和用户基数的增长,小说推文项目依然具有很大的发展潜力。我们希望更多的人能发现并......
  • 小说推文:每日三位数收益轻松实现,稳定回报持久保障!
    该项目操作简便,仅需制作和发布视频即可,且全程可通过AI工具完成。项目潜力巨大,短视频平台用户基础广泛,覆盖面广。此外,同一视频可发布至多个平台,不会被判定为非原创。随着短视频平台的持续发展和用户基数的增长,小说推文项目依然具有很大的发展潜力。我们希望更多的人能发现并......
  • 高级java每日一道面试题-2024年9月06日-基础篇-Java中的PO、VO、BO、DO、DAO、DTO、PO
    如果有遗漏,评论区告诉我进行补充面试官:Java中的PO、VO、BO、DO、DAO、DTO、POJO是什么意思?我回答:PO持久化对象(PersistentObject)PO是持久化对象,用于表示数据库中的实体或表的映射通常与数据库表的结构和字段对应PO的属性对应数据库表的字段,可以进行持久化操作(新......
  • 每日算法随笔:反转链表 II
    明白了!下面我将基于你给的两种方法来详细解释题解,并展示每一步的变化过程。题解:反转链表II这道题要求我们反转链表中从第left个节点到第right个节点的部分,返回反转后的链表。我们会使用两种方法:递归和迭代。示例解析示例1:输入:head=[1,2,3,4,5],left=2,ri......
  • 每日算法随笔:反转链表
    题解:反转链表这道题目要求我们将一个单链表进行反转,返回反转后的链表。链表的反转可以通过迭代和递归两种方法来实现。下面我们将详细解释这两种方法,并通过例子演示每一步的变化过程。方法一:迭代法思路:我们用三个指针来完成链表的反转:prev表示前一个节点,curr表示当前节......
  • sicp每日一题[2.4]
    Exercise2.4Hereisanalternativeproceduralrepresentationofpairs.Forthisrepresentation,verifythat(car(consxy))yieldsxforanyobjectsxandy.(define(consxy)(lambda(m)(mxy)))(define(carz)(z(lambda(pq)p)))Whatistheco......